For several well-studied triangle detection problems in the literature, the trivial enumeration algorithms are known to be optimal (up to the exponent) assuming popular fine-grained conjectures. For example, All-Edges Sparse Triangle and Sparse Monochromatic Triangle where each node has degree n^δ for some δ < 1, and the Exact Triangle where edges have arbitrary weights, all have this property under the 3SUM Conjecture. However, as there are slightly nontrivial algorithms for 3SUM, it is natural to wonder if the trivial algorithm for these tricky triangle tasks might also be improved. Applying a variety of techniques from randomized algorithms, circuit complexity, and communication complexity, we present the first improvements over the trivial algorithms for each of these problems in the Word RAM model. Moreover, our algorithms can be implemented with only polysize AC0 operations on words. Extending our techniques, we also show how to solve the notorious 4-cycle detection problem on n-node graphs in o(n²) time, in a Word-RAM model with word size w > ω(log² n). Along the way, we show how to sort n items over a universe of size 2^u using only AC0 word operations in O(n u log n)/w time.

Given a function, what is the minimal memory necessary to compute it? We will describe some old [John E. Hopcroft et al., 1977; Wolfgang J. Paul and Rüdiger Reischuk, 1981; Joseph Y. Halpern et al., 1986] and new algorithmic developments that give surprisingly low-space solutions to this question in many cases. We will survey the recent proof [Ryan Williams, 2026] that TIME[t] is contained in SPACE[√{t log t}] for the multitape Turing machine model, and the engine that makes the proof possible: the amazing Cook-Mertz algorithm [James Cook and Ian Mertz, 2024] for a problem called Tree Evaluation [Stephen A. Cook et al., 2012]. We will also briefly outline some new developments and generalizations that we've recently proved, pushing the low-space frontier beyond multitape Turing machines. The latter is joint work with Danil Sibgatullin (to appear).

In this work, we propose a new bounded arithmetic theory, denoted APX1, designed to formalize a broad class of probabilistic arguments commonly used in theoretical computer science. Under plausible assumptions, APX1 is strictly weaker than previously proposed frameworks, such as the theory APC1 introduced in the seminal work of Jeřábek (2007). From a computational standpoint, APX1 is closely tied to approximate counting and to the central question in derandomization, the prBPP versus prP problem, whereas APC1 is linked to the dual weak pigeonhole principle and to the existence of Boolean functions with exponential circuit complexity.

