I will mention some challenges in understanding threshold behavior, influence of variables and sets of variables, and discrete Fourier expansion, for Boolean functions and related objects. A few results and quite a few open problems will be presented.
Let f : Z_2^n o {-1,1} be a boolean function. f is in the vector space of functions from Z_2^n into R, which is spanned by the Fourier characters, but the fact that we require f to be boolean imposes restrictions on its Fourier coefficients. It is then natural to consider boolean functions whose Fourier spectrums have some natural property, and try to obtain bounds on their computational complexity in various computational models.
Two such relevant Fourier properties are the number of non-zero Fourier coefficients, known as the sparsity of f, and the spectral norm of f, which is the sum of the absolute values of its Fourier coefficients.
In this talk I will survey several recent results and conjectures regarding the relations between the structure of the Fourier spectrum and complexity theory, in areas such as (parity) decision tree complexity, circuit complexity and communication complexity.
If A is a family of permutations of {1,2,...,n}, we say that A is t-intersecting if any two permutations in A agree on at least t distinct points. Deza and Frankl conjectured that for any integer t, a t-intersecting family of permutations of {1,2,...,n} has size at most (n-t)!, if n is sufficiently large depending on t. This was proved independently by the author and by Friedgut and Pilpel in 2008, using non-Abelian Fourier analysis, i.e. the representation theory of the symmetric group.
We make a stronger conjecture, namely that if n is sufficiently large depending on t, any family of permutations of {1,2,...,n} in which no two permutations agree on exactly t-1 points, has size at most (n-t)!. (This is analogous to Erdos' conjecture on families of r-sets with a forbidden intersection-size, proved by Frankl and Furedi in 1985.) We are able to prove this for t=2; interestingly, our representation-theoretic techniques fail to prove the conjecture for t>2.
We will also discuss some stability results, characterising the 'large' t-intersecting families in S_{n}, and several other open problems, including a Frankl-type conjecture on the maximum-sized t-intersecting families of permutations of {1,2,...,n} for *all* pairs (n,t).
The classical Friedgut-Kalai-Naor (FKN) theorem states that if most of the Fourier spectrum of a boolean function on {0,1}^n is concentrated on the first two levels then the function essentially depends on one coordinate. We extend this result to boolean functions on S_n whose Fourier spectrum is concentrated on the first two irreducible representations. When the function is balanced, we show that it essentially depends on either the image or the inverse image of one point. When the function is skewed, we show that it is close to a disjunction of double cosets (indicators of events of the type "i maps to j").
Joint work with David Ellis and Ehud Friedgut.
A celebrated result of Gowers states that for every epsilon > 0 there is a graph G so that every epsilon-regular partition of G (in the sense of Szemeredi's regularity lemma) has order given by a tower of exponents of height polynomial in 1/epsilon. In this note we give a new proof of this result that uses a construction and proof of correctness that are significantly simpler and shorter.
When numbers are added in the usual way, 'carries' occur. Using balanced arithmetic can cut the carries down by a factor of two and nothing does better. Generalizing to other than groups, the carries are cocycles and one is led to the following problem: let H be a normal subgroup of a finite group G. Let X be coset representatives for H in G. As a measure of efficiency, let C(X) be the number of pairs x,y in X with xy in X divided by |X|^2. Thus if X can be chosen as a subgroup, C(X) = 1 and there are no carries. One of our theorems says that if C(X) is greater than 7/9 then there is a subgroup K with KH=G and K intersecting H only in the identity (so the extension splits).
The many related topics make heavy use of additive combinatorics. Our best proof of the theorem above use approximate homomorphisms. This is joint work with Fernando Shao and Kannan Soundarajan.
The celebrated Green-Tao theorem states that there are arbitrarily long arithmetic progressions in the primes. In this talk, I will explain the ideas of the proof and discuss some recent simplifications.
One of the main ingredients in the proof is a relative Szemeredi theorem, which says that any subset of a pseudorandom set of integers of positive relative density contains long arithmetic progressions. Our main advance is a simple proof of a strengthening of the relative Szemeredi theorem, showing that a much weaker pseudorandomness condition is sufficient.
The proof of the new relative Szemeredi theorem has three main ingredients: (1) a transference principle/dense model theorem of Green-Tao and Tao-Ziegler (with simplified proofs given later by Gowers, and independently, Reingold-Trevisan-Tulsiani-Vadhan) applied with a discrepancy/cut-type norm (instea d of a Gowers uniformity norm as it was applied in earlier works), (2) a new counting lemma, and (3) Szemeredi's theorem as a black box.
Based on joint work with David Conlon and Jacob Fox.
In analogy with the regularity lemma of Szemeredi, regularity lemmas for polynomials given by Green and Tao and Kaufman and Lovett give a way of modifying a given collection of polynomials F = {P_1,...,P_m} to a new collection F', so that the polynomials in F' are "pseudorandom." These lemmas have various applications, such as (special cases) of Reed-Muller testing and worst-case to average-case reductions for polynomials. However, the transformation from F to F' is not algorithmic for either regularity lemma. We define new notions of regularity for polynomials, which are analogous to the above, but which allow for an efficient algorithm to compute the pseudorandom collection F'. In particular, when the field is of high characteristic, we can refine F into F' where every nonzero linear combination of polynomials in F' has desirably small Gowers norm.
Using the algorithmic regularity lemmas, we are able to obtain algorithmic versions of the above results. In particular, if a polynomial P of degree d is within (normalized) Hamming distance 1-1/p -\eps of some unknown polynomial of degree k over a prime field of order p (for k < d < p), then we give an efficient algorithm for finding a degree-k polynomial Q, which is within distance 1-1/p -\eta of P, for some \eta depending on \eps. This can be thought of as decoding the Reed-Muller code of order k *beyond* the list decoding radius, in the sense of finding one close codeword, when the received word P itself is a polynomial (of degree larger than k but smaller than p).
Joint work with Pooya Hatami and Madhur Tulsiani.
Ultraproducts can be used as a tool to extract a limiting continuous (or infinitary) object from a sequence of discrete (or finitary) objects, which in turn allows for methods of continuous (or infinitary) analysis (e.g. measure theory, ergodic theory, algebraic geometry, topological group theory) to be applied to discrete (or finitary) problems (e.g. graph theory, arithmetic combinatorics, or geometric group theory). A classic example of this strategy (though not initially phrased in the language of ultraproducts) is Gromov's use of the solution of Hilbert's fifth problem on classifying Lie groups to obtain his theorem on finitely generated groups of polynomial growth. Modern examples include the theory of graph limits, the work of Hrushovski and Breuillard, Green, and myself on approximate groups, and recent work of myself on algebraic versions of the Szemeredi regul arity lemma. In this talk we set out the basic theory of ultraproducts, and give some examples of how they can be used to bridge the gap between the discrete and continuous worlds.
The purpose of this talk is to show that even the most elementary problems in asymptotic extremal graph theory can be highly non-trivial. We study linear inequalities between graph homomorphism densities. It is known that every such inequality follows from an infinite number of certain applications of the Cauchy-Schwarz inequality. Lovasz and, in a slightly different formulation, Razborov asked whether it is true or not that every algebraic inequality between the homomorphism densities follows from a "finite" number of applications of the Cauchy-Schwarz inequality. In this talk, we show that the answer to this question is negative by showing that the problem of determining the validity of a linear inequality between homomorphism densities is undecidable.
I will survey what is known about the complexity of arithmetic circuits computing polynomials and rational functions with non-commuting variables, focusing on recent results and open problems. The talk is mainly based on several papers with Pavel Hrubes and Amir Yehudayoff.
In this talk, we will examine the spectrum of random k-lifts of d-regular graphs. We show that, for random shift k-lifts (which includes 2-lifts), if all the nontrivial eigenvalues of the base graph G are at most \lambda in absolute value, then with high probability depending only on the number n of nodes of G (and not on k), the absolute value of every nontrivial eigenvalue of the lift is at most O(\lambda).
While previous results on random lifts were asymptotically true with high probability in the degree of the lift k, our result is the first upperbound on spectra of lifts for bounded k. In particular, it implies that a typical small lift of a Ramanujan graph is almost Ramanujan, which might prove crucial in constructing large Ramanujan expanders of all degrees.
Joint work with Naman Agarwal and Vivek Madan.
Expander graphs are highly connected graphs that turn have many applications. We shall give a brief introduction to expanders and specifically to monotone expanders. Unlike general expanders, natural distributions on monotone graphs do not yield expanders. We shall explain how to construct monotone expanders, and discuss the proof.
Based on work with Jean Bourgain.
The structure of low rank matrices plays an important role in several fields of theoretical computer science, such as communication complexity, arithmetic circuits lower bounds and constructions of pseudo-random graphs. In particular, the following Ramsey-type question is of interest: given a matrix which is both low rank and sparse, what is the size of the largest zero rectangle that it must have? I will describe the connections of this problem to the above mentioned fields, some recent advances on it, and its relations to additive combinatorics.
I will discuss joint work with Rob Morris on the issue of counting the number of sets A in Z/NZ of a given size with doubling constant at most K. I will also mention some applications, for example to the problem of estimating the probability that if S is a random set of natural numbers then all except k natural numbers are the sum of two elements of S, and to the problem of finding an asymptotic for the clique number of a random Cayley graph on Z/NZ.
The classical Sylvester-Gallai Theorem states the following: given a finite set of points in the Euclidean plane, if the line through every pair of points passes through a third point, then all the points must be collinear. At a high level the result shows that many ``local" linear dependencies implies a ``global" bound on the dimension of the entire set of points. This result has been well studied in mathematics. In recent years variants of the theorem have also found applications to several structural results in theoretical computer science.
In this talk I will describe several extensions to the Sylvester-Gallai theorem - quantitative versions, high dimensional versions, colorful versions and approximate versions. I will also describe some of the applications and connections in theoretical computer science to areas such as polynomial identity testing and local algorithms for error correcting codes.
Based on joint works with Albert Ai, Zeev Dvir, Neeraj Kayal and Avi Wigderson.
I will talk about using flows to "uniformize" graphs, endowing them with a geometry that emphasizes certain aspects of their global structure. In analogy with conformal uniformization on surfaces, one can use these geometries to study the spectrum of the graph Laplacian. In particular, we resolve some conjectures of Spielman and Teng on low-dimensional graphs, and offer a different resolution of a conjecture of S. T. Yau about the spectrum of surfaces (previously solved by Korevaar in 1993).
This talk will establish a generic form of hardness amplification for the approximability of constant-depth Boolean circuits by polynomials. Specifically, we will show that if a Boolean circuit cannot be pointwise approximated by low-degree polynomials to within constant error in a certain one-sided sense, then an OR of disjoint copies of that circuit cannot be pointwise approximated even with very high error.
We describe how this result enables progress on several problems in complexity theory. First, we establish new bounds on the \emph{discrepancy and threshold weight} of constant-depth Boolean circuits. These results immediately yield new lower bounds on the communication and circuit complexity of functions in AC^0, and demonstrate strong limitations on existing PAC learning algorithms.
Second, we prove an \tilde{Omega}(n^{1/2}) lower bound on the \emph{approximate degree} of AND-OR trees of any constant depth. This lower bound is tight up to polylogarithmic factors, and thereby nearly completes a line of work on this problem.
Joint work with Mark Bun.
A classical result of Pansu and Semmes asserts that the Heisenberg group does not admit a bi-Lipschitz embedding into any Euclidean space. Several alternative proofs of this fact have been subsequently found, yielding the non-embeddability of the Heisenberg group into a variety of spaces, including uniformly convex spaces and L_1. These proofs rely on metric differentiation methods, i.e., the use of a limiting procedure to show that it suffices to rule out certain more structured embeddings. For certain applications, which will be explained in this talk, it is important to get quantitative bounds, in which case turning the metric differentiation arguments into quantitative statements is quite challenging and yields sub-optimal bounds. This talk, which assumes no prerequisites, will start by explaining the approaches to the Heisenberg embeddability question based on metri c differentiation, and then present a new and different approach based on Littlewood-Paley theory that yields asymptotically sharp distortion bounds for embeddings of balls in the Heisenberg group into uniformly convex spaces. We will end with a conjectural isoperimetric inequality on the Heisenberg group that is motivated by the new Littlewood-Paley approach, and explain its implications to approximation algorithms.
Given a compact Abelian group Z, an element z of that group, and a measurable function from it to another Abelian group, one can form a new function by taking the difference of the original function and its translate by z. This is the obvious discrete analog of differentiation, and defines an operator on functions called a differencing operator.
Certain 'higher-order' partial difference equations involving such operators arise naturally in pursuing a higher-dimensional analog of Gowers' approach to Szemeredi's Theorem. Given several elements of Z, one asks for a description of those functions on Z which vanish when one applies all of the resulting differencing operators. It turns that as the order of the difference equation increases, one can find surprisingly rich families of solutions. This amounts to a first step towards understanding the inverse problem for the `directional Gowers norms' relevant to the higher-dimensional Szemeredi Theorem.
I will talk about two neoclassical results showing pseudorandom properties of some simple functions over finite fields of small characteristic (such as F_{2^n}). The first result shows that some functions over F_{2^n}, such as the cubic residue character and Trace(x^(1/3)), are uncorrelated with degree n^{0.1} polynomials over F_2. The theorems and proofs are related to the Razborov-Smolensky method for proving lower bounds on arithmetic circuits over F_2. The second result (joint with Eli Ben-Sasson) shows that some other functions, such as Trace(x^7), are nonconstant on subspaces of small dimension, provided F_{2^n} has no large subfields. The proof uses an algebraic expression of the sum-product phenomenon involving properties of "subspace polynomials."
Let C be a linear subspace of the Hamming cube H. Let C' be the dual code.
Following Friedman and Tillich we try to estimate the rate of growth of metric balls in the discrete "torus" T = H/C' and use this to upperbound the cardinality of T, and therefore of C.
A notion of discrete Ricci curvature of metric spaces, as defined by Ollivier, turns out to be useful in some cases where C' has local structure (that is C is locally correctable / locally testable).
This approach leads to different (and, we would like to think, easier) proofs of some known upper bounds and to some occasional improvements in the bounds.
Joint work with Eran Iceland.
