Monday, September 10th, 2018

10:00 am11:00 am
Speaker: Avi Wigderson (IAS)

I will review (and hope to revive) a collection of old works, surveyed in [1], which suggest obtaining circuit lower bounds by "fusing'' many correct computations (of a circuit too small) into an incorrect computation. This framework may be viewed as a generalization of both the "approximation method'' of Razborov, and the "finite limit'' approach of Sipser. This framework offers a "static" view of computation, which may eliminate the (problematic) need of progress measures in "dynamic" lower bound arguments (whether top-down or bottom-up). It further yields natural combinatorial and algebraic set-cover problems, whose solution *characterizes* the size of surprisingly many computational models (indeed, it gives rise to new ones: Span Programs were born this way!). In a couple of models, this viewpoint led to (slight) superlinear lower bounds, which nonetheless have not been improved upon for 25 years.

[1] Wigderson, Avi. "The fusion method for lower bounds in circuit complexity." Combinatorics, Paul Erdos is Eighty 1.453-468 (1993): 68.

11:30 am12:00 pm
Speaker: Or Meir (University of Haifa)

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.

12:00 pm12:30 pm
Speaker: Kaave Hosseini (UCSD)

We propose a new framework for constructing pseudorandom generators for n-variate Boolean functions. It is based on two new notions. First, we introduce fractional pseudorandom generators, which are pseudorandom distributions taking values in [-1,1]^n . Next, we use a fractional pseudorandom generator as steps of a random walk in [-1,1]^n that converges to {-1,1}^n . We prove that this random walk converges fast (in time logarithmic in n) due to polarization. As an application, we construct pseudorandom generators for Boolean functions with bounded Fourier tails. We use this to obtain a pseudorandom generator for functions with sensitivity s, whose seed length is polynomial in s. Other examples include functions computed by branching programs of various sorts or by bounded depth circuits.

Joint work with Eshan Chattopadhyay, Pooya Hatami, and Shachar Lovett.

2:30 pm3:30 pm
Speaker: Avishay Tal (Stanford University)

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.

4:00 pm4:30 pm
Speaker: Sasha Kulikov (St. Petersburg Department of Steklov Institute of Mathematics)

To prove that P is not equal to NP, it suffices to prove a superpolynomial lower bound on Boolean circuit complexity of a function from NP. Currently, we are not even close to achieving this goal: we do not know how to prove a 4n lower bound. What is more depressing is that there are almost no techniques for proving circuit lower bounds. In this talk, we’ll briefly review various approaches that could potentially lead to stronger linear or superlinear lower bounds for unrestricted Boolean circuits (i.e., circuits with no restriction on depth, fan-out, or basis).

4:30 pm5:00 pm
Speaker: Sasha Golovnev (Columbia University)

Proving lower bounds on the time-space tradeoff of data structures has been a long and active research endeavor for several decades. In a static data structure problem, the goal is to preprocess a database of n elements into minimum space s (>= n), so that queries q \in Q on the input database can be answered in time t. The only super-constant lower bound on the query time t >= \Omega(logn) we know for such data structures is for the regime of linear space s=O(n).

We show that static data structure lower bounds in the group (linear) model imply semi-explicit lower bounds on matrix rigidity. In particular, we show that an explicit lower bound of t >= \omega(log^2 n) on the query time data structures in the linear model, even against arbitrarily small linear space (s= (1+eps)*n), would already imply a semi-explicit (P^NP) construction of rigid matrices with significantly better parameters than the current state of art [Alon, Panigrahy, and Yekhanin, 2009]. Our result also proves that stronger data structure lower bounds (against *polynomial* space) would imply a super-linear circuit lower bound for log-depth linear circuits (which would close a four-decade open question). In the succinct space regime (s=n+o(n)), we show that any improvement on current cell-probe lower bounds in the linear model would also imply new rigidity bounds. Our main result relies on a new connection between the "inner" and "outer" dimensions of a matrix (Pudlak and Paturi, 2006).

Based on a joint work with Zeev Dvir and Omri Weinstein.

Tuesday, September 11th, 2018

10:00 am11:00 am
Speaker: Robert Robere (University of Toronto)

In 1993, Karchmer and Wigderson introduced span programs, which are elegant computational devices that capture the complexity of computing with linear algebra over a field. We discuss some recent work characterizing the monotone span program size of certain "structured" boolean functions in terms of the Nullstellensatz degree required to refute a related unsatisfiable system of polynomial equations. This characterization leads to the resolution of a number of open problems on the complexity of span programs and unifies the proofs of many classic lower bounds in monotone complexity theory by appealing to known Nullstellensatz degree lower bounds.

This work is joint with Toniann Pitassi.

