Schedule for: 18w5197 - Analytic techniques in Theoretical Computer Science

The 2-to-1 games conjecture is the weaker sibling of the famous and important Unique-games conjecture of [Khot02]. A recent sequence of four papers resolved a version of that former conjecture, which might count as a step towards a proof of the Unique-games conjecture, and in any case invalidates some approaches for refuting it. The proof relies crucially on some Expansion properties of the Grassmann-graph, an object that to our knowledge was not studied before in the context of theoretical Computer Science. In this talk I will explain the 2-to-1 and the Unique-games conjectures and their implications, the Grassman graph and its relevance, and hopefully also some key ideas of the proofs. This is joint work with Irit Dinur, Subhash Khot, Dror Minzer, and Muli Safra

For natural numbers t (Conference Room San Felipe)

Boolean Function Analysis, the study of functions on the Boolean cube {0,1}^n, forms an essential part of the "theoretician's toolkit". Recently, functions on other domains (such as the Grassmann scheme) have been studied along similar lines, motivated by applications to TCS and combinatorics. I will discuss this nascent field, Discrete Harmonic Analysis, and some of the domains it has been studied on.

Nisan and Szegedy showed that low degree Boolean functions are juntas, namely, they depend only on a constant number of their variables. Kindler and Safra showed a robust version of the above: low degree functions which are almost Boolean are close to juntas. We study the same question on the p-biased hypercube, for very small p. The p-biased hypercube is a product probability space in which each coordinate is 1 with probability p and 0 otherwise. In this space most of the measure is on n-bit strings whose Hamming weight about pn << n. It turns out that here new phenomena emerge. For example, the function x_1 + ... + x_n=p (where x_i \in {0,1}) is close to Boolean but not close to a junta. We characterize low degree functions that are almost Boolean and show that they are close to a new class of functions which we call sparse juntas. An interesting aspect of our proof is a new proof paradigm that relies on a local to global agreement theorem. We cover the p-biased hypercube by many smaller dimensional copies of the uniform hypercube, and approximate our function locally via the standard Kindler-Safra theorem for constant p. We then stitch the local approximations together into one global function that is a sparse junta. The stitching is made feasible via a new local-to-global agreement theorem, which is an extension of the classical direct product results to larger dimensions. Time permitting, I'll show another application of this paradigm: extending the classical AKKLR low-degree tests to the p-biased hypercube. Based on joint work with Irit Dinur and Yuval Filmus.

The Graph Matching problem is a robust version of the Graph Isomorphism problem: given two not-necessarily-isomorphic graphs, the goal is to find a permutation of the vertices which maximizes the number of common edges. We study a popular average-case variant; we deviate from the common heuristic strategy and give the first quasi-polynomial time algorithm, where previously only sub-exponential time algorithms were known. Based on joint work with Boaz Barak, Chi-Ning Chou, Zhixian Lei, and Yueqi Sheng.

