3SUM-Indexing is a preprocessing variant of the 3SUM problem that has recently received a lot of attention. The best known time-space tradeoff for the problem is T S³ = n⁶ (up to logarithmic factors), where n is the number of input integers, S is the length of the preprocessed data structure, and T is the running time of the query algorithm. This tradeoff was achieved in [Kopelowitz and Porat, 2019; Golovnev et al., 2020] using the Fiat-Naor generic algorithm for Function Inversion. Consequently, [Golovnev et al., 2020] asked whether this algorithm can be improved by leveraging the structure of 3SUM-Indexing. In this paper, we exploit the structure of 3SUM-Indexing to give a time-space tradeoff of T S = n^{2.5}, which is better than the best known one in the range n^{3/2} ≪ S ≪ n^{7/4}. We further extend this improvement to the kSUM-Indexing problem - a generalization of 3SUM-Indexing - and to the related kXOR-Indexing problem, where addition is replaced with XOR. Additionally, we improve the best known time-space tradeoffs for the Jumbled Indexing problem, which is a well-known data structure problem related to 3SUM-Indexing. Our improvement comes from an alternative way to apply the Fiat-Naor algorithm to 3SUM-Indexing. Specifically, we exploit the structure of the function to be inverted by decomposing it into "sub-functions" with certain properties. This allows us to apply an improvement to the Fiat-Naor algorithm (which is not directly applicable to 3SUM-Indexing), obtained in [Golovnev et al., 2023] in a much larger range of parameters. We believe that our techniques may be useful in additional application-dependent optimizations of the Fiat-Naor algorithm.

We prove new upper and lower bounds for the Online Orthogonal Vectors Problem (\(\text{OnlineOV}_{n,d}\)). In this problem, a preprocessing algorithm receives \(n\) vectors \(x_1, \ldots, x_n \in \{0,1\}^d\) and constructs a data structure of size \(S\). A query algorithm subsequently receives a query vector \(q \in \{0,1\}^d\) and in time \(T\) decides whether \(q\) is orthogonal to any of the input vectors \(x_i\).

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

In this note, we present examples showing that several natural ways of constructing lattices from error-correcting codes do not in general yield a correspondence between minimum-weight non-zero codewords and shortest non-zero lattice vectors. From these examples, we conclude that the main results in two works of Vlăduţ (Moscow J. Comb. Number Th., 2019 and Discrete Comput. Geom., 2021) on constructing lattices with exponential kissing number from error-correcting codes are invalid. A more recent preprint (arXiv, 2024) that Vlăduţ posted after an initial version of this work was made public is also invalid. Exhibiting a family of lattices with exponential kissing number therefore remains an open problem (as of July 2025).