11:30 am12:00 pm
Speaker: Sasha Sherstov (UCLA)

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.

12:00 pm12:30 pm
Speaker: Mark Bun (Princeton University)

The epsilon-approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f pointwise to within error epsilon. Approximate degree has a number of applications throughout theoretical computer science. As one example, a lower bound on the approximate degree of a function automatically implies a lower bound on its quantum query complexity.

I will describe recent progress proving approximate degree lower bounds using the "method of dual polynomials," a framework based on linear programming duality. Our new techniques for constructing dual polynomials yield a nearly tight lower bound on the approximate degree of AC^0, and settle (or nearly settle) the quantum query complexities of several specific functions of interest in quantum computing.

Based on joint works with Robin Kothari and Justin Thaler.

2:30 pm3:30 pm
Speaker: Toni Pitassi (University of Toronto)

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

4:00 pm4:30 pm
Speaker: Mika Göös (Harvard University)

For any unsatisfiable CNF formula F that is hard to refute in the Resolution proof system, we show that a gadget-composed version of F is hard to refute in any proof system whose lines are computed by efficient communication protocols---or, equivalently, that a monotone function associated with F has large monotone circuit complexity. Our result extends to monotone real circuits, which yields new lower bounds for the Cutting Planes proof system.

As an application, we show that a monotone version of the XOR-SAT function has exponential monotone circuit complexity. Since XOR-SAT is in NC^2, this improves qualitatively on the monotone vs. non-monotone separation of Tardos (1988). Another corollary is that monotone span programs can be exponentially more powerful than monotone circuits.

4:30 pm5:00 pm
Speaker: Meena Mahajan (Institute of Mathematical Sciences)

Polynomial-size depth-2 circuits with linear threshold functions at each gate lie at the frontier of known circuit lower bounds. In this talk I will briefly survey the landscape below these circuits - the very-low-depth threshold hierarchy - and present one new result concerning decision lists, obtained jointly with Arkadev Chattopadhyay, Nikhil Mande and Nitin Saurabh. I will also describe a (somewhat related) question from proof complexity.

Wednesday, September 12th, 2018

10:00 am10:45 am
Speaker: Roei Tell (Weizmann Institute)

I will present an overview of quantified derandomization, including known results, barriers, and main open problems. In the classical derandomization problem, we are given as input a Boolean circuit, and want to deterministically decide whether the circuit has high acceptance probability (say, 2/3 or more) or low acceptance probability (say, 1/3 or less). Quantified derandomization, introduced by Goldreich and Wigderson (2014), is the relaxed problem of deciding whether the acceptance probably of the circuit is extremely high (1-o(1)) or extremely low (o(1)). It is a potentially easier problem, which (in some settings) does not necessarily imply new circuit lower bounds. Interestingly, for many circuit classes, the parameters for which we can construct quantified derandomization algorithms are remarkably close to parameters that will yield new standard derandomization algorithms (and new lower bounds). Two prominent classes for which this is the case are AC0 and TC0. In the talk I will survey some of the known results for these classes, as well as for other classes and for diferent settings in which quantified derandomization is relevant (these results are from works by Goldreich, Wigderson, Viola, Chen, Li, Kabanets, Lu, and myself). In addition we will see techniques that were used to prove these results, limitations of these techniques in a black box setting, and main open problems.

11:15 am12:00 pm
Speaker: Susanna de Rezende (KTH Royal Institute of Technology)

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.

12:00 pm12:45 pm
Speaker: Li-Yang Tan (Stanford University)

We give a pseudorandom generator that fools m-facet polytopes over {0,1}^n with seed length polylog(m) * log(n). The previous best seed length had superlinear dependence on m. An immediate consequence is a deterministic quasipolynomial time algorithm for approximating the number of solutions to any {0,1}-integer program.

Joint work with Ryan O'Donnell and Rocco Servedio.

Thursday, September 13th, 2018

10:00 am11:00 am
Speaker: Rahul Santhanam (University of Oxford)

The Minimum Circuit Size Problem (MCSP) asks whether a given Boolean function, represented by its truth table, has small circuits. MCSP is in NP, and is in a sense the inverse problem to SAT. Unlike SAT, its complexity remains poorly understood. I will make the case that MCSP is as fundamental as SAT, and will survey work on different aspects of the problem, including connections to learning, pseudorandomness and natural proofs.

11:30 am12:00 pm
Speaker: Igor Carboni Oliveira (University of Oxford) 

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

12:00 pm12:30 pm
Speaker: Valentine Kabanets (Simon Fraser University)

