Local enumeration and majority lower bounds

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Local enumeration and majority lower bounds

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

<a href="/en/project/GX19-27871X" target="_blank" >GX19-27871X: Efficient approximation algorithms and circuit complexity</a><br>

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2024

Confidentiality

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

Article name in the collection

39th Computational Complexity Conference (CCC 2024)

ISBN

978-3-95977-331-7

ISSN

1868-8969

e-ISSN

1868-8969

Number of pages

25

Pages from-to

17

Publisher name

Schloss Dagstuhl, Leibniz-Zentrum für Informatik

Place of publication

Dagstuhl

Event location

Ann Arbor

Event date

Jul 22, 2024

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—