List of all recorded talks

Recorded Presentation # 32010 North American Association For Environmental Education

Recorded Presentation # 42010 North American Association For Environmental Education

Recorded Presentation # 52010 North American Association For Environmental Education

Geometric complexity theory (GCT)Geometric complexity theory (GCT) is an approach towards the fundamental lower bound problems of complexity theory through algebraic geometry and representation theory. This talk will give a brief introduction to GCT without assuming any background in algebraic geometry or representation theory.

How to Grow Your Lower BoundsI will survey the state of the art in proving hardness for data structure problems in the cellprobe model of computation.

How To Think About Mechanism DesignMechanism design studies optimization problems where the underlying data  such as the value of a good or the cost of performing a task  is initially unknown to the algorithm designer. Auction settings are canonical examples, where the private data is the willingness to pay the bidders for the goods on sale, and the optimization problem is to allocate the goods to maximize some objective, such as revenue or overall value to society. A "mechanism" is a protocol that interacts with participants and determines a solution to the underlying optimization problem. We first explain why designing mechanisms with good gametheoretic properties boils down to algorithm design in a certain "constrained computational model." We differentiate between singleparameter problems, where this computational model is well understood, and multiparameter problems, where it is not. We then study two specific problem domains: revenuemaximizing auctions, and the recent idea of analyzing auctions via a "Bayesian thought experiment"; and welfaremaximizing mechanisms, with an emphasis on blackbox reductions that transmute approximation algorithms into truthful approximation mechanisms.

Constructive Algorithms for Discrepancy MinimizationGiven a set system (V,S), V=[n] and S={S_1,ldots,S_m}, the minimum discrepancy problem is to find a 2coloring X:V > {1,+1}, such that each set is colored as evenly as possible, i.e. find X to minimize max_{j in [m]} sum_{i in S_j} X(i). In this paper we give the first polynomial time algorithms for discrepancy minimization, that achieve bounds similar to those known existentially using the socalled Entropy Method. We also give a first approximationlike result for discrepancy. Specifically we give efficient randomized algorithms to: 1. Construct an $O(sqrt{n})$ discrepancy coloring for general sets systems when $m=O(n)$, matching the celebrated result of Spencer up to constant factors. Previously, no algorithmic guarantee better than the random coloring bound, i.e. O((n log n)^{1/2}), was known. More generally, for $mgeq n$, we obtain a discrepancy bound of O(n^{1/2} log (2m/n)). 2. Construct a coloring with discrepancy $O(t^{1/2} log n)$, if each element lies in at most $t$ sets. This matches the (nonconstructive) result of Srinivasan cite{Sr}. 3. Construct a coloring with discrepancy O(lambdalog(nm)), where lambda is the hereditary discrepancy of the set system. In particular, this implies a logarithmic approximation for hereditary discrepancy. The main idea in our algorithms is to gradually produce a coloring by solving a sequence of semidefinite programs, while using the entropy method to guide the choice of the semidefinite program at each stage.

Bounded Independence Fools Degree2 Threshold FunctionsLet x be a random vector coming from any kwise independent distribution over {1,1}^n. For an nvariate degree2 polynomial p, we prove that E[sgn(p(x))] is determined up to an additive eps for k = poly(1/eps). This gives a large class of explicit pseudorandom generators against such functions and answers an open question of Diakonikolas et al. (FOCS 2009).
In the process, we develop a novel analytic technique we dub multivariate FTmollification. This provides a generic tool to approximate bounded (multivariate) functions by lowdegree polynomials (with respect to several different notions of approximation). A univariate version of the method was introduced by Kane et al. (SODA 2010) in the context of streaming algorithms. In this work, we refine it and generalize it to the multivariate setting. We believe that our technique is of independent mathematical interest. To illustrate its generality, we note that it implies a multidimensional generalization of Jackson's classical result in approximation theory due to (Ganzburg 1979).
To obtain our main result, we combine the FTmollification technique with several linear algebraic and probabilistic tools. These include the invariance principle of of Mossell, O'Donnell and Oleszkiewicz, anticoncentration bounds for lowdegree polynomials, an appropriate decomposition of degree2 polynomials, and a generalized hypercontractive inequality for quadratic forms which takes the operator norm of the associated matrix into account. Our analysis is quite modular; it readily adapts to show that intersections of halfspaces and degree2 threshold functions are fooled by bounded independence. From this it follows that Omega(1/eps^2)wise independence derandomizes the GoemansWilliamson hyperplane rounding scheme.
Our techniques unify, simplify, and in some cases improve several recent results in the literature concerning threshold functions. For the case of ``regular'' halfspaces we give a simple proof of an optimal independence bound of Th

