Proving super-logarithmic lower bounds on the depth of circuits is one of the main frontiers of circuit complexity. In 1991, Karchmer, Raz and Wigderson observed that we could resolve this question by proving the following conjecture: Given two boolean functions f,g, the depth complexity of their composition is about the sum of their individual depth complexities. While we cannot prove the conjecture yet, there has been some exciting progress toward such a proof, some of it in the last few years.

In this talk, I will survey the known results and propose future directions for research on the KRW conjecture. In particular, I will present some open problems which I believe are both tractable and important toward making further progress on the conjecture.

We give an explicit black-box problem that can be solved by a bounded-error quantum polynomial-time algorithm (BQP, in short), but cannot be solved by a classical algorithm in the polynomial hierarchy.

Following the approach of Aaronson [STOC, 2010], our result is obtained by finding a distribution D over Boolean strings of length N such that:
(1) There exists a quantum algorithm that runs in time polylog(N) and distinguishes between D and the uniform distribution over Boolean strings of length N.
(2) No Boolean circuit of quasi-polynomial size and constant depth can distinguish between D and the uniform distribution with advantage better than polylog(N)/sqrt(N).

Joint work with Ran Raz.

The approximate degree of a Boolean function f(x_1,x_2,...,x_n) is the minimum degree of a real polynomial that approximates f pointwise within 1/3. Upper bounds on approximate degree have a variety of applications in learning theory, diferential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity. We develop a first-principles, classical approach to the polynomial approximation of Boolean functions. We use it to give the first constructive upper bounds on the approximate degree of several fundamental problems:

(i) $O(n^{\frac{3}{4}-\frac{1}{4(2^{k}-1)}})$ for the k-element distinctness problem;

(ii) $O(n^{1-\frac{1}{k+1}})$ for the k-subset sum problem;

(iii) $O(n^{1-\frac{1}{k+1}})$ for any k-DNF or k-CNF formula;

(iv) $O(n^{3/4})$ for the surjectivity problem.

In all cases, we obtain explicit, closed-form approximating polynomials that are unrelated to the quantum arguments from previous work. Our first three results match the bounds from quantum query complexity.
Our fourth result improves polynomially on the Theta(n) quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree Omega(n). In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.

Hardness escalation or query-to-communication lifting is a method of proving tight upper and lower bounds on the communication complexity of a composed function or relation by a reduction to the query complexity of the base function. This talk will primarily be a tutorial. I will first discuss the many applications of lifting, including new and improved lower bounds for monotone complexity, game theory, proof complexity and extended formulations. Secondly, I will sketch the main ideas in the proof of the BPP lifting theorem (joint work with Mika Göös and Thomas Watson).

Deciding whether a graph has a k-clique is one of the most basic computational problems on graphs, and has been extensively studied in computational complexity theory ever since it appeared in Karp’s list of 21 NP-complete problems. In terms of upper bounds, the k-clique problem can clearly be solved in time roughly n^k simply by checking if any of the sets of k vertices forms a clique. The motivating problem behind this work is to determine the exact time complexity of the clique problem when k is given as a parameter.

In this talk we will show that for any k <= n^{1/4} regular resolution asymptotically almost surely requires length n^{Ω(k)} to establish that an Erdős–Rényi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in the exponent, and also implies unconditional n^{Ω(k)} lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs.

This is joint work with Albert Atserias, Ilario Bonacina, Massimo Lauria, Jakob Nordström and Alexander Razborov.

We show that for several natural problems of interest (including Vertex Cover, Satisfiability, and variants of the Minimum Circuit Size Problem), complexity lower bounds that are barely non-trivial imply super-polynomial or even exponential lower bounds in strong computational models. We term this phenomenon "hardness magnification''. We further explore magnification as an avenue to proving strong lower bounds, and argue that magnification circumvents the "natural proofs'' barrier of Razborov and Rudich. Examining some standard proof techniques, we find that they fall just short of proving lower bounds via magnification. As one of our main open problems, we ask whether there are other meta-mathematical barriers to proving lower bounds that rule out approaches combining magnification with known techniques.

Joint work with Rahul Santhanam (Oxford).

It is a notorious open problem to prove strong lower bounds for an explicit function against depth-three majority circuits (depth-three TC0), or against depth-two linear threshold circuits (with arbitrary weights). I plan to briefly describe the n^(1.5-o(1)) gate lower bound for an explicit function against depth-three TC0 circuits (with Daniel Kane in STOC'16), as well as a gate lower bound for a function in E^(NP) against ACC^0 composed with depth-two linear threshold circuits (with Josh Alman and Timothy Chan in FOCS'16; similar results were proved independently by Suguru Tamaki). The first lower bound uses random restrictions, while the second lower bound uses the polynomial method; both results are still the state-of-the-art.

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, there exists 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 [JCSS'02] 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 to 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 of THR circuits [R Williams STOC 2014], we conclude that for every fixed k, NQP does not have n^(log^k n)-size ACC of THR circuits.

We study the problem of testing whether an unknown n-variable Boolean function is a k-junta in the distribution-free property testing model, where the distance between functions is measured with respect to an
arbitrary and unknown probability distribution over the Boolean hypercube.

Our first main result is that distribution-free k-junta testing can be performed, with one-sided error, by an adaptive algorithm that uses poly(k/\epsilon) queries (independent of n). Complementing this, our second main result is a lower bound showing that any non-adaptive distribution-free k-junta testing algorithm must make exp(k) many queries even to test to constant accuracy.

These bounds establish that while the optimal query complexity of nonadaptive k-junta testing is exponential in k, for adaptive testing it is poly(k), and thus show that adaptivity provides an exponential improvement in the distribution-free query complexity of testing juntas.

Joint work with Xi Chen, Zhengyang Liu, Ying Sheng and Jinyu Xie.

Celebrated Rice's theorem in computability theory states that any non-trivial semantic property of Turing machines is undecidable. That is, to check if the language accepted by a Turing machine satisfies some property, essentially the only thing one can do is to run the machine.  

Is there is a similar phenomenon in the complexity theory world?  Following a conjecture posed by Barak et al. in their paper on impossibility of obfuscation,  we ask whether working with a description of a Boolean circuit gives any computational advantage for deciding properties of a Boolean function, as opposed to a black-box (oracle) access. 

We show that for read-once branching programs there is indeed such an advantage. For general Boolean circuits, we make a step towards resolving this question by showing that if properties of a certain type are easier to decide given a circuit description then there is a non-trivial algorithm for the CircuitSAT problem.

Joint work with Russell Impagliazzo, Valentine Kabanets, Pierre McKenzie and Shadab Romani.