Optimal Unambiguous DNFs and Alon-Saks-Seymour

기술 요약: 최적의 모호하지 않은 DNF 및 Alon-Saks-Seymour

1. 문제 정의 및 배경

이 논문은 Balodis, Ben-David, Göös, Jain, Kothari [2023]가 제기한 세 가지 상호 연결된 퍼즐을 다룹니다. 이 퍼즐들은 다양한 복잡도 척도 사이의 분리와 그것이 그래프 이론 및 통신 복잡도에 미치는 영향에 관한 것입니다.

퍼즐 I (모호하지 않은 DNF): 불리언 함수 집합에서 0-증명 복잡도 $C_0(f)$가 모호하지 않은 1-증명 복잡도 $UC_1(f)$보다 유의미하게 큰 경우가 존재할 수 있는가? 구체적으로, $C_0(f) \ge \Omega(UC_1(f)^\alpha)$를 만족하는 $\alpha > 1$가 존재하는가? 이전 연구에서는 로그 차수($\log^6 n$) 범위 내에서 $\alpha \approx 2$임을 입증했습니다.

퍼즐 II (부분 함수): 부분 함수 $f$와 정의되지 않은 입력 $x$가 존재하여, $C_0(f, x)$와 $C_1(f, x)$가 모두 $\Omega(C(f)^\alpha)$인 경우가 존재하는가? 이전의 경계값은 $\log^2 n$ 인자까지 고려했을 때 $\alpha \approx 2$였습니다.

퍼즐 III (교차 하이퍼그래프): 교차 하이퍼그래프 $G$와 채색 $c$가 존재하여, 모든 $c$-단색 히팅 셋(hitting set)의 크기가 $\text{rank}(G) = r(G)$에 대해 $\Omega(r(G)^\alpha)$인 경우가 존재하는가? 이전의 경계값은 $\log^2 n$ 인자까지 고려했을 때 $\alpha \approx 2$였습니다.

이 퍼즐들은 그래프의 색칠 수 $\chi(G)$가 비클리크 분할 수 $bp(G)$에 1을 더한 값으로 제한된다는($\chi(G) \le bp(G) + 1$) Alon-Saks-Seymour 추측과 연결되어 있습니다. 이 추측은 Huang과 Sudakov [2012]에 의해 반박되었으나, 가장 잘 알려진 분리는 이중 로그 인자를 포함하여 차하가 최적은 아니었습니다: $\chi(G) \ge \exp(\Omega(\frac{\log^2 bp(G)}{(\log \log bp(G))^7}))$.

마찬가지로, Clique versus Independent Set (CIS) 문제는 코-논디터미니스틱(co-nondeterministic) 통신 복잡도의 하한을 찾는 문제입니다. 가장 잘 알려진 하한은 $\Omega(\frac{\log^2 n}{(\log \log n)^7})$였으며, 상한은 $O(\log^2 n)$입니다.

본 논문은 이러한 퍼즐들을 모든 다항 로그 인자를 제거하여 최적으로 해결하며, 결과적으로 Alon-Saks-Seymour 추측에 대한 최적의 반박과 CIS 문제에 대한 최적의 하한을 제공하는 것을 목표로 합니다.

2. 방법론 및 주요 기여

2.1 최적의 모호하지 않은 DNF 구축

저자는 **항 너비(term-width)**가 $O(n)$이지만 0-증명 복잡도가 $\Omega(n^2)$인 모호하지 않은 DNF $f: \{0, 1\}^{n^2} \to \{0, 1\}$ 집합을 구축합니다. 이는 $C_0(f) = \Omega(UC_1(f)^2)$임을 입증하며, 퍼즐 I을 최적으로 해결합니다.

구축 세부 사항:

• 집합-쌍 시스템 (Set-Pair System): DNF는 크기가 $n^2$인 유니버스 $U$에 대해, $n$개의 버킷 $B_1, \dots, B_n$ (각 크기 $n$)으로 분할된 "부호화된" 집합-쌍 시스템 $\{(P_T, N_T)\}_T$로부터 유도됩니다.
• 항 (Terms): 각 항 $T = (i, S)$는 결합 $C_T = (\bigwedge_{u \in P_T} x_u) \wedge (\bigwedge_{v \in N_T} \neg x_v)$에 대응합니다.
  • 양의 집합 ($P_T$): 버킷 $B_i$와 그 부분 집합 $S \subseteq B_i$ (크기 $n/2$)에 대해, $P_T = S$입니다.
  • 음의 집합 ($N_T$): $B_i \setminus S$와 "크로스 버킷" 집합 $A_{i,j}(S)$ ($j \neq i$)를 포함합니다.