I will talk aboutthe problem of computing the operator norm of a matrix mapping vectors in the space l_p to l_q, for different values of p and q. This problem generalizes the spectral norm of a matrix (p=q=2) and the Grothendieck problem (p=\infty, q=1), and has been widely studied in various reigmes. When p greater than or equal to q, the problem exhibits a dichotomy: constant factor approximation algorithms are known if 2 lies between p and q, and is hard to approximate within almost polynomial factors otherwise. The regime when q is greater than p, known as the _hypercontractive case_, is particularly significant for various applications but much less well understood. The case with p = 2 and q > 2 was studied by [Barak et al., STOC'12] who gave sub-exponential algorithms for a promise version of the problem (which captures small-set expansion) and also proved hardness of approximation results based on the Exponential Time Hypothesis. However, no NP-hardness of approximation was known for these problems for any p < q. We study the hardness of approximating matrix norms in both the above cases. We prove the following results: - We show that for any p < q, the operator norm of a given matrix is hard to approximate within almost polynomial factors, when 2 does not lie between p and q. This suggests that similar to the non-hypercontrative setting, the case when 2 does not lie between p and q may be qualitatively different. - We also obtain new (constant factor) hardness results in the non-hypercontractive case when q <= 2 <= p. The bounds we obtain are known to be tight in the cases when either p or q equals 2.

Pointwise (i.e., infinity-norm) approximation by polynomials has produced a treasure trove of efficient learning algorithms under arbitrary distributions for fundamental concept classes. A notable exception is the intersection of two halfspaces on {0,1}^n, shown 8 years ago (STOC 2010) to require a polynomial of the maximum possible degree, Omega(n), even for representation by sign (the weakest form of pointwise approximation). The proof was based on the probabilistic method, and the explicit construction of such an intersection of two halfspaces has remained an open problem. We solve this problem here, with an explicit construction of a halfspace h:{0,1}^n -> {-1,+1} such that the intersection of two copies of h cannot be represented by the sign of a polynomial of degree less than Omega(n). We further show that h by itself is the ``hardest'' of halfspaces for pointwise approximation by polynomials and rational functions, and determine the minimum error achievable by approximants of any given degree. This completes a line of work started by Myhill and Kautz (1961). We discuss applications to separating communication complexity classes. The proof features elements of approximation theory, random walks, and number theory. Our starting point is the construction, due to Ajtai et al. (1990), of a set of O(log m) of integers that are appear random modulo m in the sense of the discrete Fourier transform on Z/mZ.

The epsilon-approximate degree of a Boolean function is the minimum degree of a real polynomial that pointwise approximates f to error epsilon. Approximate degree has wide-ranging applications in theoretical computer science, from computational learning theory to communication complexity, circuit complexity, oracle separations, and even cryptography. This talk will survey what is known about approximate degree and its many applications, including striking recent progress on proving approximate degree lower bounds. This survey will also function as a primer for Mark Bun's followup talk.

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.

Two equivalent formulations of the classical PCP theorem, hardness of approximation for constraint satisfaction problem and hardness of approximation for the value of two-player games, lead to two distinct formulations of a quantum PCP conjecture. The first conjecture, the "Hamiltonian QPCP", comes out of condensed-matter physics. The second conjecture, the "games QPCP", is closely tied to questions from foundations of quantum mechanics and has applications to quantum cryptography. In the first part of the tutorial I will motivate and formulate the two conjectures. I will not assume background in quantum information, and keep the technical aspects light while still aiming to say enough to provide concrete intuition. In the second part of the tutorial I will dive deeper into the "games PCP" conjecture, on which there has been more progress recently. I will describe the issues that arise when considering classical techniques such as the Hadamard code or low-degree tests in the quantum settings. Time allowing, these investigations will bring us to a new, group-theoretic perspective on the classical tests. For background reading, see the survey arXiv:1309.7495, the more recent (and shorter) lecture notes http://users.cms.caltech.edu/~vidick/notes/ucsd/ucsd_mip.pdf, the (even shorter) blog post https://mycqstate.wordpress.com/2014/10/31/quantum-pcp-conjectures/, or the (longer...) paper arXiv:1801.03821.

Recovering a hidden signal or structure in the presence of random noise is a recurring theme in fundamental problems arising in computational complexity, cryptography, machine learning, and statistics. In the recent years, a Sum-of-Squares method, a hierarchy of generic semi-definite programming relaxations, has yielded a systematic approach for such "parameter estimation" problems. In this talk, I'll illustrate the SoS method for parameter estimation by means of a recent application of to learning mixture of gaussians with information theoretically optimal cluster-separation in quasi-polynomial time. No sub-exponential time algorithm was previously known in this regime. Based on joint works with Jacob Steinhardt and David Steurer.

I will present an algorithm that achieves the claim in the title. This is joint work with Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, and Michal Koucký.

We give an explicit pseudorandom generator with seed length poly(log m, 1/\delta) * log n that \delta-fools the class of all m-facet polytopes over {0,1}^n. The previous best seed length had linear dependence on m. As a corollary, we obtain a deterministic quasipolynomial time algorithm for approximately counting the number of feasible solutions of general {0,1}-integer programs. Joint work with Ryan O'Donnell (CMU) and Li-Yang Tan (Stanford).

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.

We present an oracle, A, relative to which BQP^A is not contained in PH^A. Following the approach of Aaronson [STOC, 2010], our oracle separation 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 AC0 circuit of quasi-polynomial size can distinguish between D and the uniform distribution with advantage better than polylog(N)/sqrt(N). Based on joint work with Ran Raz.

A k x n matrix is an MDS matrix if any k columns are linearly independent. Such matrices span MDS (Maximum Distance Separable) codes. A standard construction of such matrices is by Vandermonde matrices, which generate the Reed-Solomon codes. The following question arose in several applications in coding theory: what zero patterns can MDS matrices have? it turns out that there is a simple combinatorial characterization that is both necessary and sufficient over large enough fields (concretely, of size {n \choose k}). It was conjectured by Dau et al in 2014 that the same combinatorial characterization is also sufficient over much smaller fields, of size n+k-1. This conjecture is called the GM-MDS conjecture. Dau et al proposed an algebraic conjecture on the structure of polynomials which would imply the GM-MDS conjecture. It speculates that the GM-MDS conjecture can be resolved by an "algebraic" construction. We prove this algebraic conjecture, and as a corollary also the GM-MDS conjecture. https://arxiv.org/abs/1803.02523

Hyperbolic Programming is a generalization of SDP obtained by replacing determinants (whose zero free regions define the PSD cone) by hyperbolic polynomials, whose zero-free regions define hyperbolicity cones. One of the main questions in real algebraic geometry, called the Generalized Lax Conjecture, is whether this generalization is strict -- i.e., whether every hyperbolicity cone can be written as a section of a PSD cone of some (potentially larger) dimension. We study the quantitative version of this question, namely, how large does the dimension of the PSD cone need to be? We show that there exist (many) hyperbolicity cones in n dimensions of degree d, such that any semidefinite representation of them must have dimension roughly exponential in n^d, even if approximation is allowed. Our cones are random perturbations of the cones induced by the elementary symmetric polynomials. Constructing succinctly describable cones with this property remains an open question. The proof involves robust versions of several classical facts about real rooted polynomials. Joint with with Prasad Raghavendra, Nick Ryder, and Ben Weitz.

In this talk, we consider the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size. We present an explicit binary tree code with constant distance and alphabet size polylog(n), where n is the depth of the tree. This is the first improvement over a two-decade-old construction that has an exponentially larger alphabet of size poly(n). For analyzing our construction, we prove a bound on the number of integral roots a real polynomial can have in terms of its sparsity with respect to the Newton basis - a result of independent interest.

In the Minimum Hypergraph Bisection problem, the vertex set of a hypergraph has to be partitioned into two parts of equal size so that the number of hyperedges intersecting both parts is minimized. This problem is a natural generalization of the well-studied Minimum Bisection problem in graphs. We present a sharp distinction between Minimum Bisection in hypergraphs and graphs. Whereas it is well-known that all bi-criteria approximation algorithms for Minimum Bisection in graphs can be extended to hypergraphs with the exact same guarantees, we prove that this is not the case when consideringh true (i.e., non bi-criteria) approximation algorithms. Specifically, we show that Minimum Hypergraph Bisection admits an $\tilde{\mathcal{O}}(\sqrt{n})$ approximation algorithm. However, we also show that any $\alpha$-approximation algorithm for Minimum Hypergraph Bisection implies an approximation of $\Omega(\alpha^{-2})$ for Densest $k$-Subgraph. Thus, assuming the exponential time hypothesis there is no efficient approximation algorithm for Minimum Hypergraph Bisection with an approximation ratio $n^{poly(\log{\log{n}})}$. In particular, Minimum Hypergraph Bisection is much harder to approximate than Minimum Bisection in graphs, for which a logarithmic approximation algorithm exists. If time permits, the problem of constructing trees that are cut sparsifiers for hypergraph and vertex cuts will also be discussed. While similar trees lie at the heart of powerful algorithms for Minimum Bisection in graphs, we prove that this is not the case for hypergraphs. Joint work with Harald R\"{a}cke and Richard Stotz.