Probabilistic polynomials over commutative rings offer a powerful way of representing Boolean functions. Although many degree lower bounds for such representations have been proved, sparsity lower bounds (counting the number of monomials in the polynomials) have not been so common. Sparsity upper bounds are of great interest for potential algorithmic applications, since sparse probabilistic polynomials are the key technical tool behind the best known algorithms for many core problems, including dense All-Pairs Shortest Paths, and the existence of sparser polynomials would lead to breakthrough algorithms for these problems. In this paper, we prove several strong lower bounds on the sparsity of probabilistic and approximate polynomials computing Boolean functions when 0 means "false". Our main result is that the AND of n ORs of c log n variables requires probabilistic polynomials (over any commutative ring which isn't too large) of sparsity n^Ω(log c) to achieve even 1/4 error. The lower bound is tight, and it rules out a large class of polynomial-method approaches for refuting the APSP and SETH conjectures via matrix multiplication. Our other results include: - Every probabilistic polynomial (over a commutative ring) for the disjointness function on two n-bit vectors requires exponential sparsity in order to achieve exponentially low error. - A generic lower bound that any function requiring probabilistic polynomials of degree d must require probabilistic polynomials of sparsity Ω(2^d). - Building on earlier work, we consider the probabilistic rank of Boolean functions which generalizes the notion of sparsity for probabilistic polynomials, and prove separations of probabilistic rank and probabilistic sparsity. Some of our results and lemmas are basis independent. For example, over any basis {a,b} for true and false where a ≠ b, and any commutative ring R, the AND function on n variables has no probabilistic R-polynomial with 2^o(n) sparsity, o(n) degree, and 1/2^o(n) error simultaneously. This AND lower bound is our main technical lemma used in the above lower bounds.

STOC ’25, Prague, Czechia

We show that for all functions \(t(n) \ge n\) , every multitape Turing machine running in time t can be simulated in space only \(O(\sqrt {t \log t})\) . This is a substantial improvement over Hopcroft, Paul, and Valiant’s simulation of time t in \(O(t/\log t)\) space from 50 years ago [FOCS 1975, JACM 1977]. Among other results, our simulation implies that bounded fan-in circuits of size s can be evaluated on any input in only \(\sqrt {s} \cdot \text{poly}(\log s)\) space, and that there are explicit problems solvable in \(O(n)\) space which require \(n^{2-\varepsilon }\) time on a multitape Turing machine for all \(\varepsilon \gt 0\) , thereby making a little progress on the \({\sf P}\) versus \({\sf PSPACE}\) problem. Our simulation reduces the problem of simulating time-bounded multitape Turing machines to a series of implicitly-defined Tree Evaluation instances with nice parameters, leveraging the remarkable space-efficient algorithm for Tree Evaluation recently found by Cook and Mertz [STOC 2024].

A line of work has shown how nontrivial uniform algorithms for analyzing circuits can be used to derive non-uniform circuit lower bounds. We show how the non-existence of nontrivial circuit-analysis algorithms can also imply non-uniform circuit lower bounds. Our connections yield new win-win circuit lower bounds, and suggest a potential approach to refuting the Orthogonal Vectors Conjecture in the$O(\log n)$-dimensional case, which would be sufficient for refuting the Strong Exponential Time Hypothesis (SETH). For example, we show that at least one of the following holds: • There is an$\varepsilon>0$such that for infinitely many$n$, read-once 2-DNFs on$n$variables cannot be simulated by non-uniform$2^{\varepsilon n}$-size depth-two exact threshold circuits. It is already a notorious open problem to prove that the class$E^{N P}$does not have polynomial-size depth-two exact threshold circuits, so such a lower bound would be a significant advance in low-depth circuit complexity. In fact, a stronger lower bound holds in this case: the$2^n \times 2^n$Disjointness Matrix (well-studied in communication complexity) cannot be expressed by a linear combination of$2^{o(n)}$structured matrices that we call “equality matrices”. • For every$c \geq 1$and every$\varepsilon>0$, Orthogonal Vectors on$n$vectors in$c \log n$dimensions can be solved in$n^{1+\varepsilon}$uniform deterministic time. This case would provide a strong refutation of the Orthogonal Vectors conjecture, and of SETH: for example, CNF-SAT on$n$variables and$O(n)$clauses could be solved in$2^{n / 2+o(n)}$time. Moreover, this case would imply non-uniform circuit lower bounds for the class$E^{NP}$, against Valiant series-parallel circuits. Inspired by this connection, we give evidence from SAT/SMT solvers that the first item (in particular, the Disjointness lower bound) may be false in its full generality. In particular, we present a systematic approach to solving Orthogonal Vectors via constant-sized decompositions of the Disjointness Matrix, which already yields interesting new algorithms. For example, using a linear combination of 6 equality matrices that express$2^6 \times 2^6$Disjointness, we derive an$\tilde{O}\left(n \cdot 6^{d / 6}\right) \leq \tilde{O}\left(n \cdot 1. \dot{35^d}\right)$time and$n \cdot \operatorname{poly}(\log n, d)$space algorithm for Orthogonal Vectors on$n$vectors in$d$dimensions. We show similar results for counting pairs of orthogonal vectors.

A compression problem is defined with respect to an efficient encoding function f; given a string x, our task is to find the shortest y such that f(y) = x. The obvious brute-force algorithm for solving this compression task on n-bit strings runs in time O(2ℓ · t(n)), where ℓ is the length of the shortest description y and t(n) is the time complexity of f when it prints n-bit output. We prove that every compression problem has a Boolean circuit family which finds short descriptions more efficiently than brute force. In particular, our circuits have size 24 ℓ / 5 · poly(t(n)), which is significantly more efficient for all ℓ ≫ log(t(n)). Our construction builds on Fiat-Naor’s data structure for function inversion [SICOMP 1999]: we show how to carefully modify their data structure so that it can be nontrivially implemented using Boolean circuits, and we show how to utilize hashing so that the circuit size is only exponential in the description length. As a consequence, the Minimum Circuit Size Problem for generic fan-in two circuits of size s(n) on truth tables of size 2n can be solved by circuits of size 24/5 · w + o(w) · poly(2n), where w = s(n) log2(s(n) + n). This improves over the brute-force approach of trying all possible size-s(n) circuits for all s(n) ≥ n. Similarly, the task of computing a short description of a string x when its t-complexity is at most ℓ, has circuits of size 24/5 ℓ · poly(t). We also give nontrivial circuits for computing Kt complexity on average, and for solving NP relations with “compressible” instance-witness pairs.

Many results in fine-grained complexity reveal intriguing consequences from solving various SAT problems even slightly faster than exhaustive search. We prove a “self-improving” (or “bootstrapping”) theorem for Circuit-SAT, #Circuit-SAT, and its fully-quantified version: solving one of these problems faster for “large” circuit sizes implies a significant speed-up for “smaller” circuit sizes. Our general arguments work for a variety of models solving circuit-analysis problems, including non-uniform circuits and randomized models of computation.

The k-Detour problem is a basic path-finding problem: given a graph G on n vertices, with specified nodes s and t, and a positive integer k, the goal is to determine if G has an st-path of length exactly dist(s,t) + k, where dist(s,t) is the length of a shortest path from s to t. The k-Detour problem is NP-hard when k is part of the input, so researchers have sought efficient parameterized algorithms for this task, running in f(k)poly(n) time, for f(⋅) as slow-growing as possible. We present faster algorithms for k-Detour in undirected graphs, running in 1.853^k poly(n) randomized and 4.082^kpoly(n) deterministic time. The previous fastest algorithms for this problem took 2.746^k poly(n) randomized and 6.523^k poly(n) deterministic time [Bezáková-Curticapean-Dell-Fomin, ICALP 2017]. Our algorithms use the fact that detecting a path of a given length in an undirected graph is easier if we are promised that the path belongs to what we call a "bipartitioned" subgraph, where the nodes are split into two parts and the path must satisfy constraints on those parts. Previously, this idea was used to obtain the fastest known algorithm for finding paths of length k in undirected graphs [Björklund-Husfeldt-Kaski-Koivisto, JCSS 2017], intuitively by looking for paths of length k in randomly bipartitioned subgraphs. Our algorithms for k-Detour stem from a new application of this idea, which does not involve choosing the bipartitioned subgraphs randomly. Our work has direct implications for the k-Longest Detour problem, another related path-finding problem. In this problem, we are given the same input as in k-Detour, but are now tasked with determining if G has an st-path of length at least dist(s,t)+k. Our results for k-Detour imply that we can solve k-Longest Detour in 3.432^k poly(n) randomized and 16.661^k poly(n) deterministic time. The previous fastest algorithms for this problem took 7.539^k poly(n) randomized and 42.549^k poly(n) deterministic time [Fomin et al., STACS 2022].

We establish an equivalence between two algorithmic tasks: derandomization, the deterministic simulation of probabilistic algorithms; and refutation, the deterministic construction of inputs on which a given probabilistic algorithm fails to compute a certain hard function. We prove that refuting low-space probabilistic streaming algorithms which attempt to compute functions $f \in \mathcal{F P}$ is equivalent to proving that $\operatorname{pr} \mathcal{B P} \mathcal{P}=\operatorname{pr} \mathcal{P}$, even in cases where a lower bound for f against such streaming algorithms (without a refuter) is already unconditionally known. We also demonstrate the generality of our connection between refutation and derandomization, by establishing connections between refuting classes of constant-depth circuits of sublinear size and derandomizing constant-depth circuits of polynomial size with threshold gates (i.e., $\mathcal{T C}^{0}$). Our connection generalizes and strengthens recent work on the characterization of derandomization. In particular, the refuter framework allows to directly compare several recent works to each other and to our work, as well as to chart a path for further progress. Along the way, we also improve the targeted hitting-set generator of Chen and Tell (FOCS 2021), showing that its translation of hardness to pseudorandomness scales down to $\mathcal{T C}^{0}$.

The range avoidance problem (denoted by Avoid) asks to find a string outside of the range of a given circuit C:{0,1}n→{0,1}m, where m>n. Although at least half of the strings of length m are correct answers, it is not clear how to deterministically find one. Recent results of Korten (FOCS’21) and Ren, Wang, and Santhanam (FOCS’ 22) show that efficient deterministic algorithms for Avoid would have far-reaching consequences, including strong circuit lower bounds and explicit constructions of combinatorial objects (e.g., Ramsey graphs, extractors, rigid matrices). This strongly motivates the question: does an efficient deterministic algorithm for Avoid actually exist?

Abstract In a Merlin–Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability 1, and rejects invalid proofs with probability arbitrarily close to 1. The running time of such a system is defined to be the length of Merlin’s proof plus the running time of Arthur. We provide new Merlin–Arthur proof systems for some key problems in fine-grained complexity. In several cases our proof systems have optimal running time. Our main results include: Certifying that a list ofnintegers has no 3-SUM solution can be done in Merlin–Arthur time $$\tilde{O}(n)$$ O~(n) . Previously, Carmosino et al. [ITCS 2016] showed that the problem has a nondeterministic algorithm running in $$\tilde{O}(n^{1.5})$$ O~(n1.5) time (that is, there is a proof system with proofs of length $$\tilde{O}(n^{1.5})$$ O~(n1.5) and a deterministic verifier running in $$\tilde{O}(n^{1.5})$$ O~(n1.5) time). Counting the number ofk-cliques with total edge weight equal to zero in ann-node graph can be done in Merlin–Arthur time $${\tilde{O}}(n^{\lceil k/2\rceil })$$ O~(n⌈k/2⌉) (where $$k\ge 3$$ k≥3 ). For oddk, this bound can be further improved for sparse graphs: for example, counting the number of zero-weight triangles in anm-edge graph can be done in Merlin–Arthur time $${\tilde{O}}(m)$$ O~(m) . Previous Merlin–Arthur protocols by Williams [CCC’16] and Björklund and Kaski [PODC’16] could only countk-cliques in unweighted graphs, and had worse running times for smallk. Computing the All-Pairs Shortest Distances matrix for ann-node graph can be done in Merlin–Arthur time $$\tilde{O}(n^2)$$ O~(n2) . Note this is optimal, as the matrix can have $$\Omega (n^2)$$ Ω(n2) nonzero entries in general. Previously, Carmosino et al. [ITCS 2016] showed that this problem has an $$\tilde{O}(n^{2.94})$$ O~(n2.94) nondeterministic time algorithm. Certifying that ann-variablek-CNF is unsatisfiable can be done in Merlin–Arthur time $$2^{n/2 - n/O(k)}$$ 2n/2-n/O(k) . We also observe an algebrization barrier for the previous $$2^{n/2}\cdot \textrm{poly}(n)$$ 2n/2·poly(n) -time Merlin–Arthur protocol of R. Williams [CCC’16] for $$\#$$ # SAT: in particular, his protocol algebrizes, and we observe there is no algebrizing protocol fork-UNSAT running in $$2^{n/2}/n^{\omega (1)}$$ 2n/2/nω(1) time. Therefore we have to exploit non-algebrizing properties to obtain our new protocol. Certifying a Quantified Boolean Formula is true can be done in Merlin–Arthur time $$2^{4n/5}\cdot \textrm{poly}(n)$$ 24n/5·poly(n) . Previously, the only nontrivial result known along these lines was an Arthur–Merlin–Arthur protocol (where Merlin’s proof depends on some of Arthur’s coins) running in $$2^{2n/3}\cdot \textrm{poly}(n)$$ 22n/3·poly(n) time. Due to the centrality of these problems in fine-grained complexity, our results have consequences for many other problems of interest. For example, our work implies that certifying there is no Subset Sum solution tonintegers can be done in Merlin–Arthur time $$2^{n/3}\cdot \textrm{poly}(n)$$ 2n/3·poly(n)

Abstract We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in $\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$ Quasi - NP = NTIME [ n ( log n ) O ( 1 ) ] and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes $\mathcal { C}$ C , by showing that $\mathcal { C}$ C admits non-trivial satisfiability and/or # SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial # SAT algorithm for a circuit class ${\mathcal C}$ C . Say that a symmetric Boolean function f(x1,…,xn) is sparse if it outputs 1 on O(1) values of ${\sum }_{i} x_{i}$ ∑ i x i . We show that for every sparse f, and for all “typical” $\mathcal { C}$ C , faster # SAT algorithms for $\mathcal { C}$ C circuits imply lower bounds against the circuit class $f \circ \mathcal { C}$ f ∘ C , which may be stronger than $\mathcal { C}$ C itself. In particular: # SAT algorithms for nk-size $\mathcal { C}$ C -circuits running in 2n/nk time (for all k) imply NEXP does not have $(f \circ \mathcal { C})$ ( f ∘ C ) -circuits of polynomial size. # SAT algorithms for $2^{n^{{\varepsilon }}}$ 2 n ε -size $\mathcal { C}$ C -circuits running in $2^{n-n^{{\varepsilon }}}$ 2 n − n ε time (for some ε > 0) imply Quasi-NP does not have $(f \circ \mathcal { C})$ ( f ∘ C ) -circuits of polynomial size. Applying # SAT algorithms from the literature, one immediate corollary of our results is that Quasi-NP does not have EMA

In 1981, Neil Immerman described a two-player game, which he called the "separability game" \cite{Immerman81}, that captures the number of quantifiers needed to describe a property in first-order logic. Immerman's paper laid the groundwork for studying the number of quantifiers needed to express properties in first-order logic, but the game seemed to be too complicated to study, and the arguments of the paper almost exclusively used quantifier rank as a lower bound on the total number of quantifiers. However, last year Fagin, Lenchner, Regan and Vyas rediscovered the games, provided some tools for analyzing them, and showed how to utilize them to characterize the number of quantifiers needed to express linear orders of different sizes. In this paper, we push forward in the study of number of quantifiers as a bona fide complexity measure by establishing several new results. First we carefully distinguish minimum number of quantifiers from the more usual descriptive complexity measures, minimum quantifier rank and minimum number of variables. Then, for each positive integer $k$, we give an explicit example of a property of finite structures (in particular, of finite graphs) that can be expressed with a sentence of quantifier rank $k$, but where the same property needs $2^{Ω(k^2)}$ quantifiers to be expressed.

We consider low-space algorithms for the classic Element Distinctness problem: given an array of n input integers with O(log n) bit-length, decide whether or not all elements are pairwise distinct. Beame, Clifford, and Machmouchi [FOCS 2013] gave an Õ(n1.5)-time randomized algorithm for Element Distinctness using only O(log n) bits of working space. However, their algorithm assumes a random oracle (in particular, read-only random access to polynomially many random bits), and it was asked as an open question whether this assumption can be removed. In this paper, we positively answer this question by giving an Õ(n1.5)-time randomized algorithm using O(log3 n log log n) bits of space, with one-way access to random bits. As a corollary, we also obtain a poly(n)-space O∗(20.86n)-time randomized algorithm for the Subset Sum problem, removing the random oracles required in the algorithm of Bansal, Garg, Nederlof, and Vyas [STOC 2017]. The main technique underlying our results is a pseudorandom hash family based on iterative restrictions, which can fool the cycle-finding procedure in the algorithms of Beame et al. and Bansal et al.

For a complexity class C and language L, a constructive separation of “L is not in C” gives an efficient algorithm (also called a refuter) to find counterexamples (bad inputs) for every C-algorithm attempting to decide L. We study the questions: Which lower bounds can be made constructive? What are the consequences of constructive separations? We build a case that “constructiveness” serves as a dividing line between many weak lower bounds we know how to prove, and strong lower bounds against P, ZPP, and BPP. Put another way, constructiveness is the opposite of a complexity barrier: it is a property we want lower bounds to have. Our results fall into three broad categories. 1. For many separations, making them constructive would imply breakthrough lower bounds. Our first set of results shows that, for many well-known lower bounds against streaming algorithms, one-tape Turing machines, and query complexity, as well as lower bounds for the Minimum Circuit Size Problem, making these lower bounds constructive would imply break-through separations ranging from “EXP not equal to BPP” to even “P not equal to NP”. 2. Most conjectured uniform separations can be made constructive. Our second set of results shows that for most major open problems in lower bounds against P, ZPP, and BPP, including “P not equal to NP”, “P not equal to PSPACE”, “P not equal to PP”, “ZPP not equal to EXP”, and “BPP not equal to NEXP”, any proof of the separation would further imply a constructive separation. Our results generalize earlier results for “P not equal to NP” [Gutfreund, Shaltiel, and Ta-Shma, CCC 2005] and “BPP not equal to NEXP” [Dolev, Fandina and Gutfreund, CIAC 2013]. Thus any proof of these strong lower bounds must also yield a constructive version, compared to many weak lower bounds we currently know. 3. Some separations cannot be made constructive. Our third set of results shows that certain complexity separations cannot be made constructive. We observe that for all super-polynomially growing functions$\mathbf{t}$, there are no constructive separations for detecting high t-time Kolmogorov complexity (a task which is known to be not in P) from any complexity class, unconditionally. We also show that under plausible conjectures, there are languages in NP -$\mathbf{P}$for which there are no constructive separations from any complexity class.

Majority-SAT (a.k.a. MAJ-SAT) is the problem of determining whether an input n-variable formula in conjunctive normal form (CNF) has at least 2^(n-1) satisfying assignments. Majority-SAT and related problems have been studied extensively in various AI communities interested in the complexity of probabilistic planning and inference. Although Majority-SAT has been known to be PP-complete for over 40 years, the complexity of a natural variant has remained open: Majority-kSAT, where the input CNF formula is restricted to have clause width at most k. We prove that for every k, Majority-kSAT is in P; in fact, the problem can be solved in linear time (whereas the previous best-known algorithm ran in exponential time). More generally, for any positive integer k and constant p in (0,1) with bounded denominator, we give an algorithm that can determine whether a given k-CNF has at least p(2^n) satisfying assignments, in deterministic linear time. We find these results surprising, as many analogous problems which are hard for CNF formulas remain hard when restricted to 3-CNFs. Our algorithms have interesting positive implications for counting complexity and the complexity of inference, significantly reducing the known complexities of related problems such as E-MAJ-kSAT and MAJ-MAJ-kSAT. Our results immediately extend to arbitrary Boolean CSPs with constraints of arity k. At the heart of our approach is an efficient method for solving threshold counting problems by extracting and analyzing various sunflowers found in the corresponding set system of a k-CNF. Exploring the implications of our results, we find that the tractability of Majority-kSAT is somewhat fragile, in intriguing ways. For the closely related GtMajority-SAT problem (where we ask whether a given formula has greater than 2^(n-1) satisfying assignments) which is also known to be PP-complete, we show that GtMajority-kSAT is in P for k at most 3, but becomes NP-complete for k at least 4. We also show that for Majority-SAT on k-CNFs with one additional clause of arbitrary width, the problem is PP-complete for k at least 4, is NP-hard for k=3, and remains in P for k=2. These results are counterintuitive, because the “natural” classifications of these problems would have been PP-completeness, and because there is a stark difference in the complexity of GtMajority-kSAT and Majority-kSAT for all k at least 4.

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.

A line of work initiated by Fortnow in 1997 has proven model-independent time-space lower bounds for the $\mathsf{SAT}$ problem and related problems within the polynomial-time hierarchy. For example, for the $\mathsf{SAT}$ problem, the state-of-the-art is that the problem cannot be solved by random-access machines in $n^c$ time and $n^{o(1)}$ space simultaneously for $c < 2\cos(\fracπ{7}) \approx 1.801$. We extend this lower bound approach to the quantum and randomized domains. Combining Grover's algorithm with components from $\mathsf{SAT}$ time-space lower bounds, we show that there are problems verifiable in $O(n)$ time with quantum Merlin-Arthur protocols that cannot be solved in $n^c$ time and $n^{o(1)}$ space simultaneously for $c < \frac{3+\sqrt{3}}{2} \approx 2.366$, a super-quadratic time lower bound. This result and the prior work on $\mathsf{SAT}$ can both be viewed as consequences of a more general formula for time lower bounds against small-space algorithms, whose asymptotics we study in full. We also show lower bounds against randomized algorithms: there are problems verifiable in $O(n)$ time with (classical) Merlin-Arthur protocols that cannot be solved in $n^c$ randomized time and $n^{o(1)}$ space simultaneously for $c < 1.465$, improving a result of Diehl. For quantum Merlin-Arthur protocols, the lower bound in this setting can be improved to $c < 1.5$.

What sort of code is so difficult to analyze that every potential analyst can discern essentially no information from the code, other than its input-output behavior? In their seminal work on program obfuscation, Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, and Yang (CRYPTO 2001) proposed the Black-Box Hypothesis, which roughly states that every property of Boolean functions which has an efficient "analyst" and is "code independent" can also be computed by an analyst that only has black-box access to the code. In their formulation of the Black-Box Hypothesis, the "analysts" are arbitrary randomized polynomial-time algorithms, and the "codes" are general (polynomial-size) circuits. If true, the Black-Box Hypothesis would immediately imply NP ̸ ⊂ BPP. We consider generalized forms of the Black-Box Hypothesis, where the set of "codes" 𝒞 and the set of "analysts" 𝒜 may correspond to other efficient models of computation, from more restricted models such as AC⁰ to more general models such as nondeterministic circuits. We show how lower bounds of the form 𝒞 ̸ ⊂ 𝒜 often imply a corresponding Black-Box Hypothesis for those respective codes and analysts. We investigate the possibility of "complete" problems for the Black-Box Hypothesis: problems in 𝒞 such that they are not in 𝒜 if and only if their corresponding Black-Box Hypothesis is true. Along the way, we prove an equivalence: for nondeterministic circuit classes 𝒞, the "𝒞-circuit satisfiability problem" is not in 𝒜 if and only if the Black-Box Hypothesis is true for analysts in 𝒜.

We consider the canonical Subset Sum problem: given a list of positive integers a1, …, an and a target integer t with t > ai for all i, determine if there is an S ⊆ [n] such that Σi∊S ai = t. The well-known pseudopolynomialtime dynamic programming algorithm [Bellman, 1957] solves Subset Sum in O(nt) time, while requiring Ω(t) space. In this paper we present algorithms for Subset Sum with Õ(nt) running time and much lower space requirements than Bellman's algorithm, as well as that of prior work. We show that Subset Sum can be solved in Õ(nt) time and O(log(nt)) space with access to O(log n log log n + log t) random bits. This significantly improves upon the Õ(nt1+∊)-time, Õ(n log t)-space algorithm of Bringmann (SODA 2017). We also give a Õ(n1+∊t)-time, O(log(nt))-space randomized algorithm, improving upon previous (nt)O(1)-time O(log(nt))-space algorithms by Elberfeld, Jakoby, and Tantau (FOCS 2010), and Kane (2010). In addition, we also give a poly log(nt)-space, Õ(n2t)-time deterministic algorithm. We also study time-space trade-offs for Subset Sum. For parameter 1 ≤ k ≤ min{n, t}, we present a randomized algorithm running in Õ((n+t) · k) time and O((t/k) poly log(nt)) space. As an application of our results, we give an Õ(min{n2/∊, n/∊2})-time and poly log(nt)-space algorithm for “weak” ∊-approximations of Subset Sum.

We show how to solve all-pairs shortest paths on n nodes in deterministic n 3> /2> Ω ( √ log n ) time, and how to count the pairs of orthogonal vectors among n 0−1 vectors in d = c log n dimensions in deterministic n 2−1/ O (log c ) time. These running times essentially match the best known randomized algorithms of Williams [46] and Abboud, Williams, and Yu [8], respectively, and the ability to count was open even for randomized algorithms. By reductions, these two results yield faster deterministic algorithms for many other problems. Our techniques can also be used to deterministically count k -satisfiability ( k -SAT) assignments on n variable formulas in 2 n - n / O ( k ) time, roughly matching the best known running times for detecting satisfiability and resolving an open problem of Santhanam [24]. A key to our constructions is an efficient way to deterministically simulate certain probabilistic polynomials critical to the algorithms of prior work, carefully applying small-biased sets and modulus-amplifying polynomials.

All known SAT-solving paradigms (backtracking, local search, and the polynomial method) only yield a 2n(1−1/O(k)) time algorithm for solving k-SAT in the worst case, where the big-O constant is independent of k. For this reason, it has been hypothesized that k-SAT cannot be solved in worst-case 2n(1−f(k)/k) time, for any unbounded ƒ : ℕ → ℕ. This hypothesis has been called the “Super-Strong Exponential Time Hypothesis” (Super Strong ETH), modeled after the ETH and the Strong ETH. We prove two results concerning the Super-Strong ETH:1. It has also been hypothesized that k-SAT is hard to solve for randomly chosen instances near the “critical threshold”, where the clause-to-variable ratio is 2k ln 2 −Θ(1). We give a randomized algorithm which refutes the Super-Strong ETH for the case of random k-SAT and planted k-SAT for any clause-to-variable ratio. In particular, given any random k-SAT instance F with n variables and m clauses, our algorithm decides satisfiability for F in 2n(1−Ω( log k)/k) time, with high probability (over the choice of the formula and the randomness of the algorithm). It turns out that a well-known algorithm from the literature on SAT algorithms does the job: the PPZ algorithm of Paturi, Pudlak, and Zane (1998).2. The Unique k-SAT problem is the special case where there is at most one satisfying assignment. It is natural to hypothesize that the worst-case (exponential-time) complexity of Unique k-SAT is substantially less than that of k-SAT. Improving prior reductions, we show the time complexities of Unique k-SAT and k-SAT are very tightly related: if Unique k-SAT is in 2n(1−f(k)/k) time for an unbounded f, then k-SAT is in 2n(1−f(k)(1−ɛ)/k) time for every ɛ > 0. Thus, refuting Super Strong ETH in the unique solution case would refute Super Strong ETH in general.

In certain complexity-theoretic settings, it is notoriously difficult to prove complexity separations which hold almost everywhere, i.e., for all but finitely many input lengths. For example, a classical open question is whether NEXP is contained in i.o.-NP; that is, it is open whether nondeterministic exponential time computation can be simulated on infinitely many input lengths by an NP algorithm. This difficulty also applies to Williams' algorithmic method for circuit lower bounds [Williams, J. ACM 2014]. [Murray and Williams, STOC 2018] proved that nondeterminstic quasi-polynomial time is not contained in ACC^0, while it remained an open problem to show that E^NP (2^O(n) time with an NP oracle) is not contained in i.o.-ACC^0. In this paper, we show how many infinitely-often circuit lower bounds proved by the algorithmic method can be adapted to establish almost-everywhere lower bounds. First, we show there is a function f in E^NP such that, for all sufficiently large input lengths n, f cannot be (1/2+exp(-n∧e))-approximated by exp(n^e)-size ACC^0 circuits on inputs of length n (for all small e), improving lower bounds in [Chen and Ren, STOC 2020] and [Viola, ECCC 2020]. Second, we construct rigid matrices in P^NP for all but finitely many inputs, rather than infinitely often as in [Alman and Chen, FOCS 2019] and [Bhangale et al. 2020]. Third, we show there is a positive c such that E^NP has constant-error probabilistic degree at least cn/(log^2 n) for all large enough n, improving an infinitely-often separation by [Viola, ECCC 2020]. Our key to proving almost-everywhere worst-case lower bounds is a new “constructive” proof of an NTIME hierarchy theorem proved by [Fortnow and Santhanam, CCC 2016], where we show for every “weak” nondeterminstic algorithm, a “refuter algorithm” exists that can construct “bad” inputs for the hard language. We use this refuter algorithm to construct an almost-everywhere hard function. To extend our lower bounds to the average case, we prove a new XOR Lemma based on approximate linear sums, and combine it with PCP of proximity ideas developed in [Chen and Williams, CCC 2019] and [Chen and Ren, STOC 2020]. As a byproduct of our new XOR Lemma, we obtain a nondeterministic pseudorandom generator for poly-size ACC^0 circuits with seed length polylog(n), which resolves an open question in [Chen and Ren, STOC 2020].

We present a deterministic, truly subquadratic algorithm for offline (1 + ε)-approximate nearest or farthest neighbor search (in particular, the closest pair or diameter problem) in Hamming space in any dimension d ≤ nδ, for a sufficiently small constant δ > 0. The running time of the algorithm is roughly for nearest neighbors, or for farthest. The algorithm follows from a simple combination of expander walks, Chebyshev polynomials, and rectangular matrix multiplication. We also show how to eliminate errors in the previous Monte Carlo randomized algorithm of Alman, Chan, and Williams [FOCS’16] for offline approximate nearest or farthest neighbors, and obtain a Las Vegas randomized algorithm with expected running time . Finally, we note a simplification of Alman, Chan, and Williams' method and obtain a slightly improved Monte Carlo randomized algorithm with running time . As one application, we obtain improved deterministic and randomized (1 + ε)-approximation algorithms for MAX-SAT.

We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in Quasi-NP = NTIME[n^{(log n)^O(1)}] and NEXP do not have small circuits (in the worst case and/or on average) from various circuit classes C, by showing that C admits non-trivial satisfiability and/or #SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of non-trivial #SAT algorithm for a circuit class {C}. Say a symmetric Boolean function f(x₁,…,x_n) is sparse if it outputs 1 on O(1) values of ∑_i x_i. We show that for every sparse f, and for all "typical" C, faster #SAT algorithms for C circuits actually imply lower bounds against the circuit class f ∘ C, which may be stronger than C itself. In particular: - #SAT algorithms for n^k-size C-circuits running in 2ⁿ/n^k time (for all k) imply NEXP does not have f ∘ C-circuits of polynomial size. - #SAT algorithms for 2^{n^ε}-size C-circuits running in 2^{n-n^ε} time (for some ε > 0) imply Quasi-NP does not have f ∘ C-circuits of polynomial size. Applying #SAT algorithms from the literature, one immediate corollary of our results is that Quasi-NP does not have EMAJ ∘ ACC⁰ ∘ THR circuits of polynomial size, where EMAJ is the "exact majority" function, improving previous lower bounds against ACC⁰ [Williams JACM'14] and ACC⁰ ∘ THR [Williams STOC'14], [Murray-Williams STOC'18]. This is the first nontrivial lower bound against such a circuit class.

We establish several “sharp threshold” results for computational complexity. For certain tasks, we can prove a resource lower bound of n c for c ≥ 1 (or obtain an efficient circuit-analysis algorithm for n c size), there is strong intuition that a similar result can be proved for larger functions of n, yet we can also prove that replacing “n c ” with “n c+ε” in our results, for any ε > 0, would imply a breakthrough n ω(1) lower bound. We first establish such a result for Hardness Magnification. We prove (among other results) that for some c, the Minimum Circuit Size Problem for (logn) c -size circuits on length-n truth tables (MCSP[(logn) c ]) does not have n 2−o(1)-size probabilistic formulas. We also prove that an n 2+ε lower bound for MCSP[(logn) c ] (for any ε > 0 and c ≥ 1) would imply major lower bound results, such as NP does not have n k -size formulas for all k, and #SAT does not have log-depth circuits. Similar results hold for time-bounded Kolmogorov complexity. Note that cubic size lower bounds are known for probabilistic De Morgan formulas (for other functions). Next we show a sharp threshold for Quantified Derandomization (QD) of probabilistic formulas: (a) For all α, ε > 0, there is a deterministic polynomial-time algorithm that finds satisfying assignments to every probabilistic formula of n 2−2α−ε size with at most 2 n α falsifying assignments. (b) If for some α, ε > 0, there is such an algorithm for probabilistic formulas of n 2−α+ε-size and 2 n α unsatisfying assignments, then a full derandomization of NC 1 follows: a deterministic poly-time algorithm additively approximating the acceptance probability of any polynomial-size formula. Consequently, NP does not have n k -size formulas, for all k. Finally we show a sharp threshold result for Explicit Obstructions, inspired by Mulmuley’s notion of explicit obstructions from GCT. An explicit obstruction against S(n)-size formulas is a poly-time algorithm A such that A(1 n ) outputs a list {(x i ,f(x i ))} i ∈ [poly(n)] ⊆ {0,1} n × {0,1}, and every S(n)-size formula F is inconsistent with the (partially defined) function f. We prove that for all ε > 0, there is an explicit obstruction against n 2−ε-size formulas, and prove that there is an explicit obstruction against n 2+ε-size formulas for some ε > 0 if and only if there is an explicit obstruction against all polynomial-size formulas. This in turn is equivalent to the statement that E does not have 2 o(n)-size formulas, a breakthrough in circuit complexity.

We prove that if every problem in ${NP}$ has $n^k$-size circuits for a fixed constant $k$, then for every ${NP}$-verifier and every yes-instance $x$ of length $n$ for that verifier, the verifier's search space has an $n^{O(k^3)}$-size witness circuit: A witness for $x$ that can be encoded with a circuit of only $n^{O(k^3)}$ size. An analogous statement is proved for nondeterministic quasi-polynomial time, i.e., ${NQP} = {NTIME}[n^{\log^{O(1)} n}]$. This significantly extends the Easy Witness Lemma of Impagliazzo, Kabanets, and Wigderson [ J. Comput. System Sci., 65 (2002), pp. 672--694] which only held for larger nondeterministic classes such as ${NEXP}$. As a consequence, the connections between circuit-analysis algorithms and circuit lower bounds can be considerably sharpened: Algorithms for approximately counting satisfying assignments for given circuits which improve over exhaustive search can imply circuit lower bounds for functions in ${NQP}$, or even ${NP}$. To illustrate, applying known algorithms for satisfiability of ${ACC} \circ {THR}$ circuits [R. Williams, New algorithms and lower bounds for circuits with linear threshold gates, in Proceedings of the 46th Annual ACM Symposium on Theory of Computing, ACM, New York, 2014, pp. 194--202] we conclude that for every fixed $k$, ${NQP}$ does not have $n^{\log^k n}$-size ${ACC} \circ {THR}$ circuits.

A frontier open problem in circuit complexity is to prove P^{NP} is not in SIZE[n^k] for all k; this is a necessary intermediate step towards NP is not in P_{/poly}. Previously, for several classes containing P^{NP}, including NP^{NP}, ZPP^{NP}, and S_2 P, such lower bounds have been proved via Karp-Lipton-style Theorems: to prove C is not in SIZE[n^k] for all k, we show that C subset P_{/poly} implies a "collapse" D = C for some larger class D, where we already know D is not in SIZE[n^k] for all k. It seems obvious that one could take a different approach to prove circuit lower bounds for P^{NP} that does not require proving any Karp-Lipton-style theorems along the way. We show this intuition is wrong: (weak) Karp-Lipton-style theorems for P^{NP} are equivalent to fixed-polynomial size circuit lower bounds for P^{NP}. That is, P^{NP} is not in SIZE[n^k] for all k if and only if (NP subset P_{/poly} implies PH subset i.o.- P^{NP}_{/n}). Next, we present new consequences of the assumption NP subset P_{/poly}, towards proving similar results for NP circuit lower bounds. We show that under the assumption, fixed-polynomial circuit lower bounds for NP, nondeterministic polynomial-time derandomizations, and various fixed-polynomial time simulations of NP are all equivalent. Applying this equivalence, we show that circuit lower bounds for NP imply better Karp-Lipton collapses. That is, if NP is not in SIZE[n^k] for all k, then for all C in {Parity-P, PP, PSPACE, EXP}, C subset P_{/poly} implies C subset i.o.-NP_{/n^epsilon} for all epsilon > 0. Note that unconditionally, the collapses are only to MA and not NP. We also explore consequences of circuit lower bounds for a sparse language in NP. Among other results, we show if a polynomially-sparse NP language does not have n^{1+epsilon}-size circuits, then MA subset i.o.-NP_{/O(log n)}, MA subset i.o.-P^{NP[O(log n)]}, and NEXP is not in SIZE[2^{o(m)}]. Finally, we observe connections between these results and the "hardness magnification" phenomena described in recent works.

We considerably sharpen the known connections between circuit-analysis algorithms and circuit lower bounds, show intriguing equivalences between the analysis of weak circuits and (apparently difficult) circuits, and provide strong new lower bounds for approximately computing Boolean functions with depth-two neural networks and related models. - We develop approaches to proving THR o THR lower bounds (a notorious open problem), by connecting algorithmic analysis of THR o THR to the provably weaker circuit classes THR o MAJ and MAJ o MAJ, where exponential lower bounds have long been known. More precisely, we show equivalences between algorithmic analysis of THR o THR and these weaker classes. The epsilon-error CAPP problem asks to approximate the acceptance probability of a given circuit to within additive error epsilon; it is the "canonical" derandomization problem. We show: - There is a non-trivial (2^n/n^{omega(1)} time) 1/poly(n)-error CAPP algorithm for poly(n)-size THR o THR circuits if and only if there is such an algorithm for poly(n)-size MAJ o MAJ. - There is a delta > 0 and a non-trivial SAT (delta-error CAPP) algorithm for poly(n)-size THR o THR circuits if and only if there is such an algorithm for poly(n)-size THR o MAJ. Similar results hold for depth-d linear threshold circuits and depth-d MAJORITY circuits. These equivalences are proved via new simulations of THR circuits by circuits with MAJ gates. - We strengthen the connection between non-trivial derandomization (non-trivial CAPP algorithms) for a circuit class C, and circuit lower bounds against C. Previously, [Ben-Sasson and Viola, ICALP 2014] (following [Williams, STOC 2010]) showed that for any polynomial-size class C closed under projections, non-trivial (2^{n}/n^{omega(1)} time) CAPP for OR_{poly(n)} o AND_{3} o C yields NEXP does not have C circuits. We apply Probabilistic Checkable Proofs of Proximity in a new way to show it would suffice to have a non-trivial CAPP algorithm for either XOR_2 o C, AND_2 o C or OR_2 o C. - A direct corollary of the first two bullets is that NEXP does not have THR o THR circuits would follow from either: - a non-trivial delta-error CAPP (or SAT) algorithm for poly(n)-size THR o MAJ circuits, or - a non-trivial 1/poly(n)-error CAPP algorithm for poly(n)-size MAJ o MAJ circuits. - Applying the above machinery, we extend lower bounds for depth-two neural networks and related models [R. Williams, CCC 2018] to weak approximate computations of Boolean functions. For example, for arbitrarily small epsilon > 0, we prove there are Boolean functions f computable in nondeterministic n^{log n} time such that (for infinitely many n) every polynomial-size depth-two neural network N on n inputs (with sign or ReLU activation) must satisfy max_{x in {0,1}^n}|N(x)-f(x)|>1/2-epsilon. That is, short linear combinations of ReLU gates fail miserably at computing f to within close precision. Similar results are proved for linear combinations of ACC o THR circuits, and linear combinations of low-degree F_p polynomials. These results constitute further progress towards THR o THR lower bounds.

In the Minimum Circuit Size Problem (MCSP[s(m)]), we ask if there is a circuit of size s(m) computing a given truth-table of length n = 2m. Recently, a surprising phenomenon termed as hardness magnification by [Oliveira and Santhanam, FOCS 2018] was discovered for MCSP[s(m)] and the related problem MKtP of computing time-bounded Kolmogorov complexity. In [Oliveira and Santhanam, FOCS 2018], [Oliveira, Pich, and Santhanam, CCC 2019], and [McKay, Murray, and Williams, STOC 2019], it was shown that minor (n1+ε-style) lower bounds for MCSP[2o(m)] or MKtP[2o(m)] would imply breakthrough circuit lower bounds such as NP⊄P/poly, NP⊄NC1, or EXP⊄P/poly. We consider the question: What is so special about MCSP and MKtP? Why do they admit this striking phenomenon? One simple property is that all variants of MCSP (and MKtP) considered in prior work are sparse languages. For example, MCSP[s(m)] has 2Õ(s(m))yes-instances of length n = 2m, so MCSP[2o(m)] is 2no(1)-sparse. We show that there is a hardness magnification phenomenon for all equally-sparse NP languages. Formally, suppose there is an ε > 0 and a language L ∈ NP which is 2no(1)-sparse, and L ∈/ Circuit[n1+ε]. Then NP does not have nk-size circuits for all k. We prove analogous theorems for De Morgan formulas, B2-formulas, branching programs, AC0[6] and TC0circuits, and more: improving the state of the art in NP lower bounds against any of these models by an ε factor in the exponent would already imply NP lower bounds for all fixed polynomials. In fact, in our proofs it is not necessary to prove a (say) n1+εcircuit size lower bound for L: one only has to prove a lower bound against n1+ε-time nε-space deterministic algorithms with nεadvice bits. Such lower bounds are well-known for non-sparse problems. Building on our techniques, we also show interesting new hardness magnifications for search-MCSP and search-MKtP (where one must output small circuits or short representations of strings), showing consequences such as ⊕P (or PP, PSPACE, and EXP) is not contained in P/poly (or NC1, AC0[6], or branching programs of polynomial size). For instance, if there is an ε > 0 such that search-MCSP[2βm] does not have De Morgan formulas of size n3+εfor all constants ß > 0, then ⊕P⊄NC1.

We show that the permanent of an n x n matrix over any finite ring of r <= n elements can be computed with a deterministic 2^{n-Omega(n/r)} time algorithm. This improves on a Las Vegas algorithm running in expected 2^{n-Omega(n/(r log r))} time, implicit in [Björklund, Husfeldt, and Lyckberg, IPL 2017]. For the permanent over the integers of a 0/1-matrix with exactly d ones per row and column, we provide a deterministic 2^{n-Omega(n/(d^{3/4)})} time algorithm. This improves on a 2^{n-Omega(n/d)} time algorithm in [Cygan and Pilipczuk ICALP 2013]. We also show that the number of Hamiltonian cycles in an n-vertex directed graph of average degree delta can be computed by a deterministic 2^{n-Omega(n/(delta))} time algorithm. This improves on a Las Vegas algorithm running in expected 2^{n-Omega(n/poly(delta))} time in [Björklund, Kaski, and Koutis, ICALP 2017]. A key tool in our approach is a reduction from computing the permanent to listing pairs of dissimilar vectors from two sets of vectors, i.e., vectors over a finite set that differ in each coordinate, building on an observation of [Bax and Franklin, Algorithmica 2002]. We propose algorithms that can be used both to derandomise the construction of Bax and Franklin, and efficiently list dissimilar pairs using several algorithmic tools. We also give a simple randomised algorithm resulting in Monte Carlo algorithms within the same time bounds. Our new fast algorithms for listing dissimilar vector pairs from two sets of vectors are inspired by recent algorithms for detecting and counting orthogonal vectors by [Abboud, Williams, and Yu, SODA 2015] and [Chan and Williams, SODA 2016].

We consider the problem of finding solutions to systems of polynomial equations over a finite field. Lokshtanov et al. [SODA'17] recently obtained the first worst-case algorithms that beat exhaustive search for this problem. In particular for degree-d equations modulo two in n variables, they gave an O^*(2^{(1-1/(5d))n}) time algorithm, and for the special case d=2 they gave an O^*(2^{0.876n}) time algorithm. We modify their approach in a way that improves these running times to O^*(2^{(1-1/(2.7d))n}) and O^*{2^{0.804n}), respectively. In particular, our latter bound - that holds for all systems of quadratic equations modulo 2 - comes close to the O^*(2^{0.792n}) expected time bound of an algorithm empirically found to hold for random equation systems in Bardet et al. [J. Complexity, 2013]. Our improvement involves three observations: 1) The Valiant-Vazirani lemma can be used to reduce the solution-finding problem to that of counting solutions modulo 2. 2) The monomials in the probabilistic polynomials used in this solution-counting modulo 2 have a special form that we exploit to obtain better bounds on their number than in Lokshtanov et al. [SODA'17]. 3) The problem of solution-counting modulo 2 can be "embedded" in a smaller instance of the original problem, which enables us to apply the algorithm as a subroutine to itself.

