Back to main page

Workshop Schedule
Talk Abstracts

Workshop Schedule

Talk slots are 50 minutes long. The intended talk length is 40 minutes, leaving 10 minutes per talk for discussion.

Wednesday, March 26
Thursday, March 27
Friday, March 28

Talk Abstracts

Non-embeddability Theorems via Fourier Analysis

This talk will review some recent results proving lower bounds on the distortion needed to embed specific classes of finite metric spaces into L₁. This includes earth-mover metrics, edit distance metrics and the so-called negative type metrics.

Recent progress on invariance

I will discuss the recent progress in proving invariance principles with a few applications to social choice and additive combinatorics. A few Gaussian conjectures and their social-choice/hardness implications will also be presented.

The Invariance Principle - Applications to Approximation Algorithms and Hardness results

For many combinatorial optimization problems, it is NP-hard to find the optimal solution. Thus the focus shifts to the best approximation to the optimum that can be computed efficiently. The field of approximation algorithms deals with designing algorithms with proven approximation guarantees, while hardness of approximation deals with determining the limits to efficient approximation.
The invariance principle for low degree multi linear polynomials was first shown by Rotar. Quantitative versions of the principle were derived recently in Mossel et al. Since then, the invariance principle has fueled several developments in the field of approximation algorithms/hardness of approximation.
In this talk, we shall outline an application of the principle to obtain approximation algorithms and hardness results for Constraint Satisfaction Problems (CSP). CSPs encompass a large number of combinatorial optimization problems like Max-3-SAT, MaxCut etc. Many of these problems have been studied extensively over the last decade in computer science. Rather surprisingly, under a hardness assumption, the invariance principle leads to general results about all CSPs, subsuming a large number of known results. Roughly speaking, we obtain optimal algorithms and hardness results for every constraint satisfaction problem (CSP) under the Unique Games Conjecture.

Approximation Resistant Predicates From Pairwise Independence

Given a predicate P : [q]^k → {0,1} on k variables from a domain [q], we prove that P is approximation resistant (under the Unique Games Conjecture) if there exists a balanced pairwise independent distribution on [q]^k whose support is entirely contained in the set P⁻¹(1) of satisfying assignments of P.
Using constructions of pairwise independent distributions with small support, we obtain improved inapproximability of the Max k-CSP problem for all domain sizes q, even in the well-studied case of boolean variables.
This result can be viewed as, on the one hand, extending and simplifying the Gowers norm-based approach of Samorodnitsky and Trevisan (STOC 2006), and, on the other hand, as extending the Majority Is Stablest-based approach which has recently been very useful for obtaining strong inapproximability for Max 2-CSP problems.
Joint work with Elchanan Mossel.

3-Query Dictator Testing

"Dictator Testing" is a Property Testing problem with direct applications to PCP constructions and hardness of approximation. The task is to test if an unknown function f : {0,1}ⁿ → {0,1} is a "Dictator"—i.e., one of the n functions f (x) = x_i. However the number of queries allowed is even smaller than usual: only 2 or 3. To compensate, one only needs to reject "quasirandom" functions with high probability.
In this talk we consider the problem of Dictator Testing with 3 queries and perfect completeness. We show that the lowest possible soundness achievable is 5/8. The upper bound proof uses tools from Fourier analysis. The lower bound proof uses a semidefinite programming algorithm of Zwick.
Joint work with Yi Wu of Carnegie Mellon University.

The Chow Parameters Problem

A halfspace is a Boolean function of the form f (x) = sign(w⋅x − θ). Halfspaces (also known as linear threshold functions, weighted majority functions, threshold gates, etc.) are a simple, natural and well-studied class of functions with many applications in fields such as learning theory and complexity theory.
In 1961 C.K. Chow proved that every halfspace is completely specified by the values of its (n+1) degree-0 and degree-1 Fourier coefficients, also known as its Chow parameters. His result is nonconstructive in that it does not indicate how to efficiently obtain a representation of a halfspace from its Chow parameters.
We describe an efficient randomized approximation algorithm for the problem in the following sense. Given (sufficiently accurate) approximations of the Chow parameters of a halfspace f over n bits and any constant accuracy parameter ε > 0, the algorithm runs in Õ(n²) time and with high probability outputs a representation of a threshold function f′ which agrees with f on all but an ε fraction of the Boolean cube.
We describe several applications of the algorithm in learning theory and the design of voting systems.
Joint work with Ryan O'Donnell.

