Proving complexity lower bounds remains a challenging task: currently, we only know how to prove conditional uniform (algorithm) lower bounds and nonuniform (circuit) lower bounds in restricted circuit models. About a decade ago, Williams (STOC 2010) showed how to derive nonuniform lower bounds from uniform upper bounds: roughly, by designing a fast algorithm for checking satisfiability of circuits, one gets a lower bound for this circuit class. Since then, a number of results of this kind have been proved. For example, Jahanjou et al. (ICALP 2015) and Carmosino et al. (ITCS 2016) proved that if NSETH fails, then E^{NP} has series-parallel circuit size ω(n). One can also derive nonuniform lower bounds from nondeterministic uniform lower bounds. Perhaps the most well-known example is the Karp-Lipton theorem (STOC 1980): if Σ₂ ≠ Π₂, then NP ⊄ P/poly. Some recent examples include the following. Nederlof (STOC 2020) proved a lower bound on the matrix multiplication tensor rank under an assumption that TSP cannot be solved faster than in 2ⁿ time. Belova et al. (SODA 2024) proved that there exists an explicit polynomial family of arithmetic circuit size Ω(n^{δ}), for any δ > 0, assuming that MAX-3-SAT cannot be solved faster than in 2ⁿ nondeterministic time. Williams (FOCS 2024) proved an exponential lower bound for ETHR ∘ ETHR circuits under the Orthogonal Vectors conjecture. Whereas all the lower bounds above are proved under strong assumptions that might eventually be refuted, the revealed connections are of great interest and may still give further insights: one may be able to weaken the used assumptions or to construct generators from other fine-grained reductions. In this paper, we continue developing this line of research and show how uniform nondeterministic lower bounds can be used to construct generators of various types of combinatorial objects that are notoriously hard to analyze: Boolean functions of high circuit size, matrices of high rigidity, and tensors of high rank. Specifically, we prove the following. - If, for some ε and k, k-SAT cannot be solved in input-oblivious co-nondeterministic time O(2^{(1/2+ε)n}), then there exists a monotone Boolean function family in coNP of monotone circuit size 2^{Ω(n / log n)}. Combining this with the result above, we get win-win circuit lower bounds: either E^{NP{}} requires series-parallel circuits of size ω(n) or coNP requires monotone circuits of size 2^{Ω(n / log n)}. - If, for all ε > 0, MAX-3-SAT cannot be solved in co-nondeterministic time O(2^{(1 - ε)n}), then there exist small families of matrices with rigidity exceeding the best known constructions as well as small families of three-dimensional tensors of rank n^{1+Δ}, for some Δ > 0.

The Strong Exponential Time Hypothesis (SETH) asserts that for every \(\varepsilon > 0\) there exists k such that k -SAT requires time \((2-\varepsilon)^{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 article, 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).

More than 40 years ago, Schroeppel and Shamir presented an algorithm that solves the Subset Sum problem for $n$ integers in time $O^*(2^{0.5n})$ and space $O^*(2^{0.25n})$. The time upper bound remains unbeaten, but the space upper bound has been improved to $O^*(2^{0.249999n})$ in a recent breakthrough paper by Nederlof and Węgrzycki (STOC 2021). Their algorithm is a clever combination of a number of previously known techniques with a new reduction and a new algorithm for the Orthogonal Vectors problem. In this paper, we improve the space bound by Nederlof and Węgrzycki to $O^*(2^{0.246n})$ and also simplify their algorithm and its analysis. We achieve this by using an idea, due to Howgrave-Graham and Joux, of using a random prime number to filter the family of subsets. We incorporate it into the algorithm by Schroeppel and Shamir and then use this amalgam inside the representation technique. This allows us to reduce an instance of Subset Sum to a larger number of instances of weighted orthogonal vector.

The field of fine-grained complexity aims at proving conditional lower bounds on the time complexity of computational problems. One of the most popular and successfully used assumptions, Strong Exponential Time Hypothesis (SETH), implies that SAT cannot be solved in 2(1-ɛ)n time. In recent years, it has been proved that known algorithms for many problems are optimal under SETH. Despite the wide applicability of SETH, for many problems, there are no known SETH-based lower bounds, so the quest for new reductions continues.

The Strong Exponential Time Hypothesis (SETH) asserts that for every ε > 0 there exists k such that k-SAT requires time (2 — ε)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 λn-hardness of these problems from SETH for any λ > 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 λ > 1, we conditionally rule out fine-grained reductions implying SETH-based lower bounds of λ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). * The full version of the paper can be accessed at https://arxiv.org/abs/2205.07709