Finding important nodes in a graph and measuring their importance is a fundamental problem in the analysis of social networks, transportation networks, biological systems, etc. Among popular such metrics are graph centrality, betweenness centrality (BC), and reach centrality (RC). These measures are also very related to classic notions like diameter and radius. Roditty and Vassilevska Williams~[STOC'13] showed that no algorithm can compute a (3/2-δ)-approximation of the diameter in sparse and unweighted graphs faster that n^{2-o(1)} time unless the widely believed strong exponential time hypothesis (SETH) is false. Abboud et al.~[SODA'15] and [SODA'16] further analyzed these problems under the recent line of research on hardness in P. They showed that in sparse and unweighted graphs (weighted for BC) none of these problems can be solved faster than n^{2-o(1)} unless some popular conjecture is false. Furthermore they ruled out a (2-δ)-approximation for RC, a (3/2-δ)-approximation for Radius and a (5/3-δ)-approximation for computing all eccentricities of a graph for any δ> 0. We extend these results to the case of unweighted graphs with constant maximum degree. Through new graph constructions we are able to obtain the same approximation and time bounds as for sparse graphs even in unweighted bounded-degree graphs. We show that no (3/2-δ) approximation of Radius or Diameter, (2-δ)-approximation of RC, (5/3-δ)-approximation of all eccentricities or exact algorithm for BC exists in time n^{2-o(1)} for such graphs and any δ> 0. This strengthens the result for BC of Abboud et al.~[SODA'16] by showing a hardness result for unweighted graphs, and follows in the footsteps of Abboud et al.~[SODA'16] and Abboud and Dahlgaard~[FOCS'16] in showing conditional lower bounds for restricted but realistic graph classes.

