=== TECHNISCHE SAMENVATTING ===

Optimale Onambiguïteit van DNFs en Alon-Saks-Seymour

1. Probleemstelling en Context

Dit artikel behandelt drie onderling verbonden puzzels in de computationele complexiteit en combinatoriek, oorspronkelijk geponeerd door Balodis, Ben-David, Göös, Jain en Kothari [2023]. Deze puzzels hebben betrekking op de scheiding tussen verschillende complexiteitsmaten en hun implicaties voor de grafentheorie en communicatiecomplexiteit.

Puzzel I (Onambiguïteit van DNFs): Kan er een familie van Booleaanse functies bestaan waarbij de 0-certificaatcomplexiteit $C_0(f)$ significant groter is dan de onambiguïteit 1-certificaatcomplexiteit $UC_1(f)$? Specifiek, kan $C_0(f) \ge \Omega(UC_1(f)^\alpha)$ gelden voor $\alpha > 1$? Vorig werk stelde vast dat $\alpha \approx 2$ is, tot aan polylogaritmische factoren ($\log^6 n$).

Puzzel II (Partiële Functies): Kan er een partiële functie $f$ en een ongedefinieerde input $x$ bestaan waarbij zowel de 0-certificaatcomplexiteit $C_0(f, x)$ als de 1-certificaatcomplexiteit $C_1(f, x)$ $\Omega(C(f)^\alpha)$ zijn? Vorige grenzen waren $\alpha \approx 2$ tot aan $\log^2 n$ factoren.

Puzzel III (Intersecterende Hypergrafen): Kan er een intersecterende hypergraaf $G$ en een kleuring $c$ bestaan zodanig dat elke $c$-monochromatische hitting set een grootte heeft van $\Omega(r(G)^\alpha)$, waarbij $r(G)$ de rang is? Vorige grenzen waren $\alpha \approx 2$ tot aan $\log^2 n$ factoren.

Deze puzzels zijn verbonden met de Alon-Saks-Seymour conjectuur, die stelt dat de kromingsgetal $\chi(G)$ van een graaf begrensd wordt door het biclique partitiegetal $bp(G)$ plus één ($\chi(G) \le bp(G) + 1$). Deze conjectuur werd weerlegd door Huang en Sudakov [2012], maar de best bekende scheiding was suboptimaal, waarbij dubbel logaritmische factoren betrokken waren: $\chi(G) \ge \exp(\Omega(\frac{\log^2 bp(G)}{(\log \log bp(G))^7}))$.

Op vergelijkbare wijze zoekt het Clique versus Independent Set (CIS) probleem naar een ondergrens op de co-nondeterministische communicatiecomplexiteit. De best bekende ondergrens was $\Omega(\frac{\log^2 n}{(\log \log n)^7})$, terwijl de bovengrens $O(\log^2 n)$ is.

Het doel van dit artikel is om deze puzzels optimaal op te lossen, waarbij alle polylogaritmische factoren worden verwijderd, en daarmee een optimale weerlegging te bieden van de Alon-Saks-Seymour conjectuur en een optimale ondergrens voor het CIS-probleem.

2. Methodologie en Belangrijkste Bijdragen

2.1 Constructie van Optimale Onambiguïteit van DNFs

De auteur construeert een familie van onambiguïteit DNFs $f: \{0, 1\}^{n^2} \to \{0, 1\}$ met term-breedte $O(n)$ maar 0-certificaatcomplexiteit $\Omega(n^2)$. Dit vestigt $C_0(f) = \Omega(UC_1(f)^2)$, waarmee Puzzel I optimaal wordt opgelost.

Constructiedetails:

• Set-Pair Systeem: De DNF is afgeleid van een "gesigneerd" set-pair systeem $\{(P_T, N_T)\}_T$ over een universum $U$ van grootte $n^2$, verdeeld in $n$ buckets $B_1, \dots, B_n$ van grootte $n$.
• Termen: Elke term $T = (i, S)$ komt overeen met een conjunctie $C_T = (\bigwedge_{u \in P_T} x_u) \wedge (\bigwedge_{v \in N_T} \neg x_v)$.
  • Positieve Set ($P_T$): Voor een bucket $B_i$ en een deelverzameling $S \subseteq B_i$ van grootte $n/2$, is $P_T = S$.
  • Negatieve Set ($N_T$): Omvat het complement $B_i \setminus S$ en "cross-bucket" verzamelingen $A_{i,j}(S)$ voor $j \neq i$.