Multiple Oracles Are Better Than One

We study the problem of learning k-juntas given access to examples drawn from a number of different product distributions. Thus we wish to learn the class of functions f : {-1, 1}ⁿ → {-1, 1} that depend on at most k (unknown) coordinates. While the best known algorithms for the general problem of learning k-juntas require running time of n^k poly(n, 2^k), we show that given access to k different product distributions with biases separated by γ > 0, the function may be learned in time poly(n, 2^k, γ^−k). More generally, given access to t ≤ k different product distributions, the functions may be learned in time n^k/t poly(n, 2^k, γ^−k). Our techniques involve novel results in Fourier analysis relating Fourier expansions with respect to different biases and a generalization of Russo's formula.
Joint work with Elchanan Mossel.

Agnostically Learning Decision Trees

We give a query algorithm for agnostically learning decision trees with respect to the uniform distribution on inputs. Given black-box access to an arbitrary binary function f on the n-dimensional hypercube, our algorithm finds a function that agrees with f on almost (within an ε fraction) as many inputs as the best size-t decision tree in time poly(n, t, 1/ε). This is the first polynomial-time algorithm for learning decision trees in a harsh noise model.
Conceptually, our algorithm parallels recent work towards agnostically learning halfspaces due to Kalai et al. Algorithmically, it is significantly more challenging. The core of our learning algorithm is a procedure to implicitly solve a convex optimization problem over the L₁ ball in 2ⁿ dimensions using an approximate gradient projection method.
Joint work with Parikshit Gopalan and Adam Kalai.

A modified logarithmic Sobolev inequality for the Hamming cube

We will describe a modification of the logarithmic Sobolev inequality for the Hamming cube and show it implies a modified hypercontractive inequality for the cube, which is stronger than the Beckner-Bonami-Gross inequality for functions with small support. Time permitting, we will also discuss some applications to coding theory.

Partial Results on Reverse Hypercontractivity

In this talk we shall give a survey and modest results regarding reverse hypercontractivity. Our main motivation for studying this appears in a fairly recent paper by Mossel et al. which gives lower bounds on hitting probabilities for short time walks on the discrete hypercube. The question under consideration concerns optimal times for reverse hypercontractivity to hold for a finite-state-space Markov Semigroup. We shall give a bold but not entirely unfounded conjecture on the relation between this notion and the more familiar notion of Hypercontractivity.

Polynomials

Polynomials are fundamental objects in computer science that arise in a variety of contexts, such as error-correcting codes and circuit lower bounds. Despite intense research, many basic computational aspects of polynomials remain poorly understood. For example, although it is known that most functions cannot be approximated by low-degree multivariate polynomials, an explicit construction of such a function is still unknown.
In this talk we discuss some of the progress we have recently made towards understanding computational aspects of polynomials. In particular, we present our latest result that the sum of d pseudorandom generators for degree-1 polynomials is a pseudorandom generator for polynomials of degree d.

Open problems in discrete harmonic analysis

I will mention some open problems regarding Fourier analysis of Boolean functions.
Among the problems: The entropy/influence conjecture. The structure of Boolean function with low total influence. Fourier analysis of low complexity functions. Thresholds and noise-sensitivity for Boolean functions where PROB (x_i = 1) = p << 1. Relations with monotonicity and correlation inequalities. Moving away from product distributions.

The influences of variables on Boolean functions in product spaces

Poster presentation

Influences of variables on Boolean functions have been extensively studied during the last few decades. This study led to important applications in numerous fields. In this poster we consider the influences of variables on Boolean functions in general product spaces (endowed with a product measure). Unlike the case of the discrete cube where there is a clear definition of influences, in the general case at least three definitions were presented in different papers. We propose a family of definitions for the influences, that contains all the known definitions, as well as other natural definitions, as partial cases. We prove that the previously known theorems about influences in the general case, including the BKKKL theorem, can be improved by replacing the notion of influence by a "weaker" one.