The minimum number of clauses in a CNF representation of the parity function x₁ ⊕ x₂ ⊕ … ⊕ x_n is 2^{n-1}. One can obtain a more compact CNF encoding by using non-deterministic variables (also known as guess or auxiliary variables). In this paper, we prove the following lower bounds, that almost match known upper bounds, on the number m of clauses and the maximum width k of clauses: 1) if there are at most s auxiliary variables, then m ≥ Ω(2^{n/(s+1)}/n) and k ≥ n/(s+1); 2) the minimum number of clauses is at least 3n. We derive the first two bounds from the Satisfiability Coding Lemma due to Paturi, Pudlák, and Zane using a tight connection between CNF encodings and depth-3 circuits. In particular, we show that lower bounds on the size of a CNF encoding of a Boolean function imply depth-3 circuit lower bounds for this function.

In this paper, we propose a new conjecture, the XOR-KRW conjecture, which is a relaxation of the Karchmer-Raz-Wigderson conjecture [Mauricio Karchmer et al., 1995]. This relaxation is still strong enough to imply 𝐏 ̸ ⊆ NC¹ if proven. We also present a weaker version of this conjecture that might be used for breaking n³ lower bound for De Morgan formulas. Our study of this conjecture allows us to partially answer an open question stated in [Dmitry Gavinsky et al., 2017] regarding the composition of the universal relation with a function. To be more precise, we prove that there exists a function g such that the composition of the universal relation with g is significantly harder than just a universal relation. The fact that we can only prove the existence of g is an inherent feature of our approach. The paper’s main technical contribution is a new approach to lower bounds for multiplexer-type relations based on the non-deterministic hardness of non-equality and a new method of converting lower bounds for multiplexer-type relations into lower bounds against some function. In order to do this, we develop techniques to lower bound communication complexity in half-duplex and partially half-duplex communication models.

We prove that the Hadwiger number of an $n$-vertex graph $G$ (the maximum size of a clique minor in $G$) cannot be computed in time $n^{o(n)}$, unless the Exponential Time Hypothesis (ETH) fails. This resolves a well-known open question in the area of exact exponential algorithms. The technique developed for resolving the Hadwiger number problem has a wider applicability. We use it to rule out the existence of $n^{o(n)}$-time algorithms (up to ETH) for a large class of computational problems concerning edge contractions in graphs.