The concept of  "natural properties" of Razborov and Rudich arose in the context of proving circuit lower bounds for explicit boolean functions, and is used to argue about the limitations of current proof techniques. MCSP (Min Circuit Size Problem), is a close relative ("worst-case version") of the "natural property" whose complexity is still wide open. Understanding the complexity of MCSP also appears to be intimately linked with the problem of proving circuit lower bounds. I'll discuss some known connections among "natural properties," (variants of) MCSP, and circuit lower bounds.

2:30 pm3:00 pm
Speaker: Ryan Williams (MIT)

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.

3:00 pm3:30 pm
Speaker: Lijie Chen (MIT)

We give two new structure lemmas for Depth-Two Threshold Circuits (THR of THR circuits) and apply them to identify potential approaches for proving super-polynomial THR of THR circuit lower bounds. Exponential-size lower bounds for the related (but weaker) classes THR of MAJ and MAJ of MAJ are well-known. Our results show that if one can mine some satisfiability or CAPP algorithms from these known lower bounds, that would already imply long-sought lower bounds for THR of THR circuits.

4:00 pm4:30 pm
Speaker: Cody Murray (MIT)

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.

4:30 pm5:00 pm
Speaker: Michal Koucky (Charles University)

We propose models of combinatorial algorithms for the Boolean Matrix Multiplication (BMM), and prove lower bounds on computing BMM in these models. First, we give a relatively relaxed combinatorial model which is an extension of the model by Angluin (1976), and we prove that the time required by any algorithm for the BMM is at least $Omega(n^3 / 2^O(\sqrt \log n ))$. Subsequently, we propose a more general model capable of simulating the "Four Russians Algorithm". We prove a lower bound of $Omega(n^7/3 / 2^O(\sqrt \log n ))$ for the BMM under this model. We use a special class of graphs, called $(r,t)$-graphs, originally discovered by Rusza and Szemeredi (1978), along with randomization, to construct matrices that are hard instances for our combinatorial models.

Joint work with Debarati Das and Mike Saks.

Friday, September 14th, 2018

10:00 am10:30 am
Speaker: Ben Rossman (University of Toronto)

This talk will give a brief overview of the “pathset complexity” method, an approach to formula lower bounds for Distance-k Connectivity which has so far yielded results in the AC0 and monotone settings.  I will describe some recent progress and highlight a few open questions in this research program.

10:30 am11:00 am
Speaker: Rocco Servedio (Columbia University)

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.

11:30 am12:30 pm
Speaker: Emanuele Viola (Northeastern University)

I survey the knowledge of the complexity of distributions, with a focus on lower bounds and the many open problems. To mention a concrete result, we give an explicit boolean function whose input-output pairs cannot be sampled by AC^0 circuits noticeably better than picking a uniform input and guessing at random the value of the function.

2:30 pm3:00 pm
Speaker: Antonina Kolokolova (Memorial University of Newfoundland)

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.

3:00 pm3:30 pm
Speaker: Srikanth Srinivasan (Indian Institute of Technology Bombay)

We come up with explicit functions for which we can prove tight (up to polynomial factors) upper and lower bounds in the AC^0[2] circuit model. In particular, this implies the first Fixed-Depth Size Hierarchy theorem for this model.

The explicit functions are obtained by constructing explicit AC^0[2] circuits for solving the coin problem, which is defined as follows. For a  parameter delta, we have to decide whether a given coin has bias (1+delta)/2 or (1-delta)/2. Our upper bounds are proved by derandomizing a circuit construction of O'Donnell-Wimmer (2007) and Amano (2009) to reduce the number of samples. Our lower bounds follow from a modification of the Razborov-Smolensky polynomial method.

3:30 pm4:00 pm
Speaker: Arkadev Chattopadhyay (Tata Institute of Fundamental Research)

We exhibit a natural function F on n variables, that can be computed by just a linear sized decision list of `Equalities', but whose sign rank is at least exp(n^(1/4)). This yields the following two new unconditional complexity class separations.

(a) The function F can be computed by linear sized depth-two threshold `formulas' when the weights of the threshold gates are unrestricted, but restricting the weights of the bottom threshold gates to even slightly sub-exponential requires `circuits' to have size exp(n^(1/4)) to compute F. This provides the first separation between the boolean circuit classes THR o MAJ and THR o THR, that was posed as an open problem first by Amano-Maruoka [2005] and again by Hansen and Podolskii[2010]. Our result perhaps explains why obtaining super-polynomial lower bounds against THR o THR have remained elusive.

(b) Communication complexity: The function F (under the natural partition of the inputs) lies in the communication complexity class P^MA.  Since F has large sign rank, this implies P^MA is not in UPP, resolving a recent open problem posed by G{\"o}{\"o}s, Pitassi and Watson [ICALP '16]. P^MA seems tantalizingly out of reach of current lower bound techniques.

This is based on joint work with Nikhil Mande (TIFR).