The UGC hardness threshold of the Grothendieck problem

We consider the problem of, given a square matrix A, maximizing x^tAx where x can be chosen inside the unit L_p ball. When p = 2, this is simply a matter of finding the largest eigenvalue of A, which can be done in polynomial time. For p = ∞ the best polynomial time algorithm for the problem achieves an approximation ratio of O(log n), and a hardness result is known for a factor of log^b(n) for some constant b > 0.
We study the cases were 2 < p < ∞ — From a physics point of view this problem corresponds to computing the ground states of spin glasses in a hard-wall potential well of varying shapes. We show an algorithm chieving an approximation factor of C(p), where C(p) is the pth norm of a standard Gaussian. Assuming the unique games conjecture we show a matching hardness result, which implies that this approximation factor is tight.
Joint work with Assaf Naor and Gideon Schechtman.

Discrete harmonic analysis and the geometry of model-based phylogenetics

This talk will deviate slightly from the main theme of harmonic analysis on product spaces, and rather discuss an application of harmonic analysis in a different context: phylogenetics. Phylogenetics is the inference of the evolutionary history of a set of species using present-day sequence information. It turns out that a Fourier transform exists in this setting, which diagonalizes a certain class of models. After an introduction, we will give two examples of recent results showing how useful the Fourier transformed space can be: first, we describe in terms of convex geometry why phylogenetic inference using concatenation of several gene sequences can produce anomalous results. Second, we present a complete implicit characterization of the possible data sets corresponding to phylogenetic trees under several popular models of sequence evolution. This characterization shows that the relevant model spaces live on the boundary of a non-convex higher dimensional contractible space.

Part I: The Pattern Matrix Method for Lower Bounds on Quantum Communication
Part II: The Sign-Rank of AC⁰

Part I: In a breakthrough result, Razborov (2003) gave optimal lower bounds on the communication complexity of every function f of the form f (x, y) = D( | x AND y | ) for some D : {0, 1, ..., n} → {0, 1}, in the bounded-error quantum model with and without prior entanglement. This was proved by the multidimensional discrepancy method. We give an entirely different proof of Razborov's result, using the original, one-dimensional discrepancy method. This refutes the commonly held intuition (Razborov 2003) that the original discrepancy method fails for functions such as DISJOINTNESS.
More importantly, our communication lower bounds hold for a much broader class of functions for which no methods were available. Namely, fix an arbitrary function f : {0, 1}^n/4 → {0, 1} and let A be the Boolean matrix whose columns are each an application of f to some subset of the variables x₁, x₂, ..., x_n. We prove that the communication complexity of A in the bounded-error quantum model with and without prior entanglement is Ω(d), where d is the approximate degree of f. From this result, Razborov's lower bounds follow easily.
Our result establishes a large new class of total Boolean functions whose quantum communication complexity (regardless of entanglement) is at best polynomially smaller than their classical complexity.
The proof technique in this paper is novel and has two ingredients. The first is a certain equivalence of approximation and orthogonality in Euclidean n-space, which follows by linear-programming duality. The second is a new construction of suitably structured matrices with low spectral norm, which we realize using matrix analysis and the Fourier transform over (Z₂)ⁿ.

Part II:
The sign-rank of a matrix A = [A_ij] with +/-1 entries is the least rank of a real matrix B = [B_ij] with A_ijB_ij > 0 for all i, j. We obtain the first exponential lower bound on the sign-rank of a function in AC⁰. Namely, let f (x, y) = ∧_i=1^m ∨_j=1^m2 (x_ij ∧ y_ij). We show that the matrix [f (x, y)]_x, y has sign-rank 2^Ω(m). This in particular implies that Σ₂^cc ⊄ UPP^cc, which solves a long-standing open problem posed by Babai, Frankl, and Simon (1986).
Part II is joint work with A. A. Razborov.