In the Shortest Common Superstring (SCS) problem, one is given a collection of strings, and needs to find a shortest string containing each of them as a substring. SCS admits $2\frac{11}{23}$-approximation in polynomial time (Mucha, SODA'13). While this algorithm and its analysis are technically involved, the 30 years old Greedy Conjecture claims that the trivial and efficient Greedy Algorithm gives a 2-approximation for SCS. We develop a graph-theoretic framework for studying approximation algorithms for SCS. The framework is reminiscent of the classical 2-approximation for Traveling Salesman: take two copies of an optimal solution, apply a trivial edge-collapsing procedure, and get an approximate solution. In this framework, we observe two surprising properties of SCS solutions, and we conjecture that they hold for all input instances. The first conjecture, that we call Collapsing Superstring conjecture, claims that there is an elementary way to transform any solution repeated twice into the same graph $G$. This conjecture would give an elementary 2-approximate algorithm for SCS. The second conjecture claims that not only the resulting graph $G$ is the same for all solutions, but that $G$ can be computed by an elementary greedy procedure called Greedy Hierarchical Algorithm. While the second conjecture clearly implies the first one, perhaps surprisingly we prove their equivalence. We support these equivalent conjectures by giving a proof for the special case where all input strings have length at most 3. We prove that the standard Greedy Conjecture implies Greedy Hierarchical Conjecture, while the latter is sufficient for an efficient greedy 2-approximate approximation of SCS. Except for its (conjectured) good approximation ratio, the Greedy Hierarchical Algorithm provably finds a 3.5-approximation.

We show that proving mildly super-linear lower bounds on non-commutative arithmetic circuits implies exponential lower bounds on non-commutative circuits. That is, non-commutative circuit complexity is a threshold phenomenon: an apparently weak lower bound actually suffices to show the strongest lower bounds we could desire. This is part of a recent line of inquiry into why arithmetic circuit complexity, despite being a heavily restricted version of Boolean complexity, still cannot prove super-linear lower bounds on general devices. One can view our work as positive news (it suffices to prove weak lower bounds to get strong ones) or negative news (it is as hard to prove weak lower bounds as it is to prove strong ones). We leave it to the reader to determine their own level of optimism.

Suppose Alice and Bob are communicating in order to compute some function f, but instead of a classical communication channel they have a pair of walkie-talkie devices. They can use some classical communication protocol for f where in each round one player sends a bit and the other one receives it. The question is whether talking via walkie-talkie gives them more power? Using walkie-talkies instead of a classical communication channel allows players two extra possibilities: to speak simultaneously (but in this case they do not hear each other) and to listen at the same time (but in this case they do not transfer any bits). The motivation for this kind of a communication model comes from the study of the KRW conjecture. We show that for some definitions this non-classical communication model is, in fact, more powerful than the classical one as it allows to compute some functions in a smaller number of rounds. We also prove lower bounds for these models using both combinatorial and information theoretic methods.

We prove that unless the Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph G to graph H cannot be done in time | V ( H )| o (| V ( G )|) . We also show an exponential-time reduction from Graph Homomorphism to Subgraph Isomorphism. This rules out (subject to ETH) a possibility of | V ( H )| o (| V ( H )|) -time algorithm deciding if graph G is a subgraph of H . For both problems our lower bounds asymptotically match the running time of brute-force algorithms trying all possible mappings of one graph into another. Thus, our work closes the gap in the known complexity of these fundamental problems. Moreover, as a consequence of our reductions, conditional lower bounds follow for other related problems such as Locally Injective Homomorphism, Graph Minors, Topological Graph Minors, Minimum Distortion Embedding and Quadratic Assignment Problem.

We introduce the Nondeterministic Strong Exponential Time Hypothesis (NSETH) as a natural extension of the Strong Exponential Time Hypothesis (SETH). We show that both refuting and proving NSETH would have interesting consequences.

We prove that unless Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph G to graph H cannot be done in time |V (H)|o(|V (G)|). We also show an exponential-time reduction from Graph Homomorphism to Subgraph Isomorphism. This rules out (subject to ETH) a possibility of |V (H)|o(|V (H)|)-time algorithm deciding if graph G is a subgraph of H. For both problems our lower bounds asymptotically match the running time of brute-force algorithms trying all possible mappings of one graph into another. Thus, our work closes the gap in the known complexity of these fundamental problems.

Assume that a group of n people is going to an excursion and our task is to seat them into buses with several constraints each saying that a pair of people does not want to see each other in the same bus. This is a well-known graph coloring problem (with n being the number of vertices) and it can be solved in O *(2 n ) time by the inclusion-exclusion principle as shown by Björklund, Husfeldt, and Koivisto in 2009. Another approach to solve this problem in O *(2 n ) time is to use the Fast Fourier Transform (FFT). For this, given a graph G one constructs a polynomial P G ( x ) of degree O *(2 n ) with the following property: G is k -colorable if and only if the coefficient of x m (for some particular value of m ) in the k -th power of P ( x ) is nonzero. Then, it remains to compute this coefficient using FFT. Assume now that we have additional constraints: the group of people contains several infants and these infants should be accompanied by their relatives in a bus. We show that if the number of infants is linear, then the problem can be solved in O *((2 − ε) n ) time, where ε is a positive constant independent of n . We use this approach to improve known bounds for several NP-hard problems (the traveling salesman problem, the graph coloring problem, the problem of counting perfect matchings) on graphs of bounded average degree, as well as to simplify the proofs of several known results.