• 모호하지 않음 (Unambiguity): 이 구축은 쌍별 비호환성(pairwise incompatibility)을 보장합니다: 임의의 서로 다른 항 $T, T'$에 대해, $P_T \cap N_{T'} \neq \emptyset$ 이거나 $P_{T'} \cap N_T \neq \emptyset$입니다. 이는 하나의 항이 만족되면 다른 모든 항이 거짓이 됨을 보장합니다.
• 확률적 방법: 크로스 버킷 집합 $A_{i,j}(S)$는 버킷에서 $[n]$으로의 무작위 비사형(random bijections/hashing)을 사용하여 구축됩니다. 확률적 방법은 전체 음의 집합의 크기가 $O(n)$을 유지하면서도 비호환성 조건을 유지할 확률이 존재함을 보장합니다.
• 증명 복잡도: 0-증명 복잡도는 양의 집합들 $\{P_T\}$의 히팅 수(hitting number)에 의해 하한이 결정됩니다. 모든 히팅 셋은 모든 버킷 내의 크기 $n/2$인 모든 부분 집합과 교차해야 하므로, 히팅 수는 $\Omega(n^2)$입니다.

2.2 상수 크기 가젯 리프팅 정리 (Constant-Gadget Lifting Theorem)

증명 복잡도의 분리를 통신 복잡도로 변환하기 위해, 저자는 $\Theta(\log n)$ 크기의 가젯을 사용하는 Göös 등의 표준 리프팅 정리[2016]를 개선하여 상수 크기 가젯 ($k=3$)을 사용하는 리프팅 정리를 도출합니다.

가젯 (The Gadget):
가젯 $g: \{0, 1\}^3 \times \{0, 1\}^3 \to \{0, 1\}$은 $\mathbb{Z}_8$ 상의 순환 함수입니다:
$$g(x, y) = 0 \iff y - x \in \{-1, 0, 1\} \pmod 8$$
그 외의 경우 $g(x, y) = 1$입니다.

스펙트럼 분석:
리프팅 증명은 리프팅된 함수 $h = f \circ g^{n^2}$와 관련된 행렬 $M$의 스펙트럼을 분석하는 데 의존합니다.

• 행렬 $M$은 가젯 $g$로부터 유도된 행렬 $W_0$와 $W_1$의 크로네커 곱의 합으로 구성됩니다.
• 저자는 최소 고윳값 $\lambda_{\min}(M)$이 어떤 $\rho < 1$에 대해 $-d \cdot \rho^{n^2}$보다 크거나 같음을 증명합니다.
• 이 스펙트럼 경계는 0-엔트리를 덮는 단색 직사각형(monochromatic rectangles)의 크기가 $\exp(\Omega(n^2))$여야 함을 의미합니다.
• 이는 $\log \text{Cov}_0(h) = \Omega(n^2)$를, $\log \text{Par}_1(h) = O(n)$을 도출하여, 다항 로그 손실 없이 이차적 분리를 달성합니다.

2.3 기타 복잡도 척도로의 응용

최적의 모호하지 않은 DNF와 Aaronson 등의 프레임워크[2016]를 사용하여, 저자는 다음과 같은 추가적인 분리를 도출합니다:

• 증명 복잡도 vs 근사 차수 (Approximate Degree): 저자는 $C(G) \ge \exp(\Omega(\tilde{\deg}(G)^4))$를 만족하는 전체 불리언 함수 $G$를 구축합니다. 이는 $C(f) \le \exp(O(\tilde{\deg}(f)^4))$라는 알려진 상한과 이전의 세제곱 분리 하한 사이의 간극을 메웁니다. 이 구축은 높은 증명 복잡도를 갖지만 낮은 차수의 검증 가능한 증명을 가진 부분 함수 $H$를 만든 후, 이를 전체화(totalize)하는 과정을 포함합니다.
• 증명 복잡도 vs 정확한 차수(Exact Degree) 및 민감도(Sensitivity): 이 구축은 $C(f) \ge \Omega(\deg(f)^2)$ 및 $C(f) \ge \Omega(s(f)^3)$를 함의하며, 이전 결과들로부터 다항 로그 인자를 제거합니다.

2.4 멀티클래스 샘플 압축 (Multiclass Sample Compression)

본 논문은 그래프 구축을 학습 이론, 특히 멀티클래스 개념 클래스의 샘플 압축에 적용합니다.

• Alon-Saks-Seymour 반박에서 사용된 그래프 $G$(정점 수가 $2^{\Theta(n^2)}$이고 $\chi(G) = 2^{\Omega(n^2)}$임)를 사용하여, 저자는 Natarajan 차원이 1인 멀티클래스 개념 클래스를 구축합니다.
• 이 클래스의 모든 샘플 압축 스킴은 레이블의 수 $c$에 대해 크기가 $\Omega(\sqrt{\log c})$여야 함을 보여줍니다. 이는 샘플 압축 크기가 레이블 수에 따라 증가해야 하는지에 대한 Pabbaraju [2024]의 열린 문제를 해결합니다.

3. 주요 결과

1. 최적의 모호하지 않은 DNF (정리 1): $UC_1(f) = O(n)$ 및 $C_0(f) = \Omega(n^2)$인 모호하지 않은 DNF의 존재.
2. 상수 가젯 리프팅 (정리 2): 3-비트 순환 가젯을 사용하여 증명 복잡도의 분리를 $\log \text{Cov}_0(h) = \Omega(n^2)$인 통신 복잡도 분리로 리프팅하는 리프팅 정리.
3. Alon-Saks-Seymour의 최적 반박 (정리 3): $bp(G) = 2^{O(n)}$ 및 $\chi(G) = 2^{\Omega(n^2)}$를 만족하며 $\chi(G) \ge \exp(\Omega(\log^2 bp(G)))$를 만족하는 그래프 패밀리의 존재. 이는 지수 내의 상수 차이를 제외하고 알려진 상한과 일치합니다.
4. 최적 CIS 하한 (결론 1.3): 코-논디터미니스틱 통신 복잡도가 $\Omega(\log^2 n)$인 Clique versus Independent Set 문제의 존재 (Yannakakis의 상한과 일치).
5. 사차 분리 (정리 4): $C(f) \ge \exp(\Omega(\tilde{\deg}(f)^4))$를 만족하는 불리언 함수 존재.
6. 샘플 압축 하한 (정리 5): Natarajan 차원이 1인 멀티클래스 개념 클래스에 대해, 샘플 압축 크기는 $\Omega(\sqrt{\log c})$임.

4. 의의 및 주장

본 논문은 Balodis 외 [2023]가 제기한 세 가지 퍼즐에 대해, 이전에 이러한 분리를 제한했던 다항 로그 인자를 완전히 제거함으로써 최적의 해결책을 제공한다고 주장합니다.

• Alon-Saks-Seymour: 이 결과는 색칠 수와 비클리크 분할 수 사이의 간격이 비클리크 분할 수의 로그의 제곱에 대해 지수적임을 보여줌으로써, 해당 추측에 대한 가장 강력한 반박을 제공합니다. 저자는 구축된 그래프의 크기 자체가 지수 내의 상수 차이를 제외하고 최적임을 언급합니다 (색칠 수가 $\chi$인 그래프는 적어도 $\chi$개의 정점을 가져야 하기 때문).
• 통신 복잡도: 이 작업은 Clique versus Independent Set 문제에 대한 최초의 최적 하한을 확립하여, 오랜 상한과 일치시켰습니다.
• 학습 이론: 샘플 압축 결과는 낮은 Natarajan 차원을 가진 클래스라 할지라도, 레이블의 수가 샘플 압축에 필요한 크기의 다항 로그 성장을 강제할 수 있음을 보여줌으로써, 레이블 수 $c$에 따라 경계가 증가해야 하는지에 대한 Pabbaraju [2024]의 질문을 부분적으로 해결합니다.

저자는 상수 가젯 리프팅 정리가 핵심적인 기술적 혁신임을 강조합니다. 일반적인 리프팅 정리는 존재하지만, 대개 $\Theta(\log n)$ 크기의 가젯을 필요로 하며, 이는 최종 경계에 이중 로그 인자를 도입합니다. 저자는 구축된 모호하지 않은 DNF의 특정 구조를 활용함으로써, 상수 크기 가젯으로 작동하는 리프팅 정리를 도출하여 마지막 남은 로그 인자들을 "깎아냈습니다(shaving)".

본 논문은 일반적인 log-rank 추측을 해결한다고 주장하지는 않지만, 그들의 결과가 다항 로그 인자를 제거함으로써 log-rank 추측에 대한 알려진 이차 하한을 개선했음을 언급합니다. 마찬가지로, 샘플 압축 경계가 $\Omega(\sqrt{\log c})$이지만, 저자는 이것이 상한이 $c$에 대해 다항식이라는 점을 고려할 때 $c$에 따라 증가해야 하는지에 대한 질문에 대한 부분적인 해결임을 인정합니다.