We define a model of size-S R-way branching programs with oracles that can make up to S distinct oracle queries over all of their possible inputs, and generalize a lower bound proof strategy of Beame [SICOMP 1991] to apply in the case of random oracles. Through a series of succinct reductions, we prove that the following problems require randomized algorithms where the product of running time and space usage must be Omega(n^2/poly(log n)) to obtain correct answers with constant nonzero probability, even for algorithms with constant-time access to a uniform random oracle (i.e., a uniform random hash function): - Given an unordered list L of n elements from [n] (possibly with repeated elements), output [n]-L. - Counting satisfying assignments to a given 2CNF, and printing any satisfying assignment to a given 3CNF. Note it is a major open problem to prove a time-space product lower bound of n^{2-o(1)} for the decision version of SAT, or even for the decision problem Majority-SAT. - Printing the truth table of a given CNF formula F with k inputs and n=O(2^k) clauses, with values printed in lexicographical order (i.e., F(0^k), F(0^{k-1}1), ..., F(1^k)). Thus we have a 4^k/poly(k) lower bound in this case. - Evaluating a circuit with n inputs and O(n) outputs. As our lower bounds are based on R-way branching programs, they hold for any reasonable model of computation (e.g. log-word RAMs and multitape Turing machines).

The Orthogonal Vectors problem (OV) asks: given n vectors in {0, 1}O(log n), are two of them orthogonal? OV is easily solved in O(n2 log n) time, and it is a central problem in fine-grained complexity: dozens of conditional lower bounds are based on the popular hypothesis that OV cannot be solved in (say) n1.99 time. However, unlike the APSP problem, few other problems are known to be non-trivially equivalent to OV. We show OV is truly-subquadratic equivalent to several fundamental problems, all of which (a priori) look harder than OV. A partial list is given below: 1. (Min-IP/Max-IP) Find a red-blue pair of vectors with minimum (respectively, maximum) inner product, among n vectors in {0, 1}O(log n). 2. (Exact-IP) Find a red-blue pair of vectors with inner product equal to a given target integer, among n vectors in {0, 1}O(log n). 3. (Apx-Min-IP/Apx-Max-IP) Find a red-blue pair of vectors that is a 100-approximation to the minimum (resp. maximum) inner product, among n vectors in {0, l}O(log n). 4. (Approximate Bichrom.-ℓp-Closest-Pair) Compute a (1+ Ω(1))-approximation to the ℓp-closest red-blue pair (for a constant p ∊ [1, 2]), among n points in ℝ, d ≤ no(1). 5. (Approximate ℓp-Furthest-Pair) Compute a (1 + Ω(1))-approximation to the ℓp-furthest pair (for a constant p ∊ [1, 2]), among n points in ℝ, d ≤ no(1). Therefore, quick constant-factor approximations to maximum inner product imply quick exact solutions to maximum inner product, in the O(log n)-dimensional setting. Another consequence is that the ability to find vectors with zero inner product suffices for finding vectors with maximum inner product. Our equivalence results are robust enough that they continue to hold in the data structure setting. In particular, we show that there is a poly(n) space, n1–ε query time data structure for Partial Match with vectors from {0, 1}O(log n) if and only if such a data structure exists for 1 + Ω(1) Approximate Nearest Neighbor Search in Euclidean space. To establish the equivalences, we introduce two general frameworks for reductions to OV: one based on ∑2 communication protocols, and another based on locality-sensitive hashing families. In addition, we obtain an n2–1/O(log c) time algorithm for Apx-Min-IP with n vectors from {0, 1}c log n, matching state-of-the-art algorithms for OV and Apx-Max-IP. As an application, we obtain a faster algorithm for approximating “almost solvable” MAX-SAT instances.

The Minimum Circuit Size Problem (MCSP) asks to determine the minimum size of a circuit computing a given truth table. MCSP is a natural and powerful string compression problem using bounded-size circuits. Recently, Oliveira and Santhanam [FOCS 2018] and Oliveira, Pich, and Santhanam [ECCC 2018] demonstrated a “hardness magnification” phenomenon for MCSP in restricted settings. Letting MCSP[s(n)] be the problem of deciding if a truth table of length 2n has circuit complexity at most s(n), they proved that small (fixed-polynomial) average case circuit/formula lower bounds for MCSP[2√n], or lower bounds for approximating MCSP[2o(n)], would imply major separations such as NP ⊄BPP and NP ⊄P/poly.

We present two new data structures for computing values of an n-variate polynomial P of degree at most d over a finite field of q elements. Assuming that d divides $$q-1$$ , our first data structure relies on $$(d+1)^{n+2}$$ tabulated values of P to produce the value of P at any of the $$q^n$$ points using $$O(nqd^2)$$ arithmetic operations in the finite field. Assuming that s divides d and d / s divides $$q-1$$ , our second data structure assumes that P satisfies a degree-separability condition and relies on $$(d/s+1)^{n+s}$$ tabulated values to produce the value of P at any point using $$O\left( nq^ssq\right) $$ arithmetic operations. Our data structures are based on generalizing upper-bound constructions due to Mockenhaupt and Tao (Duke Math J 121(1):35–74, 2004), Saraf and Sudan (Anal PDE 1(3):375–379, 2008) and Dvir (Incidence theorems and their applications, 2012. arXiv:1208.5073 ) for Kakeya sets in finite vector spaces from linear to higher-degree polynomial curves. As an application we show that the new data structures enable a faster algorithm for computing integer-valued fermionants, a family of self-reducible polynomial functions introduced by Chandrasekharan and Wiese (Partition functions of strongly correlated electron systems as fermionants, 2011. arXiv:1108.2461v1 ) that captures numerous fundamental algebraic and combinatorial functions such as the determinant, the permanent, the number of Hamiltonian cycles in a directed multigraph, as well as certain partition functions of strongly correlated electron systems in statistical physics. In particular, a corollary of our main theorem for fermionants is that the permanent of an $$m\times m$$ integer matrix with entries bounded in absolute value by a constant can be computed in time $$2^{m-\Omega \left( \sqrt{m/\log \log m}\right) }$$ , improving an earlier algorithm of Björklund (in: Proceedings of the 15th SWAT, vol 17, pp 1–11, 2016) that runs in time $$2^{m-\Omega \left( \sqrt{m/\log m}\right) }$$ .

Properties definable in first-order logic are algorithmically interesting for both theoretical and pragmatic reasons. Many of the most studied algorithmic problems, such as Hitting Set and Orthogonal Vectors, are first-order, and the first-order properties naturally arise as relational database queries. A relatively straightforward algorithm for evaluating a property with k +1 quantifiers takes time O ( m k ) and, assuming the Strong Exponential Time Hypothesis (SETH), some such properties require O ( m k −ϵ) time for any ϵ > 0. (Here, > m represents the size of the input structure, i.e., the number of tuples in all relations.) We give algorithms for every first-order property that improves this upper bound to m k /2 Θ (√ log n ) , i.e., an improvement by a factor more than any poly-log, but less than the polynomial required to refute SETH. Moreover, we show that further improvement is equivalent to improving algorithms for sparse instances of the well-studied Orthogonal Vectors problem. Surprisingly, both results are obtained by showing completeness of the Sparse Orthogonal Vectors problem for the class of first-order properties under fine-grained reductions. To obtain improved algorithms, we apply the fast Orthogonal Vectors algorithm of References [3, 16]. While fine-grained reductions (reductions that closely preserve the conjectured complexities of problems) have been used to relate the hardness of disparate specific problems both within P and beyond, this is the first such completeness result for a standard complexity class.

Motivated by the resurgence of neural networks in being able to solve complex learning tasks we undertake a study of high depth networks using ReLU gates which implement the function $x \mapsto \max\{0,x\}$. We try to understand the role of depth in such neural networks by showing size lowerbounds against such network architectures in parameter regimes hitherto unexplored. In particular we show the following two main results about neural nets computing Boolean functions of input dimension $n$, 1. We use the method of random restrictions to show almost linear, $Ω(ε^{2(1-δ)}n^{1-δ})$, lower bound for completely weight unrestricted LTF-of-ReLU circuits to match the Andreev function on at least $\frac{1}{2} +ε$ fraction of the inputs for $ε> \sqrt{2\frac{\log^{\frac {2}{2-δ}}(n)}{n}}$ for any $δ\in (0,\frac 1 2)$ 2. We use the method of sign-rank to show exponential in dimension lower bounds for ReLU circuits ending in a LTF gate and of depths upto $O(n^ξ)$ with $ξ< \frac{1}{8}$ with some restrictions on the weights in the bottom most layer. All other weights in these circuits are kept unrestricted. This in turns also implies the same lowerbounds for LTF circuits with the same architecture and the same weight restrictions on their bottom most layer. Along the way we also show that there exists a $\mathbb{R}^ n\rightarrow \mathbb{R}$ Sum-of-ReLU-of-ReLU function which Sum-of-ReLU neural nets can never represent no matter how large they are allowed to be.

In 2010, the author proposed a program for proving lower bounds in circuit complexity, via faster algorithms for circuit satisfiability and related problems. This talk will give an overview of how the program works, report on the successes of this program so far, and outline open frontiers that have yet to be resolved.

Fine-grained reductions have established equivalences between many core problems with Õ(n3)-time algorithms on n-node weighted graphs, such as Shortest Cycle, All-Pairs Shortest Paths (APSP), Radius, Replacement Paths, Second Shortest Paths, and so on. These problems also have Õ(mn)-time algorithms on m-edge n-node weighted graphs, and such algorithms have wider applicability. Are these mn bounds optimal when m << n2? Starting from the hypothesis that the minimum weight (2ℓ + 1)-Clique problem in edge weighted graphs requires n2ℓ+1–o(1) time, we prove that for all sparsities of the form m = Θ(n1+1/ℓ), there is no O(n2 + mn1–ε) time algorithm for ε > 0 for any of the below problems • Minimum Weight (2ℓ + 1)-Cycle in a directed weighted graph, • Shortest Cycle in a directed weighted graph, • APSP in a directed or undirected weighted graph, • Radius (or Eccentricities) in a directed or undirected weighted graph, • Wiener index of a directed or undirected weighted graph, • Replacement Paths in a directed weighted graph, • Second Shortest Path in a directed weighted graph, • Betweenness Centrality of a given node in a directed weighted graph. That is, we prove hardness for a variety of sparse graph problems from the hardness of a dense graph problem. Our results also lead to new conditional lower bounds from several related hypothesis for unweighted sparse graph problems including k-cycle, shortest cycle, Radius, Wiener index and APSP.

Point location problems for n points in d-dimensional Euclidean space (and ℓp spaces more generally) have typically had two kinds of running-time solutions: (Nearly-Linear) less than dpo1y(d) · n logO(d) n time, or (Barely-Subquadratic) f(d) · n2–1/Θ(d) time, for various f. For small d and large n, “nearly-linear” running times are generally feasible, while the “barely-subquadratic” times are generally infeasible, requiring essentially quadratic time. For example, in the Euclidean metric, finding a Closest Pair among n points in ℝd is nearly-linear, solvable in 2O(d). n logO(1) n time, while the known algorithms for finding a Furthest Pair (the diameter of the point set) are only barely-subquadratic, requiring Ω(n2–1/Θ(d)) time. Why do these proximity problems have such different time complexities? Is there a barrier to obtaining nearly-linear algorithms for problems which are currently only barely-subquadratic? We give a novel exact and deterministic self-reduction for the Orthogonal Vectors problem on n vectors in {0, 1}d to n vectors in ℤω(log d) that runs in 2o(d) time. As a consequence, barely-subquadratic problems such as Euclidean diameter, Euclidean bichromatic closest pair, and incidence detection do not have O(n2–∊) time algorithms (in Turing models of computation) for dimensionality d = ω(log log n)2, unless the popular Orthogonal Vectors Conjecture and the Strong Exponential Time Hypothesis are false. That is, while the poly-log-log-dimensional case of Closest Pair is solvable in n1+o(1) time, the poly-log-log-dimensional case of Furthest Pair can encode difficult large-dimensional problems conjectured to require n2–o(1) time. We also show that the All-Nearest Neighbors problem in ω(log n) dimensions requires n2–o(1) time to solve, assuming either of the above conjectures.

We prove that if every problem in NP has nk-size circuits for a fixed constant k, then for every NP-verifier and every yes-instance x of length n for that verifier, the verifier’s search space has an nO(k3)-size witness circuit: a witness for x that can be encoded with a circuit of only nO(k3) size. An analogous statement is proved for nondeterministic quasi-polynomial time, i.e., NQP = NTIME[nlogO(1) n]. This significantly extends the Easy Witness Lemma of Impagliazzo, Kabanets, and Wigderson [JCSS’02] which only held for larger nondeterministic classes such as NEXP.

