Computational Complexity of Discrete Problems

We prove that polynomial calculus and hence also Nullstellensatz requires linear degree to refute that sparse random regular graphs, as well as sparse Erdös-Rényi random graphs, are 3-colourable. Using the known relation between size and degree for polynomial calculus proofs, this implies strongly exponential lower bounds on proof size.

A tree-like Resolution refutation of a CNF is a decision tree that solves the falsified clause search problem. We can think of the leaves of the decision tree as a partition of the space of truth assignments into “monochromatic” subcubes, in the sense that each subcube can be associated with a single refuted clause. A HITTING refutation of a CNF is any partition of the space of truth assignments into monochromatic subcubes.

We explore the relation between HITTING and other proof systems. By construction, HITTING p-simulates tree-like Resolution, and in contrast, tree-like Resolution qp-simulates HITTING, and there is a qp-separation between the two systems. Resolution can be exponentially more powerful than HITTING, but we conjecture that it does not p-simulate HITTING. Using the Raz-Shpilka PIT, we show that Extended Resolution p-simulates HITTING, though this is probably an overkill.

We present a top-down lower-bound method for depth-$4$ boolean circuits. In particular, we give a new proof of the well-known result that the parity function requires depth-$4$ circuits of size exponential in $n^{1/3}$. Our proof is an application of robust sunflowers and block unpredictability.

We present the first characterization of a one-way function by worst-case hardness assumptions: A one-way function exists iff NP is hard in the worst case and “distributional Kolmogorov complexity” is NP-hard under randomized reductions. Here, the $t$-time bounded distributional Kolmogorov complexity of a string $x$ given a distribution D is defined to be the length of a shortest $t$-time program that outputs $x$ given as input $y$ drawn from the distribution D with high probability. The characterization suggests that the recent approaches of using meta-complexity to exclude Heuristica and Pessiland are both sufficient and necessary.

While there has been progress in establishing the unprovability of complexity statements in lower fragments of bounded arithmetic, understanding the limits of Jeřábek’s theory $AP{C}_1$ (2007) and of higher levels of Buss’s hierarchy $S_2^i$ (1986) has been a more elusive task. Even in the more restricted setting of Cook’s theory $P{V}_1$ (1975), known results often rely on a less natural formalization that encodes a complexity statement using a collection of sentences instead of a single sentence. This is done to reduce the quantifier complexity of the resulting sentences so that standard witnessing results can be invoked.

In this work, we establish unprovability results for stronger theories and for sentences of higher quantifier complexity. In particular, we unconditionally show that $AP{C}_1$ cannot prove strong complexity lower bounds separating the third level of the polynomial hierarchy. In more detail, the lower bound sentence refers to the non-uniform setting ($\exists \forall \exists$ Circuits vs. $\forall \exists \forall$ Circuits) and to a mild average-case lower bound for polynomial size circuits against sub-exponential size circuits.

Our argument employs a convenient game-theoretic witnessing result that can be applied to sentences of arbitrary quantifier complexity. We combine it with extensions of a technique introduced by Krajíček (2011) that was recently employed by Pich and Santhanam (2021) to establish the unprovability of lower bounds in $P{V}_1$ and in a fragment of $AP{C}_1$.

We study Frege proofs for the one-to-one graph Pigeon Hole Principle defined on the $n\times n$ grid where $n$ is odd. We are interested in the case where each formula in the proof is a depth $d$ formula in the basis given by $\wedge$, $\vee$, and $\neg$. We prove that in this situation the proof needs to be of size exponential in $n^{\mathrm{\Omega }(1/d)}$. If we restrict the size of each line in the proof to be of size $M$ then the number of lines needed is exponential in $n/{(\log M)}^{O(d)}$. The main technical component of the proofs is to design a new family of random restrictions and to prove the appropriate switching lemmas.

This is based on the papers ECFFT I (Fast algorithms for polynomials over all fields) and ECFFT II (Scalable and Transparent proofs over all large fields), both joint work with Eli Ben-Sasson, Dan Carmon, and David Levit

I will talk about a variant (the ECFFT) of the FFT which is based on elliptic-curve groups in place of multiplicative groups. While the classical FFT over finite fields is directly applicable only when the size of the multiplicative group of the field is special, the ECFFT turns out to be directly applicable over all finite fields (because all finite fields have some elliptic curve group whose size is special).

We then use the ECFFT in place of the FFT for applications in fast polynomial algorithms and interactive property testing.

We present a new locally consistent decomposition of strings. Each string $x$ is decomposed into blocks that can be described by grammars of size $\tilde{O}(k)$ (using some amount of randomness). If we take two strings $x$ and $y$ of edit distance at most $k$ then their block decomposition uses the same number of grammars and the $i$-th grammar of $x$ is the same as the $i$-th grammar of $y$ except for at most $k$ indexes $i$. The edit distance of $x$ and $y$ equals to the sum of edit distances of pairs of blocks where $x$ and $y$ differ. Our decomposition can be used to design a sketch of size $\tilde{O}(k^2)$ for edit distance, and also a rolling sketch for edit distance of size $\tilde{O}(k^2)$. The rolling sketch allows to update the sketched string by appending a symbol or removing a symbol from the beginning of the string.

The Strong Exponential Time Hypothesis (SETH) asserts that for every $\epsilon >0$ there exists $k$ such that $k$-SAT requires time ${(2-\epsilon )}^n$. The field of fine-grained complexity has leveraged SETH to prove quite tight conditional lower bounds for dozens of problems in various domains and complexity classes, including Edit Distance, Graph Diameter, Hitting Set, Independent Set, and Orthogonal Vectors. Yet, it has been repeatedly asked in the literature whether SETH-hardness results can be proven for other fundamental problems such as Hamiltonian Path, Independent Set, Chromatic Number, MAX-$k$-SAT, and Set Cover.