We study the Matrix Multiplication Verification Problem (MMV) where the goal is, given three $n \times n$ matrices $A$, $B$, and $C$ as input, to decide whether $AB = C$. A classic randomized algorithm by Freivalds (MFCS, 1979) solves MMV in $\widetilde{O}(n^2)$ time, and a longstanding challenge is to (partially) derandomize it while still running in faster than matrix multiplication time (i.e., in $o(n^ω)$ time). To that end, we give two algorithms for MMV in the case where $AB - C$ is sparse. Specifically, when $AB - C$ has at most $O(n^δ)$ non-zero entries for a constant $0 \leq δ< 2$, we give (1) a deterministic $O(n^{ω- \varepsilon})$-time algorithm for constant $\varepsilon = \varepsilon(δ) > 0$, and (2) a randomized $\widetilde{O}(n^2)$-time algorithm using $δ/2 \cdot \log_2 n + O(1)$ random bits. The former algorithm is faster than the deterministic algorithm of Künnemann (ESA, 2018) when $δ\geq 1.056$, and the latter algorithm uses fewer random bits than the algorithm of Kimbrel and Sinha (IPL, 1993), which runs in the same time and uses $\log_2 n + O(1)$ random bits (in turn fewer than Freivalds's algorithm). We additionally study the complexity of MMV. We first show that all algorithms in a natural class of deterministic linear algebraic algorithms for MMV (including ours) require $Ω(n^ω)$ time. We also show a barrier to proving a super-quadratic running time lower bound for matrix multiplication (and hence MMV) under the Strong Exponential Time Hypothesis (SETH). Finally, we study relationships between natural variants and special cases of MMV (with respect to deterministic $\widetilde{O}(n^2)$-time reductions).

For S ⊆ 𝔽ⁿ, consider the linear space of restrictions of degree-d polynomials to S. The Hilbert function of S, denoted h_S(d,𝔽), is the dimension of this space. We obtain a tight lower bound on the smallest value of the Hilbert function of subsets S of arbitrary finite grids in 𝔽ⁿ with a fixed size |S|. We achieve this by proving that this value coincides with a combinatorial quantity, namely the smallest number of low Hamming weight points in a down-closed set of size |S|. Understanding the smallest values of Hilbert functions is closely related to the study of degree-d closure of sets, a notion introduced by Nie and Wang (Journal of Combinatorial Theory, Series A, 2015). We use bounds on the Hilbert function to obtain a tight bound on the size of degree-d closures of subsets of 𝔽_qⁿ, which answers a question posed by Doron, Ta-Shma, and Tell (Computational Complexity, 2022). We use the bounds on the Hilbert function and degree-d closure of sets to prove that a random low-degree polynomial is an extractor for samplable randomness sources. Most notably, we prove the existence of low-degree extractors and dispersers for sources generated by constant-degree polynomials and polynomial-size circuits. Until recently, even the existence of arbitrary deterministic extractors for such sources was not known.

We study the problem of constructing worst-case algorithms from average-case algorithms. Prior to this work, such reductions were only known for a small number of specific problems or restricted computational models. In contrast, we show that for quantum computation, all linear problems admit worst-case to average-case reductions. Specifically, we provide an explicit and efficient transformation of quantum algorithms that are only correct on a small (even sub-constant) fraction of their inputs into ones that are correct on all inputs. En route, we obtain a tight Ω(n2) lower bound on the average-case quantum query complexity of the Matrix-Vector Multiplication problem.

A constraint satisfaction problem (CSP), \(\textsf {Max-CSP}(\mathcal {F})\) , is specified by a finite set of constraints \(\mathcal {F}\subseteq \lbrace [q]^k \rightarrow \lbrace 0,1\rbrace \rbrace\) for positive integers q and k . An instance of the problem on n variables is given by m applications of constraints from \(\mathcal {F}\) to subsequences of the n variables, and the goal is to find an assignment to the variables that satisfies the maximum number of constraints. In the (γ ,β)-approximation version of the problem for parameters 0 ≤ β ≤ γ ≤ 1, the goal is to distinguish instances where at least γ fraction of the constraints can be satisfied from instances where at most β fraction of the constraints can be satisfied. In this work, we consider the approximability of this problem in the context of sketching algorithms and give a dichotomy result. Specifically, for every family \(\mathcal {F}\) and every β < γ, we show that either a linear sketching algorithm solves the problem in polylogarithmic space or the problem is not solvable by any sketching algorithm in \(o(\sqrt {n})\) space. In particular, we give non-trivial approximation algorithms using polylogarithmic space for infinitely many constraint satisfaction problems. We also extend previously known lower bounds for general streaming algorithms to a wide variety of problems, and in particular the case of q = k =2, where we get a dichotomy, and the case when the satisfying assignments of the constraints of \(\mathcal {F}\) support a distribution on \([q]^k\) with uniform marginals. Prior to this work, other than sporadic examples, the only systematic classes of CSPs that were analyzed considered the setting of Boolean variables q = 2, binary constraints k =2, and singleton families \(|\mathcal {F}|=1\) and only considered the setting where constraints are placed on literals rather than variables. Our positive results show wide applicability of bias-based algorithms used previously by [ 47 ] and [ 41 ], which we extend to include richer norm estimation algorithms, by giving a systematic way to discover biases. Our negative results combine the Fourier analytic methods of [ 56 ], which we extend to a wider class of CSPs, with a rich collection of reductions among communication complexity problems that lie at the heart of the negative results. In particular, previous works used Fourier analysis over the Boolean cube to initiate their results and the results seemed particularly tailored to functions on Boolean literals (i.e., with negations). Our techniques surprisingly allow us to get to general q -ary CSPs without negations by appealing to the same Fourier analytic starting point over Boolean hypercubes.

Proving superlogarithmic data structure lower bounds in the static group model has been a fundamental challenge in computational geometry since the early '80s. We prove a polynomial ($n^{\Omega(1)}$) lower bound for an explicit range counting problem of $n^3$ convex polygons in $\mathbb{R}^2$ (each with $n^{\tilde{O}(1)}$ facets/semialgebraic complexity), against linear storage arithmetic data structures in the group model. Our construction and analysis are based on a combination of techniques in Diophantine approximation, pseudorandomness, and compressed sensing—in particular, on the existence and partial derandomization of optimal binary compressed sensing matrices in the polynomial sparsity regime ($k = n^{1-\delta}$). As a byproduct, this establishes a (logarithmic) separation between compressed sensing matrices and the stronger RIP property.

Range Avoidance (AVOID) is a total search problem where, given a Boolean circuit $C\colon\{0,1\}^n\to\{0,1\}^m$, $m>n$, the task is to find a $y\in\{0,1\}^m$ outside the range of $C$. For an integer $k\geq 2$, $\mathrm{NC}^0_k$-AVOID is a special case of AVOID where each output bit of $C$ depends on at most $k$ input bits. While there is a very natural randomized algorithm for AVOID, a deterministic algorithm for the problem would have many interesting consequences. Ren, Santhanam, and Wang (FOCS 2022) and Guruswami, Lyu, and Wang (RANDOM 2022) proved that explicit constructions of functions of high formula complexity, rigid matrices, and optimal linear codes, reduce to $\mathrm{NC}^0_4$-AVOID, thus establishing conditional hardness of the $\mathrm{NC}^0_4$-AVOID problem. On the other hand, $\mathrm{NC}^0_2$-AVOID admits polynomial-time algorithms, leaving the question about the complexity of $\mathrm{NC}^0_3$-AVOID open. We give the first reduction of an explicit construction question to $\mathrm{NC}^0_3$-AVOID. Specifically, we prove that a polynomial-time algorithm (with an $\mathrm{NP}$ oracle) for $\mathrm{NC}^0_3$-AVOID for the case of $m=n+n^{2/3}$ would imply an explicit construction of a rigid matrix, and, thus, a super-linear lower bound on the size of log-depth circuits. We also give deterministic polynomial-time algorithms for all $\mathrm{NC}^0_k$-AVOID problems for $m\geq n^{k-1}/\log(n)$. Prior work required an $\mathrm{NP}$ oracle, and required larger stretch, $m \geq n^{k-1}$.

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

We study the complexity of lattice problems in a world where algorithms, reductions, and protocols can run in superpolynomial time. Specifically, we revisit four foundational results in this context—two protocols and two worst-case to average-case reductions. We show how to improve the approximation factor in each result by a factor of roughly √n/logn when running the protocol or reduction in 2є n time instead of polynomial time, and we show a novel protocol with no polynomial-time analog. Our results are as follows.

We analyze the sketching approximability of constraint satisfaction problems on Boolean domains, where the constraints are balanced linear threshold functions applied to literals. In~particular, we explore the approximability of monarchy-like functions where the value of the function is determined by a weighted combination of the vote of the first variable (the president) and the sum of the votes of all remaining variables. The pure version of this function is when the president can only be overruled by when all remaining variables agree. For every $k \geq 5$, we show that CSPs where the underlying predicate is a pure monarchy function on $k$ variables have no non-trivial sketching approximation algorithm in $o(\sqrt{n})$ space. We also show infinitely many weaker monarchy functions for which CSPs using such constraints are non-trivially approximable by $O(\log(n))$ space sketching algorithms. Moreover, we give the first example of sketching approximable asymmetric Boolean CSPs. Our results work within the framework of Chou, Golovnev, Sudan, and Velusamy (FOCS 2021) that characterizes the sketching approximability of all CSPs. Their framework can be applied naturally to get a computer-aided analysis of the approximability of any specific constraint satisfaction problem. The novelty of our work is in using their work to get an analysis that applies to infinitely many problems simultaneously.

We present a new framework for designing worst-case to average-case reductions. For a large class of problems, it provides an explicit transformation of algorithms running in time T that are only correct on a small (subconstant) fraction of their inputs into algorithms running in time O(T) that are correct on all inputs.

We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on n variables taking values in {0,…,q−1}, we prove that improving over the trivial approximability by a factor of q requires Ω(n) space even on instances with O(n) constraints. We also identify a broad subclass of problems for which any improvement over the trivial approximability requires Ω(n) space. The key technical core is an optimal, q−(k−1)-inapproximability for the Max k-LIN-mod q problem, which is the Max CSP problem where every constraint is given by a system of k−1 linear equations mod q over k variables.

The orthogonality dimension of a graph $G=(V,E)$ over a field $\mathbb{F}$ is the smallest integer $t$ for which there exists an assignment of a vector $u_v \in \mathbb{F}^t$ with $\langle u_v,u_v \rangle \neq 0$ to every vertex $v \in V$, such that $\langle u_v, u_{v'} \rangle = 0$ whenever $v$ and $v'$ are adjacent vertices in $G$. The study of the orthogonality dimension of graphs is motivated by various applications in information theory and in theoretical computer science. The contribution of the present work is two-fold. First, we prove that there exists a constant $c$ such that for every sufficiently large integer $t$, it is $\mathsf{NP}$-hard to decide whether the orthogonality dimension of an input graph over $\mathbb{R}$ is at most $t$ or at least $3t/2-c$. At the heart of the proof lies a geometric result, which might be of independent interest, on a generalization of the orthogonality dimension parameter for the family of Kneser graphs, analogously to a long-standing conjecture of Stahl (J. Comb. Theo. Ser. B, 1976). Second, we study the smallest possible orthogonality dimension over finite fields of the complement of graphs that do not contain certain fixed subgraphs. In particular, we provide an explicit construction of triangle-free $n$-vertex graphs whose complement has orthogonality dimension over the binary field at most $n^{1-δ}$ for some constant $δ>0$. Our results involve constructions from the family of generalized Kneser graphs and they are motivated by the rigidity approach to circuit lower bounds. We use them to answer a couple of questions raised by Codenotti, Pudlák, and Resta (Theor. Comput. Sci., 2000), and in particular, to disprove their Odd Alternating Cycle Conjecture over every finite field.

A constraint satisfaction problem (CSP),$\text{Max}-\text{CSP}(\mathcal{F})$, is specified by a finite set of constraints$\mathcal{F}\subseteq\{[q]^{k}\rightarrow\{0,1\}\}$for positive integers$q$and$k$. An instance of the problem on$n$variables is given by$m$applications of constraints from$\mathcal{F}$to subsequences of the$n$variables, and the goal is to find an assignment to the variables that satisfies the maximum number of constraints. In the ($\gamma, \beta$)-approximation version of the problem, for parameters$0\leq\beta < \gamma\leq 1$, the goal is to distinguish instances where at least$\gamma$fraction of the constraints can be satisfied from instances where at most$\beta$fraction of the constraints can be satisfied. In this work we consider the approximability of this problem in the context of sketching algorithms and give a dichotomy result. Specifically, for every family$\mathcal{F}$and every$\beta < \gamma$, we show that either a linear sketching algorithm solves the problem in polylogarithmic space, or the problem is not solvable by any sketching algorithm in$o(\sqrt{n})$space. We also extend previously known lower bounds for general streaming algorithms to a wide variety of problems, and in particular the case of$q=k=2$where we get a dichotomy and the case when the satisfying assignments of$f$support a distribution on$[q]^{k}$with uniform marginals. Prior to this work, other than sporadic examples, the only systematic class of CSPs that were analyzed considered the setting of Boolean variables$q=2$, binary constraints$k=2$, singleton families$\vert \mathcal{F}\vert =1$and only considered the setting where constraints are placed on literals rather than variables. Our positive results show wide applicability of bias-based algorithms used previously by [2] and [3], which we extend to include richer norm estimation algorithms, by giving a systematic way to discover biases. Our negative results combine the Fourier analytic methods of [4], which we extend to a wider class of CSPs, with a rich collection of reductions among communication complexity problems that lie at the heart of the negative results. In particular, previous works used Fourier analysis over the Boolean cube to initiate their results and the results seemed particularly tailored to functions on Boolean literals (i.e., with negations). Our techniques surprisingly allow us to get to general$q$-ary CSPs without negations by appealing to the same Fourier analytic starting point over Boolean hypercubes.

The best known size lower bounds against unrestricted circuits have remained around 3n for several decades. Moreover, the only known technique for proving lower bounds in this model, gate elimination, is inherently limited to proving lower bounds of less than 5n. In this work, we propose a non-gate-elimination approach for obtaining circuit lower bounds, via certain depth-three lower bounds. We prove that every (unbounded-depth) circuit of size s can be expressed as an OR of 2^{s/3.9} 16-CNFs. For DeMorgan formulas, the best known size lower bounds have been stuck at around n^{3-o(1)} for decades. Under a plausible hypothesis about probabilistic polynomials, we show that n^{4-ε}-size DeMorgan formulas have 2^{n^{1-Ω(ε)}}-size depth-3 circuits which are approximate sums of n^{1-Ω(ε)}-degree polynomials over F₂. While these structural results do not immediately lead to new lower bounds, they do suggest new avenues of attack on these longstanding lower bound problems. Our results complement the classical depth-3 reduction results of Valiant, which show that logarithmic-depth circuits of linear size can be computed by an OR of 2^{ε n} n^δ-CNFs, and slightly stronger results for series-parallel circuits. It is known that no purely graph-theoretic reduction could yield interesting depth-3 circuits from circuits of super-logarithmic depth. We overcome this limitation (for small-size circuits) by taking into account both the graph-theoretic and functional properties of circuits and formulas. We show that improvements of the following pseudorandom constructions imply super-linear circuit lower bounds for log-depth circuits via Valiant’s reduction: dispersers for varieties, correlation with constant degree polynomials, matrix rigidity, and hardness for depth-3 circuits with constant bottom fan-in. On the other hand, our depth reductions show that even modest improvements of the known constructions give elementary proofs of improved (but still linear) circuit lower bounds.

We show a number of fine-grained hardness results for the Closest Vector Problem in the ℓp norm (CVPp), and its approximate and non-uniform variants. First, we show that CVPp cannot be solved in 2(1–∊)n time for all p ∉ 2ℤ and ∊ > 0, assuming the Strong Exponential Time Hypothesis (SETH). Second, we extend this by showing that there is no 2(1–∊)n-time algorithm for approximating CVPp to within a constant factor γ for such p assuming a “gap” version of SETH, with an explicit relationship between γ, p, and the arity k = k(∊) of the underlying hard CSP. Third, we show the same hardness result for (exact) CVPp with preprocessing (assuming non-uniform SETH). For exact “plain” CVPp, the same hardness result was shown in [Bennett, Golovnev, and Stephens-Davidowitz FOCS 2017] for all but finitely many p ∉ 2ℤ, where the set of exceptions depended on ∊ and was not explicit. For the approximate and preprocessing problems, only very weak bounds were known prior to this work. We also show that the restriction to p ∉ 2ℤ is in some sense inherent. In particular, we show that no “natural” reduction can rule out even a 23n/4-time algorithm for CVP2 under SETH. For this, we prove that the possible sets of closest lattice vectors to a target in the ℓ2 norm have quite rigid structure, which essentially prevents them from being as expressive as 3-CNFs. We prove these results using techniques from many different fields, including complex analysis, functional analysis, additive combinatorics, and discrete Fourier analysis. E.g., along the way, we give a new (and tighter) proof of Szemerédi's cube lemma for the boolean cube. Please see the full version of this paper for the proofs of these results [1].

We prove tight upper and lower bounds on approximation ratios of all Boolean Max-2CSP problems in the streaming model. Specifically, for every type of Max-2CSP problem, we give an explicit constant α, s.t. for any (i) there is an ( α-ε)-streaming approximation using space O(logn); and (ii) any ( α+ε)-streaming approximation requires space Ω(√n). This generalizes the celebrated work of [Kapralov, Khanna, Sudan SODA 2015; Kapralov, Krachun STOC 2019], who showed that the optimal approximation ratio for Max-CUT was 1/2. Prior to this work, the problem of determining this ratio was open for all other Max-2CSPs. Our results are quite surprising for some specific Max-2CSPs. For the Max-DICUT problem, there was a gap between an upper bound of 1/2 and a lower bound of 2/5 [Guruswami, Velingker, Velusamy APPROX 2017]. We show that neither of these bounds is tight, and the optimal ratio for Max-DICUT is 4/9. We also establish that the tight approximation for Max-2SAT is √2/2, and for Exact Max-2SAT it is 3/4. As a byproduct, our result gives a separation between space-efficient approximations for Max-2SAT and Exact Max-2SAT. This is in sharp contrast to the setting of polynomial-time algorithms with polynomial space, where the two problems are known to be equally hard to approximate. Finally, we prove that the tight streaming approximation for Max-kSAT is √2/2 for every k ≥ 2.

Proving super-logarithmic data structure lower bounds in the static group model has been a fundamental challenge in computational geometry since the early 80's. We prove a polynomial (nΩ(1)) lower bound for an explicit range counting problem of n3convex polygons in \mathbbR2(each with nÕ̃(1)facets/semialgebraic-complexity), against linear storage arithmetic data structures in the group model. Our construction and analysis are based on a combination of techniques in Diophantine approximation, pseudorandomness, and compressed sensing-in particular, on the existence and partial derandomization of optimal binary compressed sensing matrices in the polynomial sparsity regime (k=n1-δ). As a byproduct, this establishes a (logarithmic) separation between compressed sensing matrices and the stronger RIP property.

This paper shows several connections between data structure problems and cryptography against preprocessing attacks. Our results span data structure upper bounds, cryptographic applications, and data structure lower bounds, as summarized next.

String matching is the problem of deciding whether a given $n$-bit string contains a given $k$-bit pattern. We study the complexity of this problem in three settings. Communication complexity. For small $k$, we provide near-optimal upper and lower bounds on the communication complexity of string matching. For large $k$, our bounds leave open an exponential gap; we exhibit some evidence for the existence of a better protocol. Circuit complexity. We present several upper and lower bounds on the size of circuits with threshold and DeMorgan gates solving the string matching problem. Similarly to the above, our bounds are near-optimal for small $k$. Learning. We consider the problem of learning a hidden pattern of length at most $k$ relative to the classifier that assigns 1 to every string that contains the pattern. We prove optimal bounds on the VC dimension and sample complexity of this problem.

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.

Minimum Circuit Size Problem (MCSP) asks to decide if a given truth table of an n-variate boolean function has circuit complexity less than a given parameter s. We prove that MCSP is hard for constant-depth circuits with mod p gates, for any prime p >= 2 (the circuit class AC^0[p]). Namely, we show that MCSP requires d-depth AC^0[p] circuits of size at least exp(N^{0.49/d}), where N=2^n is the size of an input truth table of an n-variate boolean function. Our circuit lower bound proof shows that MCSP can solve the coin problem: distinguish uniformly random N-bit strings from those generated using independent samples from a biased random coin which is 1 with probability 1/2+N^{-0.49}, and 0 otherwise. Solving the coin problem with such parameters is known to require exponentially large AC^0[p] circuits. Moreover, this also implies that MAJORITY is computable by a non-uniform AC^0 circuit of polynomial size that also has MCSP-oracle gates. The latter has a few other consequences for the complexity of MCSP, e.g., we get that any boolean function in NC^1 (i.e., computable by a polynomial-size formula) can also be computed by a non-uniform polynomial-size AC^0 circuit with MCSP-oracle gates.

We quantify the separation between the numbers of labeled examples required to learn in two settings: Settings with and without the knowledge of the distribution of the unlabeled data. More specifically, we prove a separation by $\Theta(\log n)$ multiplicative factor for the class of projections over the Boolean hypercube of dimension $n$. We prove that there is no separation for the class of all functions on domain of any size. Learning with the knowledge of the distribution (a.k.a. fixed-distribution learning) can be viewed as an idealized scenario of semi-supervised learning where the number of unlabeled data points is so great that the unlabeled distribution is known exactly. For this reason, we call the separation the value of unlabeled data.

We show that static data structure lower bounds in the group (linear) model imply semi-explicit lower bounds on matrix rigidity. In particular, we prove that an explicit lower bound of t ≥ ω(log2 n) on the cell-probe complexity of linear data structures in the group model, even against arbitrarily small linear space (s= (1+)n), would already imply a semi-explicit (PNP) construction of rigid matrices with significantly better parameters than the current state of art (Alon, Panigrahy and Yekhanin, 2009). Our results further assert that polynomial (t≥ nδ) data structure lower bounds against near-optimal space, would imply super-linear circuit lower bounds for log-depth linear circuits (a four-decade open question). In the succinct space regime (s=n+o(n)), we show that any improvement on current cell-probe lower bounds in the linear model would also imply new rigidity bounds. Our results rely on a new connection between the “inner” and “outer” dimensions of a matrix (Paturi and Pudlák, 2006), and on a new reduction from worst-case to average-case rigidity, which is of independent interest.

The minrank of a directed graph G is the minimum rank of a matrix M that can be obtained from the adjacency matrix of G by switching some ones to zeros (i.e., deleting edges) and then setting all diagonal entries to one. This quantity is closely related to the fundamental information-theoretic problems of (linear) index coding (Bar-Yossef et al.), network coding (Effros et al.), and distributed storage (Mazumdar, ISIT, 2014). We prove tight bounds on the minrank of directed Erdos- Rényi random graphs G(n, p) for all regimes of p ∈ [0, 1]. In particular, for any constant p, we show that minrk(G) = Θ(n/log n) with high probability, where G is chosen from the previous best lower bound of Ω(√(n)) (Haviv and Langberg), G(n, p). This bound gives a near quadratic improvement over and partially settles an open problem raised by Lubetzky and Stav. Our lower bound matches the well-known upper bound obtained by the “clique covering" solution and settles the linear index coding problem for random knowledge graphs.

For odd integers p ≥ 1 (and p = ∞), we show that the Closest Vector Problem in the ℓpnorm (CVPp) over rank n lattices cannot be solved in 2(1-ε)ntime for any constant ε > 0 unless the Strong Exponential Time Hypothesis (SETH) fails. We then extend this result to “almost all” values of p ≥ 1, not including the even integers. This comes tantalizingly close to settling the quantitative time complexity of the important special case of CVP2(i.e., CVP in the Euclidean norm), for which a 2n+o(n)-time algorithm is known. In particular, our result applies for any p = p(n) ≠ 2 that approaches 2 as n → ∞. We also show a similar SETH-hardness result for SVP∞; hardness of approximating CVPpto within some constant factor under the so-called Gap-ETH assumption; and other hardness results for CVPpand CVPPpfor any 1 ≤ p <; ∞ under different assumptions.

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 consider Boolean circuits over the full binary basis. We prove a (3+1/86)n-o(n) lower bound on the size of such a circuit for an explicitly defined predicate, namely an affine disperser for sublinear dimension. This improves the 3n-o(n) bound of Norbert Blum (1984).The proof is based on the gate elimination technique extended with the following three ideas. We generalize the computational model by allowing circuits to contain cycles, this in turn allows us to perform affine substitutions. We use a carefully chosen circuit complexity measure to track the progress of the gate elimination process. Finally, we use quadratic substitutions that may be viewed as delayed affine substitutions.

In this paper we motivate the study of Boolean dispersers for quadratic varieties by showing that an explicit construction of such objects gives improved circuit lower bounds. An (n,k,s)-quadratic disperser is a function on n variables that is not constant on any subset of Fn/2 of size at least s that can be defined as the set of common roots of at most k quadratic polynomials. We show that if a Boolean function f is a (n, 1.83n, 2g(n)-quadratic disperser for any function g(n)=o(n) then the circuit size of f is at least 3.11n. In order to prove this, we generalize the gate elimination method so that the induction works on the size of the variety rather than on the number of variables as in previously known proofs.

Although a simple counting argument shows the existence of Boolean functions of exponential circuit complexity, proving superlinear circuit lower bounds for explicit functions seems to be out of reach of the current techniques. There has been a (very slow) progress in proving linear lower bounds with the latest record of 3 1/86*n-o(n). All known lower bounds are based on the so-called gate elimination technique. A typical gate elimination argument shows that it is possible to eliminate several gates from an optimal circuit by making one or several substitutions to the input variables and repeats this inductively. In this note we prove that this method cannot achieve linear bounds of cn beyond a certain constant c, where c depends only on the number of substitutions made at a single step of the induction.

Most of the known lower bounds for binary Boolean circuits with unrestricted depth are proved by the gate elimination method. The most efficient known algorithms for the #SAT problem on binary Boolean circuits use similar case analyses to the ones in gate elimination. Chen and Kabanets recently showed that the known case analyses can also be used to prove average case circuit lower bounds, that is, lower bounds on the size of approximations of an explicit function. In this paper, we provide a general framework for proving worst/average case lower bounds for circuits and upper bounds for #SAT that is built on ideas of Chen and Kabanets. A proof in such a framework goes as follows. One starts by fixing three parameters: a class of circuits, a circuit complexity measure, and a set of allowed substitutions. The main ingredient of a proof goes as follows: by going through a number of cases, one shows that for any circuit from the given class, one can find an allowed substitution such that the given measure of the circuit reduces by a sufficient amount. This case analysis immediately implies an upper bound for #SAT. To~obtain worst/average case circuit complexity lower bounds one needs to present an explicit construction of a function that is a disperser/extractor for the class of sources defined by the set of substitutions under consideration. We show that many known proofs (of circuit size lower bounds and upper bounds for #SAT) fall into this framework. Using this framework, we prove the following new bounds: average case lower bounds of 3.24n and 2.59n for circuits over U_2 and B_2, respectively (though the lower bound for the basis B_2 is given for a quadratic disperser whose explicit construction is not currently known), and faster than 2^n #SAT-algorithms for circuits over U_2 and B_2 of size at most 3.24n and 2.99n, respectively. Here by B_2 we mean the set of all bivariate Boolean functions, and by U_2 the set of all bivariate Boolean functions except for parity and its complement.

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.