Local enumeration and majority lower bounds

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F24%3A00588526" target="_blank" >RIV/67985840:_____/24:00588526 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.4230/LIPIcs.CCC.2024.17" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.CCC.2024.17</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.CCC.2024.17" target="_blank" >10.4230/LIPIcs.CCC.2024.17</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Local enumeration and majority lower bounds

Popis výsledku v původním jazyce

Depth-3 circuit lower bounds and k-SAT algorithms are intimately related, the state-of-the-art Σk3 -circuit lower bound (Or-And-Or circuits with bottom fan-in at most k) and the k-SAT algorithm of Paturi, Pudlák, Saks, and Zane (J. ACM’05) are based on the same combinatorial theorem regarding k-CNFs. In this paper we define a problem which reveals new interactions between the two, and suggests a concrete approach to significantly stronger circuit lower bounds and improved k-SAT algorithms. For a natural number k and a parameter t, we consider the Enum(k, t) problem defined as follows: given an n-variable k-CNF and an initial assignment α, output all satisfying assignments at Hamming distance t(n) of α, assuming that there are no satisfying assignments of Hamming distance less than t(n) of α. We observe that an upper bound b(n, k, t) on the complexity of Enum(k, t) simultaneously implies depth-3 circuit lower bounds and k-SAT algorithms: Depth-3 circuits: Any Σk3 circuit computing the Majority function has size at least (nn2 )/b(n, k, n2 ). k-SAT: There exists an algorithm solving k-SAT in time O (Pn/t=12 b(n, k, t) ) . A simple construction shows that b(n, k, n2 ) ≥ 2(1−O(log(k)/k))n. Thus, matching upper bounds for b(n, k, n2 ) would imply a Σk3 -circuit lower bound of 2Ω(log(k)n/k) and a k-SAT _upper bound of 2(1−Ω(log(k)/k))n. The former yields an unrestricted depth-3 lower bound of 2ω(√n) solving a long standing open problem, and the latter breaks the Super Strong Exponential Time Hypothesis. In this paper, we propose a randomized algorithm for Enum(k, t) and introduce new ideas to analyze it. We demonstrate the power of our ideas by considering the first non-trivial instance of the problem, i.e., Enum(3, n2 ). We show that the expected running time of our algorithm is 1.598n, substantially improving on the trivial bound of 3n/2 ≃ 1.732n. This already improves Σ33 lower bounds for Majority function to 1.251n. The previous bound was 1.154n which follows from the work of Håstad, Jukna, and Pudlák (Comput. Complex.’95). By restricting ourselves to monotone CNFs, Enum(k, t) immediately becomes a hypergraph Turán problem. Therefore our techniques might be of independent interest in extremal combinatorics.

Název v anglickém jazyce

Local enumeration and majority lower bounds

Popis výsledku anglicky

Depth-3 circuit lower bounds and k-SAT algorithms are intimately related, the state-of-the-art Σk3 -circuit lower bound (Or-And-Or circuits with bottom fan-in at most k) and the k-SAT algorithm of Paturi, Pudlák, Saks, and Zane (J. ACM’05) are based on the same combinatorial theorem regarding k-CNFs. In this paper we define a problem which reveals new interactions between the two, and suggests a concrete approach to significantly stronger circuit lower bounds and improved k-SAT algorithms. For a natural number k and a parameter t, we consider the Enum(k, t) problem defined as follows: given an n-variable k-CNF and an initial assignment α, output all satisfying assignments at Hamming distance t(n) of α, assuming that there are no satisfying assignments of Hamming distance less than t(n) of α. We observe that an upper bound b(n, k, t) on the complexity of Enum(k, t) simultaneously implies depth-3 circuit lower bounds and k-SAT algorithms: Depth-3 circuits: Any Σk3 circuit computing the Majority function has size at least (nn2 )/b(n, k, n2 ). k-SAT: There exists an algorithm solving k-SAT in time O (Pn/t=12 b(n, k, t) ) . A simple construction shows that b(n, k, n2 ) ≥ 2(1−O(log(k)/k))n. Thus, matching upper bounds for b(n, k, n2 ) would imply a Σk3 -circuit lower bound of 2Ω(log(k)n/k) and a k-SAT _upper bound of 2(1−Ω(log(k)/k))n. The former yields an unrestricted depth-3 lower bound of 2ω(√n) solving a long standing open problem, and the latter breaks the Super Strong Exponential Time Hypothesis. In this paper, we propose a randomized algorithm for Enum(k, t) and introduce new ideas to analyze it. We demonstrate the power of our ideas by considering the first non-trivial instance of the problem, i.e., Enum(3, n2 ). We show that the expected running time of our algorithm is 1.598n, substantially improving on the trivial bound of 3n/2 ≃ 1.732n. This already improves Σ33 lower bounds for Majority function to 1.251n. The previous bound was 1.154n which follows from the work of Håstad, Jukna, and Pudlák (Comput. Complex.’95). By restricting ourselves to monotone CNFs, Enum(k, t) immediately becomes a hypergraph Turán problem. Therefore our techniques might be of independent interest in extremal combinatorics.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GX19-27871X" target="_blank" >GX19-27871X: Efektivní aproximační algoritmy a obvodová složitost</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

39th Computational Complexity Conference (CCC 2024)

ISBN

978-3-95977-331-7

ISSN

1868-8969

e-ISSN

1868-8969

Počet stran výsledku

25

Strana od-do

17

Název nakladatele

Schloss Dagstuhl, Leibniz-Zentrum für Informatik

Místo vydání

Dagstuhl

Místo konání akce

Ann Arbor

Datum konání akce

22. 7. 2024

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—