• Onambiguïteit: De constructie garandeert wederzijdse incompatibiliteit: voor elke afzonderlijke termen $T, T'$ geldt dat ofwel $P_T \cap N_{T'} \neq \emptyset$ ofwel $P_{T'} \cap N_T \neq \emptyset$. Dit garandeert dat als één term wordt vervuld, alle andere worden weerlegd.
• Probabilistische Methode: De cross-bucket verzamelingen $A_{i,j}(S)$ worden geconstrueerd met behulp van willekeurige bijeenfuncties (hashing) van buckets naar $[n]$. De probabilistische methode zorgt ervoor dat met een positieve waarschijnlijkheid de totale grootte van de negatieve verzamelingen $O(n)$ blijft, terwijl de incompatibiliteitsvoorwaarde behouden blijft.
• Certificaatcomplexiteit: De 0-certificaatcomplexiteit wordt ondergrenst door het hitting getal van de familie van positieve verzamelingen $\{P_T\}$. Aangezien elke hitting set elke deelverzameling van grootte $n/2$ in elke bucket moet snijden, is het hitting getal $\Omega(n^2)$.

2.2 Constant-Gadget Lifting Theorem

Om de scheiding in certificaatcomplexiteit te vertalen naar communicatiecomplexiteit, leidt de auteur een lifting theorem af met behulp van een constant-grootte gadget ($k=3$), wat een verbetering is ten opzichte van het standaard lifting theorem van Göös et al. [2016] dat een gadget van grootte $\Theta(\log n)$ gebruikt.

Het Gadget:
Het gadget $g: \{0, 1\}^3 \times \{0, 1\}^3 \to \{0, 1\}$ is een cyclische functie gedefinieerd op $\mathbb{Z}_8$:
$$g(x, y) = 0 \iff y - x \in \{-1, 0, 1\} \pmod 8$$
Anders is $g(x, y) = 1$.

Spectrale Analyse:
Het bewijs voor het lifting proces berust op het analyseren van het spectrum van een matrix $M$ geassocieerd met de lifted functie $h = f \circ g^{n^2}$.

• De matrix $M$ wordt geconstrueerd als een som van Kronecker-producten van matrices $W_0$ en $W_1$, afgeleid van het gadget $g$.
• De auteur bewijst dat de minimale eigenwaarde $\lambda_{\min}(M)$ ondergrenst wordt door $-d \cdot \rho^{n^2}$ voor een $\rho < 1$.
• Deze spectrale grens impliceert dat elke dekking van de 0-entries van de communicatiematrix door monochrome rechthoeken een grootte van $\exp(\Omega(n^2))$ moet hebben.
• Dit levert $\log \text{Cov}_0(h) = \Omega(n^2)$ op, terwijl $\log \text{Par}_1(h) = O(n)$, wat een kwadratische scheiding bereikt zonder polylogaritmische verliezen.

2.3 Toepassingen op Andere Complexiteitsmaten

Gebruikmakend van de optimale onambiguïteit DNFs en het raamwerk van Aaronson et al. [2016], leidt het artikel verdere scheidingen af:

• Certificaatcomplexiteit versus Benaderingsgraad: De auteur construeert een totale Booleaanse functie $G$ met $C(G) \ge \exp(\Omega(\tilde{\deg}(G)^4))$. Dit sluit de kloof tussen de bekende bovengrens $C(f) \le \exp(O(\tilde{\deg}(f)^4))$ en de vorige ondergrens van een kubische scheiding. De constructie betreft een partiële functie $H$ met een hoge certificaatcomplexiteit maar lage-graad verifieerbare certificaten, die vervolgens getotaliseerd wordt.
• Certificaatcomplexiteit versus Exacte Graad en Sensitiviteit: De constructie impliceert $C(f) \ge \Omega(\deg(f)^2)$ en $C(f) \ge \Omega(s(f)^3)$, waarbij de polylogaritmische factoren uit eerdere resultaten worden verwijderd.

2.4 Multiclass Sample Compression

Het artikel past de graafconstructie toe op de leertheorie, specifiek sample compression voor multiclass concept classes.

• Met behulp van de graaf $G$ uit de Alon-Saks-Seymour weerlegging (die $2^{\Theta(n^2)}$ knopen heeft en $\chi(G) = 2^{\Omega(n^2)}$), construeert de auteur een multiclass concept class met Natarajan dimensie 1.
• Zij tonen aan dat elk sample compressie schema voor deze klasse een grootte moet hebben van $\Omega(\sqrt{\log c})$, waarbij $c$ het aantal labels is. Dit lost een open vraag van Pabbaraju [2024] op over de vraag of de compressiegrootte moet groeien met het aantal labels.

3. Belangrijkste Resultaten

1. Optimale Onambiguïteit van DNFs (Theorem 1): Bestaan van onambiguïteit DNFs met $UC_1(f) = O(n)$ en $C_0(f) = \Omega(n^2)$.
2. Constant-Gadget Lifting (Theorem 2): Een lifting theorem met behulp van een 3-bit cyclisch gadget dat de certificaatcomplexiteit scheiding naar een communicatiecomplexiteit scheiding lift met $\log \text{Cov}_0(h) = \Omega(n^2)$.
3. Optimale Weerlegging van Alon-Saks-Seymour (Theorem 3): Bestaan van een graaffamilie met $bp(G) = 2^{O(n)}$ en $\chi(G) = 2^{\Omega(n^2)}$, voldoend aan $\chi(G) \ge \exp(\Omega(\log^2 bp(G)))$. Dit komt overeen met de bekende bovengrenzen tot aan constanten in de exponent.
4. Optimale CIS Ondergrens (Corollary 1.3): Bestaan van een Clique versus Independent Set probleem met co-nondeterministische communicatiecomplexiteit $\Omega(\log^2 n)$, wat overeenkomt met de boven grens van Yannakakis.
5. Quartische Scheiding (Theorem 4): Bestaan van Booleaanse functies met $C(f) \ge \exp(\Omega(\tilde{\deg}(f)^4))$.
6. Sample Compression Ondergrens (Theorem 5): Voor multiclass concept classes met Natarajan dimensie 1, is de sample compression grootte $\Omega(\sqrt{\log c})$.

4. Betekenis en Claims

Het artikel claimt optimale oplossingen te bieden voor de drie puzzels geponeerd door Balodis et al. [2023], waarbij de polylogaritmische factoren die voorheen de nauwkeurigheid van deze scheidingen beperkten, volledig worden geëlimineerd.

• Alon-Saks-Seymour: Het resultaat biedt de sterkst mogelijke weerlegging van de conjectuur, waarbij laat zien dat de kloof tussen het kromingsgetal en het biclique partitiegetal exponentieel is in het kwadraat van het logaritme van het biclique partitiegetal. De auteur merkt op dat de grootte van de geconstrueerde grafen zelf optimaal is tot aan constante factoren in de exponent, aangezien een graaf met kromingsgetal $\chi$ minstens $\chi$ knopen moet hebben.
• Communicatiecomplexiteit: Het werk vestigt de eerste optimale ondergrens voor het Clique versus Independent Set probleem, die de langdurige boven grens van Yannakakis evenaart.
• Leertheorie: Het sample compression resultaat toont aan dat zelfs voor klassen met een lage Natarajan dimensie, het aantal labels een polylogaritmische groei in de vereiste sample compression grootte kan afdwingen, wat de open vraag van Pabbaraju [2024] gedeeltelijk oplost.

De auteur benadrukt dat het constant-gadget lifting theorem een cruciale technische innovatie is. Hoewel algemene lifting theorems bestaan, vereisen zij doorgaans gadgets van grootte $\Theta(\log n)$, wat de dubbel logaritmische factoren in de uiteindelijke grenzen introduceert. Door de specifieke structuur van de geconstrueerde onambiguïteit DNFs te exploiteren, leidt de auteur een lifting theorem af dat werkt met een constant-grootte gadget, waardoor de laatste resterende logaritmische factoren worden "afgeschoren".

Het artikel claimt niet de algemene log-rank conjectuur op te lossen, maar merkt wel op dat hun resultaat de bekende kwadratische ondergrens voor de log-rank conjectuur verbetert door polylogaritmische factoren te verwijderen. Eveneens, hoewel de sample compression ondergrens $\Omega(\sqrt{\log c})$ is, erkent de auteur dat dit een gedeeltelijke oplossing is voor de vraag of de grens moet groeien met $c$, aangezien de bovengrens polynomiaal is in $c$.