We say an algorithm on n × n matrices with integer entries in [− M , M ] (or n -node graphs with edge weights from [− M , M ]) is truly subcubic if it runs in O ( n 3 − δ ċ poly(log M )) time for some δ > 0. We define a notion of subcubic reducibility and show that many important problems on graphs and matrices solvable in O ( n 3 ) time are equivalent under subcubic reductions. Namely, the following weighted problems either all have truly subcubic algorithms, or none of them do: •The all-pairs shortest paths problem on weighted digraphs (APSP). •Detecting if a weighted graph has a triangle of negative total edge weight. •Listing up to n 2.99 negative triangles in an edge-weighted graph. •Finding a minimum weight cycle in a graph of non-negative edge weights. •The replacement paths problem on weighted digraphs. •Finding the second shortest simple path between two nodes in a weighted digraph. •Checking whether a given matrix defines a metric. •Verifying the correctness of a matrix product over the (min, +)-semiring. •Finding a maximum subarray in a given matrix. Therefore, if APSP cannot be solved in n 3−ε time for any ε > 0, then many other problems also need essentially cubic time. In fact, we show generic equivalences between matrix products over a large class of algebraic structures used in optimization, verifying a matrix product over the same structure, and corresponding triangle detection problems over the structure. These equivalences simplify prior work on subcubic algorithms for all-pairs path problems, since it now suffices to give appropriate subcubic triangle detection algorithms. Other consequences of our work are new combinatorial approaches to Boolean matrix multiplication over the (OR,AND)-semiring (abbreviated as BMM). We show that practical advances in triangle detection would imply practical BMM algorithms, among other results. Building on our techniques, we give two improved BMM algorithms: a derandomization of the combinatorial BMM algorithm of Bansal and Williams (FOCS’09), and an improved quantum algorithm for BMM.

We present a new randomized method for computing the min-plus product (a.k.a., tropical product) of two $n \times n$ matrices, yielding a faster algorithm for solving the all-pairs shortest path problem (APSP) in dense $n$-node directed graphs with arbitrary edge weights. On the real RAM, where additions and comparisons of reals are unit cost (but all other operations have typical logarithmic cost), the algorithm runs in time $\frac{n^3}{2^{\Omega(\log n)^{1/2}}}$ and is correct with high probability. On the word RAM with wordsize $\log(n)$, the algorithm runs in $n^3/2^{\Omega(\log n)^{1/2}} + n^{2+o(1)}\log(nM)$ time for edge weights in $([0,M] \cap \mathbb{Z})\cup\{\infty\}$. Prior algorithms took either $O(n^3/\log^c n)$ time for various $c \leq 2$, or $O(M^{\alpha}n^{\beta})$ time for various $\alpha > 0$ and $\beta > 2$. The new algorithm applies a tool from circuit complexity, namely the Razborov--Smolensky polynomials for approximately representing ${\sf AC}^0[p]$ circuits, to efficiently reduce a matrix product over the $(\min,+)$ algebra to a relatively small number of rectangular matrix products over $\mathbb{F}_2$, each of which is computable using a particularly efficient method due to Coppersmith. We also give a deterministic version of the algorithm running in $n^3/2^{\log^{\delta} n}$ time for some $\delta > 0$, which utilizes the Yao--Beigel--Tarui translation of ${\sf AC}^0[m]$ circuits into “nice” depth-two circuits.

We present a new distributed model of probabilistically checkable proofs (PCP). A satisfying assignment x ∈ {0, 1}nto a CNF formula φ is shared between two parties, where Alice knows x1, ... , xn/2, Bob knows xn/2+1, . . . , xn, and both parties know φ. The goal is to have Alice and Bob jointly write a PCP that x satisfies φ, while exchanging little or no information. Unfortunately, this model as-is does not allow for nontrivial query complexity. Instead, we focus on a non-deterministic variant, where the players are helped by Merlin, a third party who knows all of x. Using our framework, we obtain, for the first time, PCP-like reductions from the Strong Exponential Time Hypothesis (SETH) to approximation problems in P. In particular, under SETH we show that there are no trulysubquadratic approximation algorithms for Maximum Inner Product over {0, 1}-vectors, LCS Closest Pair over permutations, Approximate Partial Match, Approximate Regular Expression Matching, and Diameter in Product Metric. All our inapproximability factors are nearly-tight. In particular, for the first three problems we obtain nearly-polynomial factors of 2(log n)1-o(1); only (1+o(1))-factor lower bounds (under SETH) were known before. As an additional feature of our reduction, we obtain new SETH lower bounds for the exact “monochromatic” Closest Pair problem in the Euclidean, Manhattan, and Hamming metrics.

We present two new data structures for computing values of an n-variate polynomial P of degree at most d over a finite field of q elements. Assuming that d divides q-1, our first data structure relies on (d+1)^{n+2} tabulated values of P to produce the value of P at any of the q^n points using O(nqd^2) arithmetic operations in the finite field. Assuming that s divides d and d/s divides q-1, our second data structure assumes that P satisfies a degree-separability condition and relies on (d/s+1)^{n+s} tabulated values to produce the value of P at any point using O(nq^ssq) arithmetic operations. Our data structures are based on generalizing upper-bound constructions due to Mockenhaupt and Tao (2004), Saraf and Sudan (2008), and Dvir (2009) for Kakeya sets in finite vector spaces from linear to higher-degree polynomial curves. As an application we show that the new data structures enable a faster algorithm for computing integer-valued fermionants, a family of self-reducible polynomial functions introduced by Chandrasekharan and Wiese (2011) that captures numerous fundamental algebraic and combinatorial invariants such as the determinant, the permanent, the number of Hamiltonian cycles in a directed multigraph, as well as certain partition functions of strongly correlated electron systems in statistical physics. In particular, a corollary of our main theorem for fermionants is that the permanent of an m-by-m integer matrix with entries bounded in absolute value by a constant can be computed in time 2^{m-Omega(sqrt(m/log log m))}, improving an earlier algorithm of Bjorklund (2016) that runs in time 2^{m-Omega(sqrt(m/log m))}.

Properties definable in first-order logic are algorithmically interesting for both theoretical and pragmatic reasons. Many of the most studied algorithmic problems, such as Hitting Set and Orthogonal Vectors, are first-order, and the first-order properties naturally arise as relational database queries. A relatively straightforward algorithm for evaluating a property with k + 1 quantifiers takes time O(mk) and, assuming the Strong Exponential Time Hypothesis (SETH), some such properties require O(mk-∊) time for any ∊ > 0. (Here, m represents the size of the input structure, i.e. the number of tuples in all relations.) We give algorithms for every first-order property that improves this upper bound to i.e., an improvement by a factor more than any poly-log, but less than the polynomial required to refute SETH. Moreover, we show that further improvement is equivalent to improving algorithms for sparse instances of the well-studied Orthogonal Vectors problem. Surprisingly, both results are obtained by showing completeness of the Sparse Orthogonal Vectors problem for the class of first-order properties under fine-grained reductions. To obtain improved algorithms, we apply the fast Orthogonal Vectors algorithm of [3, 16]. While fine-grained reductions (reductions that closely preserve the conjectured complexities of problems) have been used to relate the hardness of disparate specific problems both within P and beyond, this is the first such completeness result for a standard complexity class.

We consider the Online Boolean Matrix-Vector Multiplication (OMV) problem studied by Henzinger et al. [STOC'15]: given an n × n Boolean matrix M, we receive n Boolean vectors v1,…, vn one at a time, and are required to output Mvi (over the Boolean semiring) before seeing the vector vi+1, for all i. Previous known algorithms for this problem are combinatorial, running in O(n3/log2 n) time. Henzinger et al. conjecture there is no O(n3-∊) time algorithm for OMV, for all ∊ > 0; their OMV conjecture is shown to imply strong hardness results for many basic dynamic problems. We give a substantially faster method for computing OMV, running in randomized time. In fact, after seeing vectors, we already achieve amortized time for matrix-vector multiplication. Our approach gives a way to reduce matrix-vector multiplication to solving a version of the Orthogonal Vectors problem, which in turn reduces to “small” algebraic matrix-matrix multiplication. Applications include faster independent set detection, partial match retrieval, and 2-CNF evaluation. We also show how a modification of our method gives a cell probe data structure for OMV with worst case time per query vector, where w is the word size. This result rules out an unconditional proof of the OMV conjecture using purely information-theoretic arguments.

We consider the problem of solving systems of multivariate polynomial equations of degree k over a finite field. For every integer k ≤ 2 and finite field q where q = pd for a prime p, we give, to the best of our knowledge, the first algorithms that achieve an exponential speedup over the brute force O(qn) time algorithm in the worst case. We present two algorithms, a randomized algorithm with running time qn+o(n) · q−n/O(k) time if q < 24ekd, and otherwise, where e = 2.718… is Napier's constant, and a deterministic algorithm for counting solutions with running time qn+o(n) · q−n/O(kq6/7d). For the important special case of quadratic equations in F2, our randomized algorithm has running time O(20.8765n). For systems over 2 we also consider the case where the input polynomials do not have bounded degree, but instead can be efficiently represented as a ΣΠΣ circuit, i.e., a sum of products of sums of variables. For this case we present a deterministic algorithm running in time 2n-dn for δ = 1/O(log(s/n)) for instances with s product gates in total and n variables. Our algorithms adapt several techniques recently developed via the polynomial method from circuit complexity. The algorithm for systems of ΣΠΣ polynomials also introduces a new degree reduction method that takes an instance of the problem and outputs a subexponential-sized set of instances, in such a way that feasibility is preserved and every polynomial among the output instances has degree O(log(s/n)).

We consider a notion of probabilistic rank and probabilistic sign-rank of a matrix, which measure the extent to which a matrix can be probabilistically represented by low-rank matrices. We demonstrate several connections with matrix rigidity, communication complexity, and circuit lower bounds. The most interesting outcomes are:

We present an efficient proof system for Multipoint Arithmetic Circuit Evaluation: for every arithmetic circuit C(x_1,...,x_n) of size s and degree d over a field F, and any inputs a_1,...,a_K in F}^n, - the Prover sends the Verifier the values C(a_1), ..., C(a_K) in F and a proof of ~O(K * d) length, and - the Verifier tosses poly(log(dK|F|epsilon)) coins and can check the proof in about ~O}(K * (n + d) + s) time, with probability of error less than epsilon. For small degree d, this "Merlin-Arthur" proof system (a.k.a. MA-proof system) runs in nearly-linear time, and has many applications. For example, we obtain MA-proof systems that run in c^{n} time (for various c < 2) for the Permanent, #Circuit-SAT for all sublinear-depth circuits, counting Hamiltonian cycles, and infeasibility of 0-1 linear programs. In general, the value of any polynomial in Valiant's class VP can be certified faster than "exhaustive summation" over all possible assignments. These results strongly refute a Merlin-Arthur Strong ETH and Arthur-Merlin Strong ETH posed by Russell Impagliazzo and others. We also give a three-round (AMA) proof system for quantified Boolean formulas running in 2^{2n/3+o(n)} time, nearly-linear time MA-proof systems for counting orthogonal vectors in a collection and finding Closest Pairs in the Hamming metric, and a MA-proof system running in n^{k/2+O(1)}-time for counting k-cliques in graphs. We point to some potential future directions for refuting the Nondeterministic Strong ETH.

We design new polynomials for representing threshold functions in three different regimes: probabilistic polynomials of low degree, which need far less randomness than previous constructions, polynomial threshold functions (PTFs) with "nice" threshold behavior and degree almost as low as the probabilistic polynomials, and a new notion of probabilistic PTFs where we combine the above techniques to achieve even lower degree with similar "nice" threshold behavior. Utilizing these polynomial constructions, we design faster algorithms for a variety of problems: · Offline Hamming Nearest (and Furthest) Neighbors: Given n red and n blue points in d-dimensional Hamming space for d = c log n, we can find an (exact) nearest (or furthest) blue neighbor for every red point in randomized time n2-1/O(√clog2/3c) or deterministic time n2-1/O(c log2 c). These improve on a randomized n2-1/O(c log2 c)bound by Alman and Williams (FOCS'15), and also lead to faster MAX-SAT algorithms for sparse CNFs. · Offline Approximate Nearest (and Furthest) Neighbors: Given n red and n blue points in d-dimensional ℓ1or Euclidean space, we can find a (1+ε)-approximate nearest (or furthest) blue neighbor for each red point in randomized time near dn+n2-Ω(ε1/3/log(1/ε)). This improves on an algorithm by Valiant (FOCS'12) with randomized time near dn+n2-Ω(√ε), which in turn improves previous methods based on locality-sensitive hashing. · SAT Algorithms and Lower Bounds for Circuits With Linear Threshold Functions: We give a satisfiability algorithm for AC0[m] o LTF LTF circuits with a subquadratic number of LTF gates on the bottom layer, and a subexponential number of gates on the other layers, that runs in deterministic 2n-nεtime. This strictly generalizes a SAT algorithm for ACC0oLTF circuits of subexponential size by Williams (STOC'14) and also implies new circuit lower bounds for threshold circuits, improving a recent gate lower bound of Kane and Williams (STOC'16). We also give a randomized 2n-nε-time SAT algorithm for subexponential-size MAJ o AC0oLTF o AC0oLTF circuits, where the top MAJ gate and middle LTF gates have O(n6/5-δ) fan-in.

Given a set of numbers, the k-SUM problem asks for a subset of k numbers that sums to zero. When the numbers are integers, the time and space complexity of k-SUM is generally studied in the word-RAM model; when the numbers are reals, the complexity is studied in the real-RAM model, and space is measured by the number of reals held in memory at any point. We present a time and space efficient deterministic self-reduction for the k-SUM problem which holds for both models, and has many interesting consequences. To illustrate: - 3-SUM is in deterministic time O(n^2*lg(lg(n))/lg(n)) and space O(sqrt(n*lg(n)/lg(lg(n)))). In general, any polylogarithmic-time improvement over quadratic time for 3-SUM can be converted into an algorithm with an identical time improvement but low space complexity as well. - 3-SUM is in deterministic time O(n^2) and space O(sqrt(n)), derandomizing an algorithm of Wang. - A popular conjecture states that 3-SUM requires n^{2-o(1)} time on the word-RAM. We show that the 3-SUM Conjecture is in fact equivalent to the (seemingly weaker) conjecture that every O(n^{.51})-space algorithm for 3-SUM requires at least n^{2-o(1)} time on the word-RAM. - For k >= 4, k-SUM is in deterministic O(n^{k-2+2/k}) time and O(sqrt(n)) space.

