Document

**Published in:** LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Depth-3 circuit lower bounds and k-SAT algorithms are intimately related; the state-of-the-art Σ^k_3-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 Σ^k_3 circuit computing the Majority function has size at least binom(n,n/2)/b(n, k, n/2).
- k-SAT: There exists an algorithm solving k-SAT in time O(∑_{t=1}^{n/2}b(n, k, t)).
A simple construction shows that b(n, k, n/2) ≥ 2^{(1 - O(log(k)/k))n}. Thus, matching upper bounds for b(n, k, n/2) would imply a Σ^k_3-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, n/2). We show that the expected running time of our algorithm is 1.598ⁿ, substantially improving on the trivial bound of 3^{n/2} ≃ 1.732ⁿ. This already improves Σ^3_3 lower bounds for Majority function to 1.251ⁿ. The previous bound was 1.154ⁿ 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.

Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák, Michael Saks, and Navid Talebanfard. Local Enumeration and Majority Lower Bounds. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 17:1-17:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gurumukhani_et_al:LIPIcs.CCC.2024.17, author = {Gurumukhani, Mohit and Paturi, Ramamohan and Pudl\'{a}k, Pavel and Saks, Michael and Talebanfard, Navid}, title = {{Local Enumeration and Majority Lower Bounds}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {17:1--17:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.17}, URN = {urn:nbn:de:0030-drops-204136}, doi = {10.4230/LIPIcs.CCC.2024.17}, annote = {Keywords: Depth 3 circuits, k-CNF satisfiability, Circuit lower bounds, Majority function} }

Document

**Published in:** LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

In this paper, we investigate the complexity of one-dimensional dynamic programming, or more specifically, of the Least-Weight Subsequence (LWS) problem: Given a sequence of n data items together with weights for every pair of the items, the task is to determine a subsequence S minimizing the total weight of the pairs adjacent in S. A large number of natural problems can be formulated as LWS problems, yielding obvious O(n^2)-time solutions.
In many interesting instances, the O(n^2)-many weights can be succinctly represented. Yet except for near-linear time algorithms for some specific special cases, little is known about when an LWS instantiation admits a subquadratic-time algorithm and when it does not. In particular, no lower bounds for LWS instantiations have been known before. In an attempt to remedy this situation, we provide a general approach to study the fine-grained complexity of succinct instantiations of the LWS problem: Given an LWS instantiation we identify a highly parallel core problem that is subquadratically equivalent. This provides either an explanation for the apparent hardness of the problem or an avenue to find improved algorithms as the case may be.
More specifically, we prove subquadratic equivalences between the following pairs (an LWS instantiation and the corresponding core problem) of problems: a low-rank version of LWS and minimum inner product, finding the longest chain of nested boxes and vector domination, and a coin change problem which is closely related to the knapsack problem and (min,+)-convolution. Using these equivalences and known SETH-hardness results for some of the core problems, we deduce tight conditional lower bounds for the corresponding LWS instantiations. We also establish the (min,+)-convolution-hardness of the knapsack problem. Furthermore, we revisit some of the LWS instantiations which are known to be solvable in near-linear time and explain their easiness in terms of the easiness of the corresponding core problems.

Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider. On the Fine-Grained Complexity of One-Dimensional Dynamic Programming. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kunnemann_et_al:LIPIcs.ICALP.2017.21, author = {K\"{u}nnemann, Marvin and Paturi, Ramamohan and Schneider, Stefan}, title = {{On the Fine-Grained Complexity of One-Dimensional Dynamic Programming}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {21:1--21:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.21}, URN = {urn:nbn:de:0030-drops-74688}, doi = {10.4230/LIPIcs.ICALP.2017.21}, annote = {Keywords: Least-Weight Subsequence, SETH, Fine-Grained Complexity, Knapsack, Subquadratic Algorithms} }

Document

**Published in:** Dagstuhl Reports, Volume 3, Issue 8 (2013)

This report documents the program and the outcomes of Dagstuhl Seminar
13331 "Exponential Algorithms: Algorithms and Complexity Beyond
Polynomial Time". Problems are often solved in practice by algorithms with worst-case exponential time complexity. It is of interest to find the fastest algorithms for a given problem, be it polynomial, exponential, or something in between. The focus of the Seminar is on finer-grained notions of complexity
than np-completeness and on understanding the exact complexities of problems.
The report provides a rationale for the workshop and chronicles the presentations at the workshop. The report notes the progress on the open problems posed at the past workshops on the same topic. It also reports a collection of results that cite the presentations at the previous seminar. The docoument presents the collection of the abstracts of the results presented
at the Seminar. It also presents a compendium of open problems.

Thore Husfeldt, Ramamohan Paturi, Gregory B. Sorkin, and Ryan Williams. Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331). In Dagstuhl Reports, Volume 3, Issue 8, pp. 40-72, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{husfeldt_et_al:DagRep.3.8.40, author = {Husfeldt, Thore and Paturi, Ramamohan and Sorkin, Gregory B. and Williams, Ryan}, title = {{Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331)}}, pages = {40--72}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2013}, volume = {3}, number = {8}, editor = {Husfeldt, Thore and Paturi, Ramamohan and Sorkin, Gregory B. and Williams, Ryan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.8.40}, URN = {urn:nbn:de:0030-drops-43422}, doi = {10.4230/DagRep.3.8.40}, annote = {Keywords: Algorithms, exponential time algorithms, exact algorithms, computational complexity, satisfiability} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 10441, Exact Complexity of NP-hard Problems (2011)

A decade before NP-completeness became the
lens through which Computer Science views computationally hard
problems, beautiful algorithms were discovered that are much better
than exhaustive search, for example
Bellman's 1962 dynamic programming treatment of the Traveling Salesman problem
and Ryser's 1963 inclusion--exclusion formula for the permanent.

Thore Husfeldt, Dieter Kratsch, Ramamohan Paturi, and Gregory B. Sorkin. 10441 Abstracts Collection – Exact Complexity of NP-hard Problems. In Exact Complexity of NP-hard Problems. Dagstuhl Seminar Proceedings, Volume 10441, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{husfeldt_et_al:DagSemProc.10441.1, author = {Husfeldt, Thore and Kratsch, Dieter and Paturi, Ramamohan and Sorkin, Gregory B.}, title = {{10441 Abstracts Collection – Exact Complexity of NP-hard Problems}}, booktitle = {Exact Complexity of NP-hard Problems}, pages = {1--22}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2011}, volume = {10441}, editor = {Thore Husfeldt and Dieter Kratsch and Ramamohan Paturi and Gregory B. Sorkin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10441.1}, URN = {urn:nbn:de:0030-drops-29363}, doi = {10.4230/DagSemProc.10441.1}, annote = {Keywords: Complexity, Algorithms, NP-hard Problems, Exponential Time, SAT, Graphs} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail