Schedule for: 19w5088 - Algebraic Techniques in Computational Complexity

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

For every constant d >= 3 and epsilon > 0, we give a deterministic poly(n)-time algorithm that outputs a d-regular graph on Θ(n) vertices that is epsilon-near-Ramanujan; i.e., its eigenvalues are bounded in magnitude by 2sqrt(d-1)+epsilon (excluding the single trivial eigenvalue of d).

Existing proofs that deduce BPP=P from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown. Specifically, assuming exponential lower bounds against nondeterministic circuits, we convert any randomized algorithm that errs rarely into a deterministic algorithm with a similar running time (with pre-processing), and any general randomized algorithm into a deterministic algorithm whose runtime is slower by a nearly linear multiplicative factor. Our results follow from a new, nearly optimal, explicit pseudorandom generator fooling circuits of size s with seed length (1+alpha)log s for an arbitrarily small constant alpha>0, under the assumption that there exists a function f in E that requires nondeterministic circuits of size at least 2^{(1-alpha')n}, where alpha = O(alpha'). The construction uses, among other ideas, a new connection between pseudoentropy generators and locally list recoverable codes.

We describe new ways of constructing pseudorandom generators for Boolean functions that satisfy certain bounds on their Fourier spectrum. We discuss the possibility of using this approach to construct pseudorandom generators for complexity classes that have eluded researches for decades. Based on joint works with Pooya Hatami, Kaave Hosseini, Shachar Lovett and Avishay Tal.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

We give an explicit pseudorandom generator (PRG) for read-once $\mathbf{AC}^0$, i.e., constant-depth read-once formulas over the basis $\{\wedge, \vee, \neg\}$ with unbounded fan-in. The seed length of our PRG is $\widetilde{O}(\log(n/\varepsilon))$. Previously, PRGs with near-optimal seed length were known only for the depth-$2$ case (Gopalan et al. FOCS '12). For a constant depth $d > 2$, the best prior PRG is a recent construction by Forbes and Kelley with seed length $\widetilde{O}(\log^2 n + \log n \log(1/\varepsilon))$ for the more general model of constant-width read-once branching programs with arbitrary variable order (FOCS '18). Looking beyond read-once $\mathbf{AC}^0$, we also show that our PRG fools read-once $\mathbf{AC}^0[\oplus]$ with seed length $\widetilde{O}(t + \log(n/\varepsilon))$, where $t$ is the number of parity gates in the formula. Our construction follows Ajtai and Wigderson's approach of iterated pseudorandom restrictions (Advances in Computing Research '89). We assume by recursion that we already have a PRG for depth-$d$ $\mathbf{AC}^0$ formulas. To fool depth-$(d + 1)$ $\mathbf{AC}^0$ formulas, we use the given PRG, combined with a small-bias distribution and almost $k$-wise independence, to sample a pseudorandom restriction. The analysis of Forbes and Kelley shows that our restriction approximately preserves the expectation of the formula. The crux of our work is showing that after $\text{poly}(\log \log n)$ independent applications of our pseudorandom restriction, the formula simplifies in the sense that every gate other than the output has only $\text{polylog} n$ remaining children. Finally, as the last step, we use a recent PRG by Meka, Reingold, and Tal (STOC '19) to fool this simpler formula. Joint work with Dean Doron and Pooya Hatami.

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

http://www.mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pdf

Ever since Beals et al. made the connection in 1998, the polynomial method has been one of the central tools for understanding the limitations of quantum algorithms. Here I'll explain a new variant of this method, which uses Laurent polynomials (polynomials that can have negative exponents). Together with colleagues William Kretschmer, Robin Kothari, and Justin Thaler, we've been able to use the emerging "Laurent polynomial method" (1) to prove a tight lower bound for approximately counting a set S, given not only a membership oracle for S but also copies of the state |S> and the ability to reflect about the state, (2) to prove an oracle separation between the classes SBP and QMA, showing that in the black-box setting, "there are no succinct quantum proofs that a set is large," and (3) for other applications still in development. No quantum computing background is needed for this talk. Preprint at https://arxiv.org/abs/1904.08914

Are factors of sparse polynomials sparse? This is a really basic question and we are still quite far from understanding it in general. In this talk, I will discuss a recent result showing that this is in some sense true for multivariate polynomials when the polynomial has each variable appearing only with bounded degree. Our sparsity bound uses techniques from convex geometry, such as the theory of Newton polytopes and an approximate version of the classical Caratheodory's Theorem. Using our sparsity bound, we then show how to devise efficient deterministic factoring algorithms for sparse polynomials of bounded individual degree. The talk is based on joint work with Vishwas Bhargav and Ilya Volkovich.

We prove Sylvester-Gallai type theorems for quadratic polynomials. Specifically, we prove that if a finite collection Q, of irreducible polynomials of degree at most 2, satisfy that for every two polynomials Q1,Q2 ∈ Q there is a third polynomial Q3∈Q so that whenever Q1 and Q2 vanish then also Q3 vanishes, then the linear span of the polynomials in Q has dimension O(1). We also prove a colored version of the theorem: If three finite sets of quadratic polynomials satisfy that for every two polynomials from distinct sets there is a polynomial in the third set satisfying the same vanishing condition then all polynomials are contained in an O(1)-dimensional space. This answers affirmatively two conjectures of Gupta [Electronic Colloquium on Computational Complexity (ECCC), 21:130, 2014] that were raised in the context of solving certain depth-4 polynomial identities. To obtain our main theorems we prove a new result classifying the possible ways that a quadratic polynomial Q can vanish when two other quadratic polynomials vanish. Our proofs also require robust versions of a theorem of Edelstein and Kelly (that extends the Sylvester-Gallai theorem to colored sets).

If H is a matrix over a field F, then the rank-r rigidity of H, denoted R_{H}(r), is the minimum Hamming distance from H to a matrix of rank at most r over F. Giving explicit constructions of rigid matrices for a variety of parameter regimes is a central open challenge in complexity theory. In this work, building on Williams' seminal connection between circuit-analysis algorithms and lower bounds [Williams, J. ACM 2014], we give a construction of rigid matrices in P^NP. Letting q = p^r be a prime power, we show: - There is an absolute constant delta>0 such that, for all constants eps>0, there is a P^NP machine M such that, for infinitely many N's, M(1^N) outputs a matrix H_N in {0,1}^{N times N} with rigidity R_{H_N}(2^{(log N)^{1/4 - eps}}) >= delta N^2 over F_q. Using known connections between matrix rigidity and a number of different areas of complexity theory, we derive several consequences of our constructions, including: - There is a function f in TIME[2^{(log n)^{omega(1)}}]^NP such that f notin PH^cc. Previously, it was even open whether E^NP subset PH^cc. - For all eps>0, there is a P^NP machine M such that, for infinitely many N's, M(1^N) outputs an N times N matrix H_N in {0,1}^{N times N} whose linear transformation requires depth-2 F_q-linear circuits of size Omega(N 2^{(log N)^{1/4 - eps}}). The previous best lower bound for an explicit family of N \times N matrices was only Omega(N log^2 N / log log N), for super-concentrator graphs. Joint work with Lijie Chen to appear in FOCS 2019.

Worst-case complexity has been for decades the main paradigm of theoretical CS. The study of worst-case complexity has led to many beautiful upper and lower bounds, but this notion can be sometimes too rigid. In this informal talk I would like to explore whether it is possible to define a meaningful notion of *instance-based complexity*, assigning to any instance X of a computational problem a complexity measure c(X) that captures the running time needed to solve X. There are several obstacles to establishing such a measure, which we'll discuss, but I will offer some directions for progress. I've given a similar talk at the IAS ( https://video.ias.edu/csdm/2019/0415-BoazBarak ) but for the Banff audience I will keep it shorter, less formal, and also discuss some more recent thoughts. This talk will be best enjoyed with beer.

Conventional wisdom asserts that linear programs (LPs) perform poorly for max-cut and other constraint satisfaction problems, and that semidefinite programming and spectral methods are needed to give nontrivial bounds. In this talk, I will describe a recent result that stands in contrast to this wisdom: we show that surprisingly small LPs can give nontrivial upper bounds for constraint satisfaction problems. Even more surprisingly, the quality of our bounds depends on the spectral radius of the adjacency matrix of the associated graph. For example, in a random $\Delta$-regular $n$-vertex graph, the $\exp(c \frac{\log n}{\log \Delta})$-round Sherali--Adams LP certifies that the max cut has value at most $50.1\%$. In random graphs with $n^{1.01}$ edges, $O(1)$ rounds suffice; in random graphs with $n \cdot \log(n)$ edges, $n^{O(1/\log \log n)} = n^{o(1)}$ rounds suffice.

Lifting theorems in complexity theory are a method of transferring lower bounds in a weak computational model into lower bounds for a more powerful computational model, via function composition.​ There has been an explosion of lifting theorems in the last ten years, essentially reducing communication lower bounds to query complexity lower bounds. These theorems only hold for composition with very specific ``gadgets'' such as indexing and inner product. In this talk, we will present a generalization of the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget with high enough rank, in particular, for useful gadgets such as equality and greater-than. We will then explain how to apply our generalized theorem to solve two open problems: • We present the first result that demonstrates a separation in proof power for cutting planes with unbounded versus polynomially bounded coefficients. Specifically, we exhibit CNF formulas that can be refuted in quadratic length and constant line space in cutting planes with unbounded coefficients, but for which there are no refutations in subexponential length and subpolynomial line space if coefficients are restricted to be of polynomial magnitude. • We give the first explicit separation between monotone Boolean formulas and monotone real formulas. Namely, we give an explicit family of functions that can be computed with monotone real formulas of nearly linear size but require monotone Boolean formulas of exponential size. Previously only a non-explicit separation was known. This talk is based on joint work with Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, and Marc Vinyals.

Lifting theorems are theorems that relate the query complexity of a function f : {0, 1}^n → {0, 1} to the communication complexity of the composed function f ◦ g^n, for some “gadget” g : {0, 1}^b × {0, 1}^b →{0, 1}. Such theorems allow transferring lower bounds from query complexity to the communication complexity, and have seen numerous applications in the recent years. In addition, such theorems can be viewed as a strong generalization of a direct-sum theorem for the gadget g. We prove a new lifting theorem that works for all gadgets g that have logarithmic length and exponentially-small discrepancy, for both deterministic and randomized communication complexity. Thus, we increase the range of gadgets for which such lifting theorems hold considerably. Our result has two main motivations: First, allowing a larger variety of gadgets may support more applications. In particular, our work is the first to prove a randomized lifting theorem for logarithmic-size gadgets, thus improving some applications the theorem. Second, our result can be seen a strong generalization of a direct-sum theorem for functions with low discrepancy. Joint work with Arkadev Chattopadhyay, Yuval Filmus, Or Meir, Toniann Pitassi

We construct a simple and total XOR function F on 2n variables that has only O(n) spectral norm, O(n^2) approximate rank and O(n^{2.5}) approximate nonnegative rank. We show it has polynomially large randomized bounded-error communication complexity of Omega(sqrt(n)). This yields the first exponential gap between the logarithm of the approximate rank and randomized communication complexity for total functions. Thus, F witnesses a refutation of the Log-Approximate-Rank Conjecture which was posed by Lee and Shraibman (2007) as a very natural analogue for randomized communication of the still unresolved Log-Rank Conjecture for deterministic communication. The best known previous gap for any total function between the two measures was a recent 4th-power separation by Göös, Jayram, Pitassi and Watson (2017). Remarkably, after our manuscript was published in the public domain, two groups of researchers, Anshu-Boddu-Touchette (2018) and Sinha-de-Wolf (2018), showed independently that the function F even refutes the Quantum-Log-Approximate-Rank Conjecture. (Joint work with Nikhil Mande and Suhail Sherif)

The sunflower conjecture is one of the famous open problems in combinatorics. In attempting to improve the current known bounds, we discovered connections to objects studies in TCS, such as randomness extractors and DNFs, as well as to new questions in pseudo-randomness. I will describe some of these connections and the many open problems that arise. Based on joint works with Ryan Alweiss, Xin Li, Noam Solomon and Jiapeng Zhang.

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, 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 meaningful progress toward such a proof, some of it in the last few years. With the goal of making further progress, we study two interesting variants of the conjecture: First, we consider the analogue of the KRW conjecture for monotone circuits. In this setting, we are able to prove that the conjecture holds for a very broad range of cases: namely, our result holds for every outer function, and for every inner function whose hardness can be established by lifting. This includes in particular several interesting inner functions, such as s-t-connectivity, clique and the GEN function of Raz-McKenzie. For our second variant, we define a natural "semi-monotone" version of the KRW conjecture, which aims to bridge the monotone and the non-monotone settings. While we are not able to prove this version of the conjecture, we prove lower bounds on some closely related problems.

We investigate the problem of differentially private hypothesis selection: Given i.i.d. samples from an unknown probability distribution P and a set of m probability distributions H, the goal is to privately output a distribution from H whose total variation distance to P is comparable to that of the best such distribution. We present several algorithms for this problem which achieve sample complexity similar to those of the best non-private algorithms. These give new and improved learning algorithms for a number of natural distribution classes. Our results also separate the sample complexities of private mean estimation under product vs. non-product distributions.

A boolean function F : {0,1}^n -> {0,1} is said to be “k-critical” if it satisfies Pr[ F|R_p has decision-tree depth >= t ] <= (pk)^t for all p and t, where R_p : {x_1,…,x_n} -> {0,1,*} is the p-random restriction. For example, Hastad’s Switching Lemma (1986) states that every k-CNF formula is O(k)-critical. I will discuss an alternative switching lemma (using an entropy argument) which shows that size-s CNF formulas are O(log s)-critical. A recent extension of this argument establishes a tight bound of O((log s)/d)^d on the criticality of regular AC^0 formulas of depth d+1, where “regular” means that gates at the same height have equal fan-in. This strengthens several recent results for AC^0 circuits on their decision-tree size, Fourier spectrum, and the complexity of #SAT. (Paper to appear in CCC 2019.)

What is the smallest formula computing a given multivariate polynomial f(x)= ? In this talk I will present a paradigm for translating the known lower bound proofs for various subclasses of formulas into efficient proper learn= ing algorithms for the same subclass. Many lower bounds proofs for various subclasses of arithmetic formulas redu= ce the problem to showing that any expression for f(x) as a sum of =93simpl= e=94 polynomials T_i(x): f(x) =3D T_1(x) + T_2(x) + =85 + T_s(x), the number s of simple summands is large. For example, each simple summand = T_i could be a product of linear forms or a power of a low degree polynomia= l and so on. The lower bound consists of constructing a vector space of linear maps M, e= ach L in M being a linear map from the set of polynomials F[x] to some vect= or space W (typically W is F[X] itself) with the following two properties: (i) For every simple polynomial T, dim(M*T) is small, say = that dim(M*T) <=3D r. (ii) For the candidate hard polynomial f, dim(M*f) is large,= say that dim(M*f) >=3D R. These two properties immediately imply a lower bound: s >=3D R/r. The corresponding reconstruction/proper learning problem is the following: = given f(x) we want to find the simple summands T_1(x), T_2(x), =85, T_s(x) = which add up to f(x). We will see how such a lower bound proof can often be used to solve the rec= onstruction problem. Our main tool will be an efficient algorithmic solutio= n to the problem of decomposing a pair of vector spaces (U, V) under the simu= ltaneous action of a vector space of linear maps from U to V. Along the way we will also obtain very precise bounds on the size of formul= as computing certain explicit polynomials. For example, we will obtain for = every s, an explicit polynomial f(x) that can be computed by a depth three formula of size s but= not by any depth three formula of size (s-1). Based on joint works with Chandan Saha and Ankit Garg.

We consider the problems of testing isomorphism of tensors, p-groups, cubic forms, algebras, and more, which arise from a variety of areas, including machine learning, group theory, and cryptography. Despite a perhaps seeming similarity with Graph Isomorphism, the current-best algorithms for these problems (when given by bases) are still exponential - for most of them, even q^{n^2} over GF(q). Similarly, while efficient practical software exists for Graph Isomorphism, for these problems even the best current software can only handle very small instances (e.g., 10 x 10 x 10 over GF(13)). This raises the question of finding new algorithmic techniques for these problems, and/or of proving hardness results. We show that all of these problems are equivalent under polynomial-time reductions, giving rise to a class of problems we call Tensor Isomorphism-complete (TI-complete). We further show that testing isomorphism of d-tensors for any fixed d (at least 3) is equivalent to testing isomorphism of 3-tensors. Using the same techniques, we show two first-of-their-kind results for Group Isomorphism (GpI): (a) a reduction from isomorphism of p-groups of exponent p and class c < p, to isomorphism of p-groups of exponent p and class 2, and (b) a search-to-decision reduction for the latter class of groups in time |G|^{O(log log|G|)}. We note that while p-groups of class 2 have long been believed to be the hardest cases of GpI, as far as we are aware this is the first reduction from any larger class to this class of groups. Finally, we discuss a way to apply combinatorial methods from Graph Isomorphism (namely, Weisfeiler-Leman) to Group and Tensor Isomorphism. Based on joint works with Vyacheslav V. Futorny and Vladimir V. Sergeichuk (Lin. Alg. Appl., 2019; arXiv:1810.09219), with Peter A. Brooksbank, Yinan Li, Youming Qiao, and James B. Wilson (arXiv:1905.02518), and with Youming Qiao (arXiv:190X.XXXXX).

5-day workshop participants are welcome to use BIRS facilities (BIRS Coffee Lounge, TCPL and Reading Room) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 12 noon.