We show how to solve all-pairs shortest paths on n nodes in deterministic time, and how to count the pairs of orthogonal vectors among n 0–1 vectors in d = clogn dimensions in deterministic n2–1/O(logc) time. These running times essentially match the best known randomized algorithms of (Williams, STOC'14) and (Abboud, Williams, and Yu, SODA 2015) respectively, and the ability to count was open even for randomized algorithms. By reductions, these two results yield faster deterministic algorithms for many other problems. Our techniques can also be used to deterministically count k-SAT assignments on n variable formulas in 2n–n/O(k) time, roughly matching the best known running times for detecting satisfiability and resolving an open problem of Santhanam (2013). A key to our constructions is an efficient way to deterministically simulate certain probabilistic polynomials critical to the algorithms of prior work, carefully applying small-biased sets and modulus-amplifying polynomials.

A recent, active line of work achieves tight lower bounds for fundamental problems under the Strong Exponential Time Hypothesis (SETH). A celebrated result of Backurs and Indyk (STOC’15) proves that computing the Edit Distance of two sequences of length n in truly subquadratic O(n2−ε) time, for some ε>0, is impossible under SETH. The result was extended by follow-up works to simpler looking problems like finding the Longest Common Subsequence (LCS).

In order to formally understand the power of neural computing, we first need to crack the frontier of threshold circuits with two and three layers, a regime that has been surprisingly intractable to analyze. We prove the first super-linear gate lower bounds and the first super-quadratic wire lower bounds for depth-two linear threshold circuits with arbitrary weights, and depth-three majority circuits computing an explicit function. (1) We prove that for all ε ≪ √log(n)/n, the linear-time computable Andreev’s function cannot be computed on a (1/2+ε)-fraction of n-bit inputs by depth-two circuits of o(ε3 n3/2/log3 n) gates, nor can it be computed with o(ε3 n5/2/log7/2 n) wires. This establishes an average-case “size hierarchy” for threshold circuits, as Andreev’s function is computable by uniform depth-two circuits of o(n3) linear threshold gates, and by uniform depth-three circuits of O(n) majority gates. (2) We present a new function in P based on small-biased sets, which we prove cannot be computed by a majority vote of depth-two threshold circuits of o(n3/2/log3 n) gates, nor with o(n5/2/log7/2n) wires. (3) We give tight average-case (gate and wire) complexity results for computing PARITY with depth-two threshold circuits; the answer turns out to be the same as for depth-two majority circuits. The key is a new method for analyzing random restrictions to linear threshold functions. Our main analytical tool is the Littlewood-Offord Lemma from additive combinatorics.

We study connections between the Natural Proofs of Razborov and Rudich, derandomization, and the problem of proving “weak” circuit lower bounds such as ${\sf NEXP} \not\subset {\sf TC}^0$, which are still wide open. Natural Proofs have three properties: they are constructive (an efficient algorithm $A$ is embedded in them), have largeness ($A$ accepts a large fraction of strings), and are useful ($A$ rejects all strings which are truth tables of small circuits). Strong circuit lower bounds that are “naturalizing” would contradict present cryptographic understanding, yet the vast majority of known circuit lower bound proofs are naturalizing. So it is imperative to understand how to pursue un-Natural Proofs. Some heuristic arguments say constructivity should be circumventable: largeness is inherent in many proof techniques, and it is probably our presently weak techniques that yield constructivity. We prove the following: (i) Constructivity is unavoidable, even for ${\sf NEXP}$ lower bounds. Informally, we prove for all “typical” nonuniform circuit classes ${\cal C}$, ${\sf NEXP} \not\subset {\cal C}$ if and only if there is a polynomial-time algorithm distinguishing some function from all functions computable by ${\cal C}$-circuits. Hence ${\sf NEXP} \not\subset {\cal C}$ is equivalent to exhibiting a constructive property useful against ${\cal C}$. (ii) There are no ${\sf P}$-natural properties useful against ${\cal C}$ if and only if randomized exponential time can be “derandomized” using truth tables of circuits from ${\cal C}$ as random seeds. Therefore the task of proving there are no ${\sf P}$-natural properties is inherently a derandomization problem, weaker than but implied by the existence of strong pseudorandom functions. These characterizations are applied to yield several new results, including improved ${\sf ACC}^0$ lower bounds and new unconditional derandomizations. In general, we develop and apply several new connections between the existence of certain algorithms for analyzing truth tables, and the nonexistence of small circuits for problems in large classes such as ${\sf NEXP}$.

The fastest known randomized algorithms for several parameterized problems use reductions to the k -M l D problem: detection of multilinear monomials of degree k in polynomials presented as circuits. The fastest known algorithm for k -M l D is based on 2 k evaluations of the circuit over a suitable algebra. We use communication complexity to show that it is essentially optimal within this evaluation framework. On the positive side, we give additional applications of the method: finding a copy of a given tree on k nodes, a minimum set of nodes that dominate at least t nodes, and an m -dimensional k -matching. In each case, we achieve a faster algorithm than what was known before. We also apply the algebraic method to problems in exact counting. Among other results, we show that a variation of it can break the trivial upper bounds for the disjoint summation problem.

The Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function f and a size parameter k, is the circuit complexity of f at most k? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. Unlike many problems of its kind, MCSP is not known to be NP-hard, yet an efficient algorithm for this problem also seems very unlikely: for example, MCSP in P would imply there are no pseudorandom functions. Although most NP-complete problems are complete under strong "local" reduction notions such as poly-logarithmic time projections, we show that MCSP is provably not NP-hard under O(n^(1/2-epsilon))-time projections, for every epsilon > 0. We prove that the NP-hardness of MCSP under (logtime-uniform) AC0 reductions would imply extremely strong lower bounds: NP \not\subset P/poly and E \not\subset i.o.-SIZE(2^(delta * n)) for some delta > 0 (hence P = BPP also follows). We show that even the NP-hardness of MCSP under general polynomial-time reductions would separate complexity classes: EXP != NP \cap P/poly, which implies EXP != ZPP. These results help explain why it has been so difficult to prove that MCSP is NP-hard. We also consider the nondeterministic generalization of MCSP: the Nondeterministic Minimum Circuit Size Problem (NMCSP), where one wishes to compute the nondeterministic circuit complexity of a given function. We prove that the Sigma_2 P-hardness of NMCSP, even under arbitrary polynomial-time reductions, would imply EXP \not\subset P/poly.

Complexity lower bounds like P != NP assert impossibility results for all possible programs of some restricted form. As there are presently enormous gaps in our lower bound knowledge, a central question on the minds of today's complexity theorists is how will we find better ways to reason about all efficient programs? I argue that some progress can be made by (very deliberately) thinking algorithmically about lower bounds. Slightly more precisely, to prove a lower bound against some class C of programs, we can start by treating C as a set of inputs to another (larger) process, which is intended to perform some basic analysis of programs in C. By carefully studying the algorithmic "meta-analysis" of programs in C, we can learn more about the limitations of the programs being analyzed. This essay is mostly self-contained; scant knowledge is assumed of the reader.

We show how to compute any symmetric Boolean function on n variables over any field (as well as '/ the integers) with a probabilistic polynomial of degree O( √nlog(1/ε)) and error at most ε. The degree dependence on n and ε is optimal, matching a lower bound of Razborov (1987) and Smolensky (1987) for the MAJORITY function. The proof is constructive: a low-degree polynomial can be efficiently sampled from the distribution. This polynomial construction is combined with other algebraic ideas to give the first subquadratic time algorithm for computing a (worst-case) batch of Hamming distances in superlogarithmic dimensions, exactly. To illustrate, let c(n) : ℕ → ℕ. Suppose we are given a database D of n vectors in {0,1}c(n)lognand a collection of n query vectors Q in the same dimension. For all u ∈ Q, we wish to compute a v ∈ D with minimum Hamming distance from u. We solve this problem in n2-1/O(c(n)log2c(n))randomized time. Hence, the problem is in “truly subquadratic” time for O(logn) dimensions, and in subquadratic time for d = o((log2 n)/(loglogn)2). We apply the algorithm to computing pairs with maximum inner product, closest pair in ℓ1 for vectors with bounded integer entries, and pairs with maximum Jaccard coefficients.

We revisit a natural zero-sum game from several prior works. A circuit player, armed with a collection of Boolean circuits, wants to compute a function $f$ with one (or some) of its circuits. An input player has a collection of inputs, and wants to find one (or some) inputs on which the circuit player cannot compute f. Several results are known on the existence of small-support strategies for zero-sum games, in particular the above circuit-input game. We give two new applications of these classical results to circuit complexity:

Given a set-comparison predicate P and given two lists of sets A = (A1,...,Am) and B = (B1,...,Bm), with all Ai, Bj ⊆ [n], the P-set join A bowtieP B is defined to be the set {(i, j) in [m] x [m] | P(Ai,Bj)}. When P(Ai,Bj) is the condition "Ai ∩ Bj ≠ is empty " we call this the set-intersection-notempty join (a.k.a. the composition of A and B); when P(Ai,Bj) is "Ai ∩ Bj is empty" we call it the set-disjointness join; when P(Ai,Bj) is "Ai = Bj" we call it the set-equality join; when P(Ai,Bj) is "|Ai ∩ Bj| ≥ T" for a given threshold T, we call it the set-intersection threshold join. Assuming A and B are stored at two different sites in a distributed environment, we study the (randomized) communication complexity of computing these, and related, set-joins A bowtieP B, as well as the (randomized) communication complexity of computing the exact and approximate value of their size k = |A bowtieP B|. Combined, our analyses shed new insights into the quantitative differences between these different set-joins. Furthermore, given the close affinity of the natural join and the set-intersection-not-empty join, our results also yield communication complexity results for computing the natural join in a distributed environment.

In low-depth circuit complexity, the polynomial method is a way to prove lower bounds by translating weak circuits into low-degree polynomials, then analyzing properties of these polynomials. Recently, this method found an application to algorithm design: Williams (STOC 2014) used it to compute all-pairs shortest paths in time on dense n-node graphs. In this paper, we extend this methodology to solve a number of problems in combinatorial pattern matching and Boolean algebra, considerably faster than previously known methods. First, we give an algorithm for Boolean Orthogonal Detection, which is to detect among two sets A,B ⊆ {0,1}dof size n if there is an x ∊ A and y ∊ B such that 〈x,y〉 = 0. For vectors of dimension d = c(n) log n, we solve Boolean Orthogonal Detection in n2–1/O(log c(n)) time by a Monte Carlo randomized algorithm. We apply this as a subroutine in several other new algorithms: In Batch Partial Match, we are given n query strings from from {0, 1, ⋆}c(n) log n (⋆ is a “don't care”), n strings from {0, 1}c(n)log n, and wish to determine for each query whether or not there is a string matching the query. We solve this problem in n2–1/O(logc(n)) time by a Monte Carlo randomized algorithm. Let t ≤ ν be integers. Given a DNF F on c log t variables with t terms, and v arbitrary assignments on the variables, F can be evaluated on all ν assignments in ν · t1–1/O(log c) time, with high probability. There is a randomized algorithm that solves the Longest Common Substring with don't cares problem on two strings of length n in time. Given two strings S, T of length n, there is a randomized algorithm that computes the length of the longest substring of S that has Edit-Distance less than k to a substring of T in time. Symmetric Boolean Constraint Satisfaction Problems (CSPs) with n variables and m constraints are solvable in poly(m). 2n(1–1/O(log mn)) time.

We study algorithms for the satisfiability problem for quantified Boolean formulas (QBFs), and consequences of faster algorithms for circuit complexity. We show that satisfiability of quantified 3-CNFs with m clauses, n variables, and two quantifier blocks (one existential block and one universal) can be solved deterministically in time . poly(m). For the case of multiple quantifier blocks (alternations), we show that satisfiability of quantified CNFs of size poly(n) on n variables with q quantifier blocks can be solved in 2n−n1/(q + 1)· poly(n) time by a zero-error randomized algorithm. These are the first provable improvements over brute force search in the general case, even for quantified polynomial-sized CNFs with two quantifier blocks. A second zero-error randomized algorithm solves QBF on circuits of size s in 2n–Ω(q) · poly(s) time when the number of quantifier blocks is q. We complement these algorithms by showing that improvements on them would imply new circuit complexity lower bounds. For example, if satisfiability of quantified CNF formulas with n variables, poly(n) size and at most q quantifier blocks can be solved in time 2n–nwq (1/q) then the complexity class NEXP does not have O(log n) depth circuits of polynomial size. Furthermore, solving satisfiability of quantified CNF formulas with n variables, poly(n) size and O(log n) quantifier blocks in time 2n–w(log (n)) time would imply the same circuit complexity lower bound. The proofs of these results proceed by establishing strong relationships between the time complexity of QBF satisfiability over CNF formulas and the time complexity of QBF satisfiability over arbitrary Boolean formulas.

We present new algorithms for finding induced four-node subgraphs in a given graph, which run in time roughly that of detecting a clique on three nodes (i.e., a triangle). The best known algorithms for triangle finding in an n-node graph take O(nω) time, where ω < 2.373 is the matrix multiplication exponent. We give a general randomized technique for finding any induced four-node subgraph, except for the clique or independent set on 4 nodes, in Õ (nω) time with high probability. The algorithm can be derandomized in some cases: we show how to detect a diamond (or its complement) in deterministic Õ(nω) time. Our approach substantially improves on prior work. For instance, the previous best algorithm for C4 detection ran in O(n3.3) time, and for diamond detection in O(n3) time. For sparse graphs with m edges, the best known triangle finding algorithm runs in O(m2ω/(ω+1)) ≤ O(m1.41) time. We give a randomized Õ(m2ω/(ω+1)) time algorithm (analogous to the best known for triangle finding) for finding any induced four-node subgraph other than C4, K4 and their complements. In the case of diamond detection, we also design a deterministic Õ(m2ω/(ω+1)) time algorithm. For C4 or its complement, we give randomized Õ(m(4ω–1)/(2ω+1)) ≤ O(m1.48) time finding algorithms. These algorithms substantially improve on prior work. For instance, the best algorithm for diamond detection ran in O(m1.5) time.

The title of this paper is meant to highlight an emerging duality between two fundamental topics in algorithms and complexity theory. Algorithms for circuits} refers to the design of interesting algorithms which can perform non-trivial circuit analysis of some kind, on either a circuit or a Boolean function given as a truth table. For instance, an algorithm determining whether a given circuit has an input that forces a true output would solve the NP-complete Circuit-SAT problem. Such an algorithm is of course unlikely to run in polynomial time, but could possibly be more efficient than exhaustively trying all possible inputs to the circuit. Circuits for algorithms refers to the modeling of uniform algorithms with non-uniform circuit families (or proving such modeling is impossible). For instance, the NEXP versus P/poly question asks whether nondeterministic exponential-time algorithms can be simulated using non-uniform circuit families of polynomial size. It is widely believed that the answer is emph{no}, however the present mathematical tools available are still too crude to prove this kind of separation. This paper surveys these two generic subjects, the ways in which they arise, and connections that have been developed between them, focusing on the connections between non-trivial circuit-analysis algorithms and proofs of circuit size lower bounds. To give one example, if there is a nontrivial algorithm (running slightly faster than exhaustive search) that can determine if a given circuit computes a constant function, then it can be concluded that NEXP is not contained in P/poly. Informally, this connection can be interpreted as saying "some good algorithms for circuits imply there are no good circuits for some algorithms."

In circuit complexity, the polynomial method is a general approach to proving circuit lower bounds in restricted settings. One shows that functions computed by sufficiently restricted circuits are "correlated" in some way with a low-complexity polynomial, where complexity may be measured by the degree of the polynomial or the number of monomials. Then, results limiting the capabilities of low-complexity polynomials are extended to the restricted circuits. Old theorems proved by this method have recently found interesting applications to the design of algorithms for basic problems in the theory of computing. This paper surveys some of these applications, and gives a few new ones.

Hopcroft's problem in d dimensions asks: given n points and n hyperplanes in ℝd, does any point lie on any hyperplane? Equivalently, if we are given two sets of n vectors each in ℝd+1, is there a pair of vectors (one from each set) that are orthogonal? This problem has a long history and a multitude of applications. It is widely believed that for large d, the problem is subject to the curse of dimensionality: all known algorithms need at least f(d) · n2–1/O(d) time for fast-growing functions f, and at the present time there is little hope that a n2 – ∊ • poly(d) time algorithm will be found. We consider Hopcroft's problem over finite fields and integers modulo composites, leading to both surprising algorithms and hardness reductions. The algorithms arise from studying the communication problem of determining whether two lists of vectors (one list held by Alice, one by Bob) contain an orthogonal pair of vectors over a discrete structure (one from each list). We show the randomized communication complexity of the problem is closely related to the sizes of matching vector families, which have been studied in the design of locally decodable codes. Letting HOPCROFTR denote Hopcroft's problem over a ring ℛ, we give randomized algorithms and almost matching lower bounds (modulo a breakthrough in SAT algorithms) for HOPCROFTR, when ℛ is the ring of integers modulo m or a finite field. Building on the ideas developed here, we give a very simple and efficient output-sensitive algorithm for matrix multiplication that works over any field.

Let ACC o THR be the class of constant-depth circuits comprised of AND, OR, and MODm gates (for some constant m > 1), with a bottom layer of gates computing arbitrary linear threshold functions. This class of circuits can be seen as a "midpoint" between ACC (where we know nontrivial lower bounds) and depth-two linear threshold circuits (where nontrivial lower bounds remain open).

We present a new randomized method for computing the min-plus product (a.k.a., tropical product) of two n × n matrices, yielding a faster algorithm for solving the all-pairs shortest path problem (APSP) in dense n-node directed graphs with arbitrary edge weights. On the real RAM, where additions and comparisons of reals are unit cost (but all other operations have typical logarithmic cost), the algorithm runs in time

The class ACC consists of circuit families with constant depth over unbounded fan-in AND, OR, NOT, and MOD m gates, where m > 1 is an arbitrary constant. We prove the following. ---NEXP, the class of languages accepted in nondeterministic exponential time, does not have nonuniform ACC circuits of polynomial size. The size lower bound can be slightly strengthened to quasipolynomials and other less natural functions. ---E NP , the class of languages recognized in 2 O(n) time with an NP oracle, doesn’t have nonuniform ACC circuits of 2 n o(1) size. The lower bound gives an exponential size-depth tradeoff: for every d, m there is a δ > 0 such that E NP doesn’t have depth- d ACC circuits of size 2 n δ with MOD m gates. Previously, it was not known whether EXP NP had depth-3 polynomial-size circuits made out of only MOD 6 gates. The high-level strategy is to design faster algorithms for the circuit satisfiability problem over ACC circuits, then prove that such algorithms entail these lower bounds. The algorithms combine known properties of ACC with fast rectangular matrix multiplication and dynamic programming, while the second step requires a strengthening of the author’s prior work.

We explore relationships between circuit complexity, the complexity of generating circuits, and algorithms for analyzing circuits. Our results can be divided into two parts: 1. Lower Bounds Against Medium-Uniform Circuits. Informally, a circuit class is “medium uniform” if it can be generated by an algorithmic process that is somewhat complex (stronger than LOGTIME) but not infeasible. Using a new kind of indirect diagonalization argument, we prove several new unconditional lower bounds against medium uniform circuit classes, including: ; For all k, P is not contained in P-uniform SIZE(nk). That is, for all k there is a language Lk∈ P that does not have O(nk)-size circuits constructible in polynomial time. This improves Kannan's lower bound from 1982 that NP is not in P-uniform SIZE(nk) for any fixed k. ; For all k, NP is not in P||NP-uniform SIZE(nk). This also improves Kannan's theorem, but in a different way: the uniformity condition on the circuits is stronger than that on the language itself. ; For all k, LOGSPACE does not have LOGSPACE-uniform branching programs of size nk. 2. Eliminating Non-Uniformity and (Non-Uniform) Circuit Lower Bounds. We complement these results by showing how to convert any potential simulation of LOGTIME-uniform NC1in ACC0/poly or TC0/poly into a medium-uniform simulation using small advice. This lemma can be used to simplify the proof that faster SAT algorithms imply NEXP circuit lower bounds, and leads to the following new connection: . Consider the following task: given a TC0circuit C of nO(1)size, output yes when C is unsatisfiable, and output no when C has at least 2n-2satisfying assignments. (Behavior on other inputs can be arbitrary.) Clearly, this problem can be solved efficiently using randomness. If this problem can be solved deterministically in 2n-ω(log n)time, then NEXP ⊄ TC0/poly. The lemma can also be used to derandomize randomized TC0simulations of NC1on almost all inputs: ; Suppose NC1⊆ BPTC0. Then for every ε > 0 and every language L in NC1, there is a (uniform) TC0circuit family of polynomial size recognizing a language L' such that L and L' differ on at most 2nϵinputs of length n, for all n.

We consider a model of teaching in which the learners are consistent and have bounded state, but are otherwise arbitrary. The teacher is non-interactive and "massively open": the teacher broadcasts a sequence of examples of an arbitrary target concept, intended for every possible on-line learning algorithm to learn from. We focus on the problem of designing interesting teachers: efficient sequences of examples that lead all capable and consistent learners to learn concepts, regardless of the underlying algorithm used by the learner. We use two measures of teaching efficiency: the number of mistakes made by the worst-case learner, and the maximum length of the example sequence needed for the worst-case learner. Our results are summarized as follows: Given a uniform random sequence of examples of an n-bit concept function, learners (capable of consistently learning the concept) with s(n) bits of state are guaranteed to make only O(n ⋅ s(n)) mistakes and exactly learn the concept, with high probability. This theorem has interesting corollaries; for instance, every concept c has a sequence of examples can teach c to all capable consistent on-line learners implementable with s(n)-size circuits, such that every learner makes only ~O(s(n)^2) mistakes. That is, all resource-bounded algorithms capable of consistently learning a concept can be simultaneously taught that concept with few mistakes, on a single example sequence. We also show how to efficiently generate such a sequence of examples on-line: using Nisan's pseudorandom generator, each example in the sequence can be generated with polynomial-time overhead per example, with an O(n ⋅ s(n))-bit initial seed. To justify our use of randomness, we prove that any non-trivial derandomization of our sequences would imply new circuit lower bounds. For instance, if there is a deterministic 2n O(1) time algorithm that generates a sequence of examples, such that all consistent and capable polynomial-size circuit learners learn the all-zeroes concept with less than 2n mistakes, then EXP ⊄ P. We present examples illustrating that the key differences in our model -- our focus on mistakes rather than the total number of examples, and our use of a state bound -- must be considered together to obtain our results. We show that for every consistent s(n)-state bounded learner A, and every n-bit concept that A is capable of learning, there is a custom "tutoring" sequence of only O(n ⋅ s(n)) examples that teaches A the concept. That is, in principle, there are no slow learners, only bad teachers: if a state-bounded learner is capable of learning a concept at all, then it can always be taught that concept quickly via some short sequence of examples.

We study connections between Natural Proofs, derandomization, and the problem of proving "weak" circuit lower bounds such as NEXP ⊄ TC0, which are still wide open. Natural Proofs have three properties: they are constructive (an efficient algorithm A is embedded in them), have largeness (A accepts a large fraction of strings), and are useful (A rejects all strings which are truth tables of small circuits). Strong circuit lower bounds that are "naturalizing" would contradict present cryptographic understanding, yet the vast majority of known circuit lower bound proofs are naturalizing. So it is imperative to understand how to pursue un-Natural Proofs. Some heuristic arguments say constructivity should be circumventable. Largeness is inherent in many proof techniques, and it is probably our presently weak techniques that yield constructivity. We prove: Constructivity is unavoidable, even for NEXP lower bounds. Informally, we prove for all "typical" non-uniform circuit classes C, NEXP ⊄ C if and only if there is a polynomial-time algorithm distinguishing some function from all functions computable by C-circuits. Hence NEXP ⊄ C is equivalent to exhibiting a constructive property useful against C. There are no P-natural properties useful against C if and only if randomized exponential time can be "derandomized" using truth tables of circuits from C as random seeds. Therefore the task of proving there are no P-natural properties is inherently a derandomization problem, weaker than but implied by the existence of strong pseudorandom functions. These characterizations are applied to yield several new results. The two main applications are that NEXP ∩ coNEXP does not have nlog n size ACC circuits, and a mild derandomization result for RP.

The P vs. NP problem arose from the question of whether exhaustive search is necessary for problems with short verifiable solutions. We do not know if even a slight algorithmic improvement over exhaustive search is universally possible for all NP problems, and to date no major consequences have been derived from the assumption that an improvement exists. We show that there are natural NP and BPP problems for which minor algorithmic improvements over the trivial deterministic simulation already entail lower bounds such as ${\sf NEXP} \not\subseteq {\sf P}/{\rm poly}$ and ${\sf LOGSPACE} \neq {\sf NP}$. These results are especially interesting given that similar improvements have been found for many other hard problems. Optimistically, one might hope our results suggest a new path to lower bounds; pessimistically, they show that carrying out the seemingly modest program of finding slightly better algorithms for all search problems may be extremely difficult (if not impossible). We also prove unconditional superpolynomial time-space lower bounds for improving on exhaustive search: there is a problem verifiable with $k(n)$ length witnesses in $O(n^a)$ time (for some $a$ and some function $k(n) \leq n$) that cannot be solved in $k(n)^c n^{a+o(1)}$ time and $k(n)^c n^{o(1)}$ space, for every $c \geq 1$. While such problems can always be solved by exhaustive search in $O(2^{k(n)} n^a)$ time and $O(k(n)+ n^a)$ space, we can prove a superpolynomial lower bound in the parameter $k(n)$ when space usage is restricted.

For a pattern graph $H$ on $k$ nodes, we consider the problems of finding and counting the number of (not necessarily induced) copies of $H$ in a given large graph $G$ on $n$ nodes, as well as finding minimum weight copies in both node-weighted and edge-weighted graphs. Our results include the following: 1. The number of copies of an $H$ with an independent set of size $s$ can be computed exactly in $O^*(2^s n^{k-s+3})$ time and $poly(n,k)+O(2^s n^2)$ space, or in $O^*(4^s n^{k-s+3})$ time and $poly(n,k)$ space. (The $O^*$ notation omits $poly(k)$ factors.) To obtain these algorithms we provide fast algorithms for computing the permanent of a $k \times n$ matrix over rings and semirings. 2. The number of copies of any $H$ having minimum (or maximum) node-weight (with arbitrary real weights on nodes) can be found in $O(n^{\omega k/3} + n^{2k/3+o(1)})$ time, where $\omega < 2.38$ is the matrix multiplication exponent and $k$ is divisible by $3$. Similar results hold for other values of $k$. Also, the number of copies having exactly a prescribed weight can be found within this time. These algorithms extend the technique of Czumaj and Lingas [in Proceedings of SODA 2007, ACM, New York, SIAM, Philadelphia, 2007, pp. 986--994] and give a new (algorithmic) application of multiparty communication complexity. 3. Finding an edge-weighted triangle of weight exactly $0$ in general graphs requires $\Omega(n^{3-\varepsilon})$ time for all $\varepsilon > 0$, unless the $3$SUM problem on $N$ numbers can be solved in $O(N^{2 - \varepsilon})$ time. This suggests that the edge-weighted problem is much harder than its node-weighted version.

This paper characterizes alternation trading based proofs that the satisfiability problem is not in the time and space bounded class DTISP(nc, nϵ), for various values c <; 2 and ϵ <; 1. We characterize exactly what can be proved for ϵ ∈ o(1) with currently known methods, and prove the conjecture of Williams that the best known lower bound exponent c = 2 cos(π/7) is optimal for alternation trading proofs. For general time-space tradeoff lower bounds on satisfiability, we give a theoretical and computational analysis of the alternation trading proofs for 0 <; ϵ <; 1, again proving time lower bounds for various values of ϵ which are optimal for the alternation trading proof paradigm.

We give a self-reduction for the Circuit Evaluation problem (CircEval), and prove the following consequences. · Amplifying Size-Depth Lower Bounds. If CIRCEVAL ϵ SIZEDEPTH [nk, n1-δ] for some k and δ, then for every ε >; 0, there is a δ >; 0, there is a δ' >; 0 such that CIRCEVAL ϵ SIZEDEPTH [nk, n1-δ']. Moreover, the resulting circuits require only O(nε) bits of non-uniformity to construct. As a consequence, strong enough depth lower bounds for Circuit Evaluation imply a full separation of P and NC (even with a weak size lower bound). · Lower Bounds for Quantified Boolean Formulas. Let c,d >; 1 and e <; 1 satisfy c <; (1 - e + d)/d. Either the problem of recognizing valid quantified Boolean formulas (QBF) is not solvable in TIME[nc], or the Circuit Evaluation problem cannot be solved with circuits of nd size and ne depth. This implies unconditional polynomial-time uniform circuit lower bounds for solving QBF.

In deletion propagation, tuples from the database are deleted in order to reflect the deletion of a tuple from the view. Such an operation may result in the (often necessary) deletion of additional tuples from the view, besides the intentionally deleted one. The article studies the complexity of deletion propagation, where the view is defined by a conjunctive query (CQ), and the goal is to maximize the number of tuples that remain in the view. Buneman et al. showed that for some simple CQs, this problem can be solved by a straightforward algorithm, which is called here the unidimensional algorithm. The article identifies additional cases of CQs where the unidimensional algorithm succeeds, and in contrast, shows that for some other CQs the problem is NP-hard to approximate better than some constant ratio. In fact, it is shown here that among the CQs without self joins, the hard CQs are exactly the ones that the unidimensional algorithm fails on. In other words, the following dichotomy result is proved: for every CQ without self joins, deletion propagation is either APX-hard or solvable (in polynomial time) by the unidimensional algorithm. The article then presents approximation algorithms for certain CQs where deletion propagation is APX-hard. Specifically, two constant-ratio (and polynomial-time) approximation algorithms are given for the class of sunflower CQs (i.e., CQs having a sunflower hypergraph) without self joins. The first algorithm, providing the approximation ratio 1 − 1/ e , is obtained by formulating the problem at hand as that of maximizing a monotone submodular function subject to a matroid constraint, and then using a known algorithm for such maximization. The second algorithm gives a smaller approximation ratio, 1/2, yet in polynomial time even under combined complexity. Finally, it is shown that self joins can significantly harden approximation in deletion propagation.

The class ACC consists of circuit families with constant depth over unbounded fan-in AND, OR, NOT, and MODm gates, where m >; 1 is an arbitrary constant. We prove: 1. NTIME[2n] does not have non-uniform ACC circuits of polynomial size. The size lower bound can be strengthened to quasi-polynomials and other less natural functions. 2. ENP, the class of languages recognized in 2O(n)time with an NP oracle, doesn't have non-uniform ACC circuits of 2no(1)size. The lower bound gives a size-depth tradeoff: for every d, m there is a δ >; 0 such that ENPdoesn't have s depth-d ACC circuits of size 2nδwith MODmgates. Previously, it was not known whether EXPNPhad depth-3 polynomial size circuits made out of only MOD6gates. The high-level strategy is to design faster algorithms for the circuit satisfiability problem over ACC circuits, then prove that such algorithms can be applied to obtain the above lower bounds.

In deletion propagation, tuples from the database are deleted in order to reflect the deletion of a tuple from the view. Such an operation may result in the (often necessary) deletion of additional tuples from the view, besides the intentionally deleted one. The complexity of deletion propagation is studied, where the view is defined by a conjunctive query (CQ), and the goal is to maximize the number of tuples that remain in the view. Buneman et al. showed that for some simple CQs, this problem can be solved by a trivial algorithm. This paper identifies additional cases of CQs where the trivial algorithm succeeds, and in contrast, it proves that for some other CQs the problem is NP-hard to approximate better than some constant ratio. In fact, this paper shows that among the CQs without self joins, the hard CQs are exactly the ones that the trivial algorithm fails on. In other words, for every CQ without self joins, deletion propagation is either APX-hard or solvable by the trivial algorithm.

We consider two natural extensions of the communication complexity model that are inspired by distributed computing. In both models, two parties are equipped with synchronized discrete clocks, and we assume that a bit can be sent from one party to another in one step of time. Both models allow implicit communication, by allowing the parties to choose whether to send a bit during each step. We examine trade-offs between time (total number of possible time steps elapsed) and communication (total number of bits actually sent). In the synchronized bit model, we measure the total number of bits sent between the two parties (e.g., email). We show that, in this model, communication costs can differ from the usual communication complexity by a factor roughly logarithmic in the number of time steps, and no more than such a factor. In the synchronized connection model, both parties choose whether or not to open their end of the communication channel at each time step. An exchange of bits takes place only when both ends of the channel are open (e.g., instant messaging), in which case we say that a connection has occurred. If a party does not open its end, it does not learn whether the other party opened its channel. When we restrict the number of time steps to be polynomial in the input length, and the number of connections to be polylogarithmic in the input length, the class of problems solved with this model turns out to be roughly equivalent to the communication complexity analogue of PNP([BFS86]). Using our new model, we give what we believe to be the first lower bounds for this class, separating PNPfrom Σ2∩ Π2in the communication complexity setting. Although these models are both quite natural, they have unexpected power, and lead to a refinement of problem classifications in communication complexity.

We say an algorithm on n × n matrices with entries in [-M, M] (or n-node graphs with edge weights from [-M, M]) is truly subcubic if it runs in O(n3-δ- poly(log M)) time for some δ > 0. We define a notion of subcubic reducibility, and show that many important problems on graphs and matrices solvable in O(n3) time are equivalent under subcubic reductions. Namely, the following weighted problems either all have truly subcubic algorithms, or none of them do: The all-pairs shortest paths problem (APSP). Detecting if a weighted graph has a triangle of negative total edge weight. Listing up to n2.99negative triangles in an edge-weighted graph. Finding a minimum weight cycle in a graph of nonnegative edge weights. The replacement paths problem in an edge-weighted digraph. Finding the second shortest simple path between two nodes in an edge-weighted digraph. Checking whether a given matrix defines a metric. Verifying the correctness of a matrix product over the (min, +)-semiring. Therefore, if APSP cannot be solved in n3-ε time for any ε > 0, then many other problems also need essentially cubic time. In fact we show generic equivalences between matrix products over a large class of algebraic structures used in optimization, verifying a matrix product over the same structure, and corresponding triangle detection problems over the structure. These equivalences simplify prior work on subcubic algorithms for all-pairs path problems, since it now suffices to give appropriate subcubic triangle detection algorithms. Other consequences of our work are new combinatorial approaches to Boolean matrix multiplication over the (OR, AND)semiring (abbreviated as BMM). We show that practical advances in triangle detection would imply practical BMM algorithms, among other results. Building on our techniques, we give two new BMM algorithms: a derandomization of the recent combinatorial BMM algorithm of Bansal and Williams (FOCS'09), and an improved quantum algorithm for BMM.

We describe reductions from the problem of determining the satisfiability of Boolean CNF formulas (CNF-SAT) to several natural algorithmic problems. We show that attaining any of the following bounds would improve the state of the art in algorithms for SAT: an O(nk – ε) algorithm for k-Dominating Set, for any k ≥ 3, a (computationally efficient) protocol for 3-party set disjointness with o(m) bits of communication, an no(d) algorithm for d-SUM, an O(n2 – ε) algorithm for 2-SAT formulas with m = n1+o(1) clauses, where two clauses may have unrestricted length, and an O((n + m)k – ε) algorithm for HornSat with k unrestricted length clauses. One may interpret our reductions as new attacks on the complexity of SAT, or sharp lower bounds conditional on exponential hardness of SAT.

A fertile area of recent research has demonstrated concrete polynomial time lower bounds for solving natural hard problems on restricted computational models. Among these problems are Satisfiability, Vertex Cover, Hamilton Path, $\text{MOD}_6\text{-SAT}$, Majority-of-Majority-SAT, and Tautologies, to name a few. The proofs of these lower bounds follow a certain proof-by-contradiction strategy that we call {\em alternation-trading}. An important open problem is to determine how powerful such proofs can possibly be. We propose a methodology for studying these proofs that makes them amenable to both formal analysis and automated theorem proving. We prove that the search for better lower bounds can often be turned into a problem of solving a large series of linear programming instances. Implementing a small-scale theorem prover based on this result, we extract new human-readable time lower bounds for several problems. This framework can also be used to prove concrete limitations on the current techniques.

The P vs NP problem arose from the question of whether exhaustive search is necessary for problems with short verifiable solutions. We still do not know if even a slight algorithmic improvement over exhaustive search is universally possible for all NP problems, and to date no major consequences have been derived from the assumption that an improvement exists.

For a graph G with real weights assigned to the vertices (edges), the MAX H -SUBGRAPH problem is to find an H -subgraph of G with maximum total weight, if one exists. Our main results are new strongly polynomial algorithms for the MAX H -SUBGRAPH problem. Some of our algorithms are based, in part, on fast matrix multiplication. For vertex-weighted graphs with n vertices we solve a more general problem: the all pairs MAX H -SUBGRAPH problem, where the task is to find for every pair of vertices u,v, a maximum H -subgraph containing both u and v , if one exists. We obtain an O ( n t (ω, h )) -time algorithm for the all pairs MAX H -SUBGRAPH problem in the case where H is a fixed graph with h vertices and ω < 2.376 is the exponent of matrix multiplication. The value of t (ω, h ) is determined by solving a small integer program. In particular, heaviest triangles for all pairs can be found in O ( n 2+1/(4-ω) ) ≤ o ( n 2.616 )-time. For h =4,5,8 the running time of our algorithm essentially matches that of the (unweighted) H -subgraph detection problem. Using rectangular matrix multiplication, the value of t ( ω,h ) can be improved; for example, the runtime for triangles becomes O ( n 2.575 ). We also present improved algorithms for the MAX H -SUBGRAPH problem in the edge-weighted case. In particular, we obtain an O ( m 2−1/ k log n )-time algorithm for the heaviest cycle of length 2 k or 2 k −1 in a graph with m edges and an O ( n 3 /log n )-time randomized algorithm for finding the heaviest cycle of any fixed length. Our methods also yield efficient algorithms for several related problems that are faster than any previously existing algorithms. For example, we show how to find chromatic H -subgraphs in edge-colored graphs, and how to compute the most significant bits of the distance product of two real matrices, in truly subcubic time.

In 1982, Kannan showed that SigmaP2does not have nk-sized circuits for any k. Do smaller classes also admit such circuit lower bounds? Despite several improvements of Kannan's result, we still cannot prove that PNPdoes not have linear size circuits. Work of Aaronson and Wigderson provides strong evidence - the "algebrization'' barrier - that current techniques have inherent limitations in this respect. We explore questions about fixed-polynomial size circuit lower bounds around and beyond the algebrization barrier. We find several connections, including 1) The following are equivalent: -NP is in SIZE(nk) (has O(nk)-size circuit families) for some k -For each c, PNP[nc]is in SIZE(nk) for some k -ONP/1 is in SIZE(nk) for some k, where ONP is the class of languages accepted obliviously by NP machines, with witnesses for "yes" instances depending only on the input length. 2) For a large number of natural classes C and all k ges C is in SIZE(nk) if and only if C/1 cap P/poly is in SIZE(nk). 3) If there is a d such that MATIME(n) sube NTIME(nd), then PNPdoes not have O(nk) size circuits for any k > 0. 4) One cannot show n2-size circuit lower bounds for oplusP without new nonrelativizing techniques. In particular, the proof that PP nsube SIZE(nk) for all k relies on the (relativizing) result that PPPsube MA rArr PP nsube SIZE(nk), and we give an oracle relative to which PoplusPsube MA and oplusP sube SIZE(n2) both hold.

We present new combinatorial algorithms for Boolean matrix multiplication (BMM) and preprocessing a graph to answer independent set queries. We give the first asymptotic improvements on combinatorial algorithms for dense BMM in many years, improving on the "Four Russians'' O(n3/(w log n)) bound for machine models with word size w. (For a pointer machine, we can set w = log n.) The algorithms utilize notions from Regularity Lemmas for graphs in a novel way. 1) We give two randomized combinatorial algorithms for BMM. The first algorithm is essentially a reduction from BMM to the Triangle Removal Lemma}. The best known bounds for the Triangle Removal Lemma only imply an O((n3log ?)/(?w log n)\right) time algorithm for BMM where ? = (log*n)?for some ? > 0, but improvements on the Triangle Removal Lemma would yield corresponding runtime improvements. The second algorithm applies the Weak Regularity Lemma of Frieze and Kannan along with several information compression ideas, running in O(n3(log log n)2/(log n)9/4) time with probability exponentially close to 1. When w ? log n, it can be implemented in O(n3(log log n)2/(w log n)7/6)) time. Our results immediately imply improved combinatorial methods for CFG parsing, detecting triangle-freeness, and transitive closure. 2)Using Weak Regularity, we also give an algorithm for answering queries of the form is S ? V an independent set? in a graph. Improving on prior work, we show how to randomly preprocess a graph in O(n2+?}) time (for all ? > 0) so that with high probability, all subsequent batches of log n independent set queries can be answered deterministically in O(n2(log log n)2/((log n)5/4)) time. When w ? log n, w queries can be answered in O(n2(log log n)2/((log n)7/6))\right) time. In addition to its nice applications, this problem is interesting in that it is not known how to do better than O(n2) using "algebraic'' methods.

For a pattern graph H on k nodes, we consider the problems of finding and counting the number of (not necessarily induced) copies of H in a given large graph G on n nodes, as well as finding minimum weight copies in both node-weighted and edge-weighted graphs. Our results include: The number of copies of an H with an independent set of size s can be computed exactly in O*(2s nk-s+3) time. A minimum weight copy of such an H (with arbitrary real weights on nodes and edges) can be found in O(4s+o(s) nk-s+3) time. (The O* notation omits (k) factors.) These algorithms rely on fast algorithms for computing the permanent of a k x n matrix, over rings and semirings. The number of copies of any H having minimum (or maximum) node-weight (with arbitrary real weights on nodes) can be found in O(nω k/3 + n2k/3+o(1)) time, where ω < 2.4 is the matrix multiplication exponent and k is divisible by 3. Similar results hold for other values of k. Also, the number of copies having exactly a prescribed weight can be found within this time. These algorithms extend the technique of Czumaj and Lingas (SODA 2007) and give a new (algorithmic) application of multiparty communication complexity. Finding an edge-weighted triangle of weight exactly 0 in general graphs requires Ω(n2.5-ε) time for all ε > 0, unless the 3SUM problem on N numbers can be solved in O(N2 - ε) time. This suggests that the edge-weighted problem is much harder than its node-weighted version.

We prove the first time-space tradeoffs for counting the number of solutions to an NP problem modulo small integers, and also improve upon the known time-space tradeoffs for SAT. Let m be a positive integer, and define MOD_m- SAT to be the problem of determining if a given Boolean formula has exactly km satisfying assignments, for some integer k. We prove that for all primes p, except for possibly one of them, MOD_p-SAT is not solvable in nc time and n^o(1) space on RAMs, for c \geqslant 1 satisfying c^3 - c^2 - 2c + 1 \le 0 (c \le 1.801 suffices). That is, there is at most one prime p that does not satisfy the lower bound. Note that such a lower bound does not follow from the SAT time-space tradeoffs, as we do not know of an efficient deterministic reduction from SAT to MOD_p-SAT. The result is non-constructive, in that it does not provide an explicit prime for which the lower bound holds. However, we can prove that the same limitation holds for SAT and MOD_6-SAT, as well as MOD_m-SAT for any composite m that is not a prime power. Our main tool is a general method for rapidly simulating deterministic RAM computations with restricted space, by counting the number of solutions to NP predicates modulo primes. The simulation converts an ordinary RAM into a "canonical one" that runs in roughly the same amount of time and space, yet its configuration sequences have nice properties suitable for counting.

In the all-pairs bottleneck paths (APBP) problem (a.k.a. all-pairs maximum capacity paths), one is given a directed graph with real non-negative capacities on its edges and is asked to determine, for all pairs of vertices s and t, the capacity of a single path for which a maximum amount of flow can be routed from s to t. The APBP problem was first studied in operations research, shortly after the introduction of maximum flows and all-pairs shortest paths.

We present the first truly sub-cubic algorithms for finding a maximum node-weighted triangle in directed and undirected graphs with arbitrary real weights. The first is an O(B • n3+ω/2) = O(B • n2.688) deterministic algorithm, where n is the number of nodes, ω is the matrix multiplication exponent, and B is the number of bits of precision. The second is a strongly polynomial randomized algorithm that runs in O(n3+ω/2 log n) expected worst-case time. To achieve this, we show how to efficiently sample a weighted triangle uniformly at random, out of just those triangles whose total weight falls in some prescribed interval (W1,W2) for arbitrary weights W1 and W2. Previous approaches to the problem resulted in time bounds with either an exponential dependence on B, or a runtime of the form Ω(n3/(log n)c). The algorithms are easily extended to finding a maximum node-weighted induced subgraph on 3k nodes in Õ(n(3+ω)k/2) = O(n2.688 k) time.We give applications to a variety of problems, including a stable matching problem between buyers and sellers in computational economics, and discuss the possibility of extending our approach to a truly sub-cubic algorithm for computing all-pairs shortest paths on directed graphs with arbitrary weights.

We improve upon indirect diagonalization arguments for lower bounds on explicit problems within the polynomial hierarchy. Our contributions are summarized as follows. 1. We present a technique that uniformly improves upon most known nonlinear time lower bounds for nondeterminism and alternating computation, on both subpolynomial (n o(1)) space RAMs and sequential one-tape machines with random access to the input. We obtain improved lower bounds for Boolean satisfiability (SAT), as well as all NP-complete problems that have efficient reductions from SAT, and ∑ k -SAT, for constant k ≥ 2. For example, SAT cannot be solved by random access machines using $$n^{\sqrt{3}}$$ time and subpolynomial space. 2. We show how indirect diagonalization leads to time-space lower bounds for computation with bounded nondeterminism. For both the random access and multitape Turing machine models, we prove that for all k ≥ 1, there is a constant c k > 1 such that linear time with n 1/k nondeterministic bits is not contained in deterministic $$n^{{c}_{k}}$$ time with subpolynomial space. This is used to prove that satisfiability of Boolean circuits with n inputs and n k size cannot be solved by deterministic multitape Turing machines running in $${n^{{k \cdot {c}}_{k}}}$$ time and subpolynomial space.

We make several improvements on time lower bounds for concrete problems in NP and PH. 1) We present an elementary technique based on "indirect diagonalization" that uniformly improves upon the known nonlinear time lower bounds for nondeterminism and alternating computation, on both sublinear (n/sup o(1)/) space RAMs and sequential worktape machines with random access to the input. We obtain better lower bounds for SAT as well as all NP-complete problems that have efficient reductions from SAT and /spl Sigma//sub k/-SAT for constant k /spl ges/ 2. For example, SAT cannot be solved by random access machines using n/sup /spl radic/(3) /time and n/sub o(1)/ space. The technique is a natural inductive approach, for which previous work is essentially its base case. 2) We show how indirect diagonalization can also yield time-space lower bounds for computation with bounded nondeterminism. One corollary is that for all k, there exists a constant c/sub k/ > 1 such that satisfiability of Boolean circuits with n inputs and n/sup k/ gates cannot be solved in deterministic time n/sup k/spl middot/c//sub k/ and n/sup o(1)/ space.

We study the problem of asymptotically reducing the runtime of serial computations with circuits of polynomial size. We give an algorithmic size-depth tradeoff for parallelizing time t random access Turing machines, a model at least as powerful as logarithmic cost RAMs. Our parallel simulation yields logspace-uniform t O(1) size, O(t / log t)-depth Boolean circuits having semi-unbounded fan-in gates. In fact, for appropriate d, uniform t O(1) 2 O(t/d) size circuits of depth O(d) can simulate time t. One corollary is that every log-cost time t RAM can be simulated by a log-cost CRCW PRAM using t O(1) processors and O(t / log t) time. This improves over previous parallel speedups, which only guaranteed an Ω(log t)-speedup with an exponential number of processors for weaker models of computation. These results are obtained by generalizing the well-known result that DTIME[t] ⊆ ASPACE[log t].

The technique of k-anonymization has been proposed in the literature as an alternative way to release public information, while ensuring both data privacy and data integrity. We prove that two general versions of optimal k-anonymization of relations are NP-hard, including the suppression version which amounts to choosing a minimum number of entries to delete from the relation. We also present a polynomial time algorithm for optimal k-anonymity that achieves an approximation ratio independent of the size of the database, when k is constant. In particular, it is a O(k log k)-approximation where the constant in the big-O is no more than 4, However, the runtime of the algorithm is exponential in k. A slightly more clever algorithm removes this condition, but is a O(k log m)-approximation, where m is the degree of the relation. We believe this algorithm could potentially be quite fast in practice.