2011-2012 Seminars

In joint work with Paul Valiant, we consider the tasks of estimating a broad class of statistical properties, which includes support size, entropy, and various distance metrics between pairs of distributions. Our estimators are the first proposed...

In FT-mollification, one smooths a function while maintaining good quantitative control on high-order derivatives. This is a continuation of my talk from last week, and I will continue to describe this approach and show how it can be used to show...

The braid group on n strands may be viewed as an infinite analog of the symmetric group on n elements with additional topological phenomena. It appears in several areas of mathematics, physics and computer sciences, including knot theory, algebraic...

In FT-mollification, one smooths a function while maintaining good quantitative control on high-order derivatives. I will describe this approach and show how it can be used to show that bounded independence fools polynomial threshold functions over...

Complexity theory, with some notable exceptions, typically studies the complexity of computing a function h(x) of a *given* input x. We advocate the study of the complexity of generating -- or sampling -- the output distribution h(x) for random x...

For a {0,1}-valued matrix M let CC(M) denote he deterministic communication complexity of the boolean function associated with M. The log-rank conjecture of Lovasz and Saks [FOCS 1988] states that CC(M) <= log^c(rank(M)) for some absolute constant c where rank(M) denotes the rank of M over the field of real numbers. We show that CC(M) <= c rank(M)/logrank(M) for some absolute constant c, assuming a well-known conjecture from additive combinatorics, known as the Polynomial Freiman-Ruzsa (PFR) conjecture. Our proof is based on the study of the "approximate duality conjecture" which was recently suggested by Ben-Sasson and Zewi [STOC 2011] and studied there in connection to the PFR conjecture. First we improve the bounds on approximate duality assuming the PFR conjecture. Then we use the approximate duality conjecture (with improved bounds) to get the aforementioned upper bound on the communication complexity of low-rank martices, and this part uses the methodology suggested by Nisan and Wigderson [Combinatorica 1995]. This is joint work with Eli Ben-Sasson and Shachar Lovett.

The talk will have 2 parts (between the parts we will have a break). In the first part, we will discuss two options for using groups to construct expander graphs (Cayley graphs and Schreier diagrams). Specifically, we will see how to construct...

I'll describe a physical implementation of zero knowledge proofs whose goal is to verify that two physical objects are identical, without revealing any information about them. Our motivation is the task of verifying that an about-to-be-dismantled...