The Coin Problem, and Pseudorandomness for Branching Programs / Pseudorandom Generators for Regular Branching ProgramsThe emph{Coin Problem} is the following problem: a coin is given, which lands on head with probability either $1/2 + eta$ or $1/2  eta$. We are given the outcome of $n$ independent tosses of this coin, and the goal is to guess which way the coin is biased, and to be correct with probability $ge 2/3$. When our computational model is unrestricted, the majority function is optimal, and succeeds when $eta ge c /sqrt{n}$ for a large enough constant $c$. The coin problem is open and interesting in models that cannot compute the majority function.
In this paper we study the coin problem in the model of emph{readonce width$w$ branching programs}. We prove that in order to succeed in this model, $eta$ must be at least $1/ (log n)^{Theta(w)}$. For constant $w$ this is tight by considering the recursive tribes function.
We generalize this to a emph{Dice Problem}, where instead of independent tosses of a coin we are given independent tosses of one of two $m$sided dice. We prove that if the distributions are too close, then the dice cannot be distinguished by a smallwidth readonce branching program.
We suggest one application for this kind of theorems: we prove that Nisan's Generator fools width$w$ readonce emph{permutation} branching programs, using seed length $O(w^4 log n log log n + log n log (1/eps))$. For $w=eps=Theta(1)$, this seedlength is $O(log n log log n)$. The coin theorem and its relatives might have other connections to PRGs. This application is related to the independent, but chronologicallyearlier, work of Braverman, Rao, Raz and Yehudayoff (which might be submitted to this FOCS).

Settling the Polynomial Learnability of Mixtures of GaussiansGiven data drawn from a mixture of multivariate Gaussians, a basic problem is to accurately estimate the mixture parameters. We give an algorithm for this problem that has a running time, and data requirement polynomial in the dimension and the inverse of the desired accuracy, with provably minimal assumptions on the Gaussians. As simple consequences of our learning algorithm, we can perform nearoptimal clustering of the sample points and density estimation for mixtures of $k$ Gaussians, efficiently.
The building blocks of our algorithm are based on the work (Kalai emph{et al}, STOC 2010)~cite{2Gs} that gives an efficient algorithm for learning mixtures of two Gaussians by considering a series of projections down to one dimension, and applying the emph{method of moments} to each univariate projection. A major technical hurdle in~cite{2Gs} is showing that one can efficiently learn emph{univariate} mixtures of two Gaussians. In contrast, because pathological scenarios can arise when considering univariate projections of mixtures of more than two Gaussians, the bulk of the work in this paper concerns how to leverage an algorithm for learning univariate mixtures (of many Gaussians) to yield an efficient algorithm for learning in high dimensions. Our algorithm employs emph{hierarchical clustering} and rescaling, together with delicate methods for backtracking and recovering from failures that can occur in our univariate algorithm.
Finally, while the running time and data requirements of our algorithm depend exponentially on the number of Gaussians in the mixture, we prove that such a dependence in necessary.
 All Talks
 Recorded Presentation # 3
 Recorded Presentation # 4
 Recorded Presentation # 5
 Geometric complexity theory (GCT)
 How to Grow Your Lower Bounds
 How To Think About Mechanism Design
 Constructive Algorithms for Discrepancy Minimization
 Bounded Independence Fools Degree2 Threshold Functions
 The Coin Problem, and Pseudorandomness for Branching Programs / Pseudorandom Generators for Regular Branching Programs
 Settling the Polynomial Learnability of Mixtures of Gaussians