In this paper, we show that fine-grained reductions implying even ${\lambda }^n$-hardness of these problems from SETH for any $\lambda >1$, would imply new circuit lower bounds: super-linear lower bounds for Boolean series-parallel circuits or polynomial lower bounds for arithmetic circuits (each of which is a four-decade open question).

We also extend this barrier result to the class of parameterized problems. Namely, for every $\lambda >1$, we conditionally rule out fine-grained reductions implying SETH-based lower bounds of ${\lambda }^k$ for a number of problems parameterized by the solution size $k$.

Our main technical tool is a new concept called polynomial formulations. In particular, we show that many problems can be represented by relatively succinct low-degree polynomials, and that any problem with such a representation cannot be proven SETH-hard (without proving new circuit lower bounds).

Recent work in proof complexity has shown that studying many of the major proof systems studied in practice is, in a sense, completely equivalent to studying black-box versions of syntactically-defined subclasses of TFNP. Many weak proof systems, such as Resolution, Sherali-Adams, and Nullstellensatz are now known to admit characterizations of this type, and these new characterizations have been used to obtain new results in both proof complexity and the study of TFNP.

In this talk, we outline recent work in which we have characterized stronger proof systems – including $Res(k)$ and higher-depth analogues of Sherali-Adams – inside of TFNP by using the so-called “coloured” generalization of standard TFNP classes. This talk is based on joint work with Ben Davis.

The edit distance between two strings, equal to the minimum number of operations (insertions, deletions or substitutions) needed to transform one to the other, is a standard measure of similarity of strings. The classic dynamic programming algorithm for edit distance requires time quadratic in n to compute the edit distance between two strings of length n, and there is evidence (via the strong exponential time hypothesis) that it may be impossible to improve substantially on this time complexity.

Recently, there has been considerable progress in developing approximation algorithms for edit distance (and the more general problem of Dyck edit distance) that are fast and have constant, or near constant approximation factors. These algorithms run in near linear time, but are logically complex, and the constants in both the running time and the approximation factor are huge, making the algorithms impractical.

In this work, we seek algorithms with weaker but still useful approximation guarantees that are practical: simple, fast and space efficient. We introduce a class of algorithms called single pass algorithms. In such an algorithm we maintain a single pointer within each string, starting at the left. In each step, if the current symbols match we advance both pointers, otherwise we have a mismatch and choose one of the pointers to advance. Such an algorithm is specified by its advancement rule, which determines which pointer to advance. We consider particularly simple (possibly randomized) advancement rules where at each mismatch step the pointer advanced depends only on the number of mismatches seen so far and the randomness of the algorithm. It is easy to see that the total number of mismatches is always an upper bound on edit distance. Saha (2014) showed that the simple randomized rule (on mismatch advance a pointer at random) when run on two strings of edit distance d returns (with high probability) an upper bound of $O(d^2)$.

In this work we (1) present a deterministic single pass algorithm that achieves similar performance and (2) prove that no algorithm (even randomized) in this class can give a better approximation factor.

For the Dyck edit distance problem, Saha gave a complicated randomized reduction from Dyck edit distance to standard edit distance at a cost of a $O(\log d)$ factor where $d$ is the Dyck edit distance. I will present a simple deterministic reduction with a similar (slightly better) approximation guarantee.

More than twenty years ago, Capalbo, Reingold, Vadhan, and Wigderson gave the first (and up-to-date only) explicit construction of a bipartite expander with almost full combinatorial expansion. The construction incorporates zig-zag ideas and extractor technology and is rather complicated. We give an alternative construction that builds upon recent constructions of hyper-regular, high-dimensional expanders. The new construction is, in our opinion, simple and elegant.

Beyond demonstrating a new, surprising, and intriguing, application of high-dimensional expanders, the construction employs totally new ideas which we hope may lead to progress on the still remaining open problems in the area.

The width complexity measure plays a central role in Resolution and other propositional proof systems like Polynomial Calculus (under the name of degree). The study of width lower bounds is the most extended method for proving size lower bounds, and it is known that for these systems, proofs with small width also imply the existence of proofs with small size. Not much has been studied, however, about the width parameter in the Cutting Planes (CP) proof system, a measure that was introduced by Dantchev and Martin in 2011 under the name of CP cutwidth.

In this talk, we consider the width complexity of CP refutations of graph isomorphism formulas. For a pair of non-isomorphic graphs $G$ and $H$, we show a direct connection between the Weisfeiler–Leman differentiation number $\mathrm{𝖶𝖫}(G,H)$ of the graphs and the width of a CP refutation for the corresponding isomorphism formula $Iso(G,H)$. In particular, we show that if $\mathrm{𝖶𝖫}(G,H)\le k$, then there is a CP refutation of $Iso(G,H)$ with width $k$, and if $\mathrm{𝖶𝖫}(G,H)>k$, then there are no CP refutations of $Iso(G,H)$ with width $k-2$. Similar results are known for other proof systems, like Resolution, Sherali–Adams, or Polynomial Calculus. We also show polynomial-size CP refutations from our width bound for isomorphism formulas for graphs with constant WL.

Randomness extractors are tools for converting “low quality” randomness into “high quality” randomness. In addition to being useful in the areas of pseudorandomness and derandomization, these objects are also connected to various fundamental notions in complexity theory and mathematics in general. In this talk we’ll consider the randomness extraction problem from distributions with algebraic structure. We’ll survey the different types of algebraic sources and constructions, and talk about a recent construction of extractors for polynomial images of varieties