Seminars

We prove a \(\tilde{\Omega}(n^{1/5})\) lower bound on the query complexity of any non-adaptive two-sided error algorithm for testing whether an unknown n-variable Boolean function is monotone versus constant-far from monotone. This gives an...

The goal of computationally sound symbolic security is to create formal systems of cryptography which have a sound interpretation with respect to complexity-based notions of security. While there has been much progress in the development of such...

We consider the problem of the list-decodability of error correcting codes. The well-known Johnson bound implies that any code with good distance has good list-decodability, but we do not know many structural conditions on a code which guarantee...

In joint work with Ballard, Demmel, and Schwartz, we showed the communication cost of algorithms (also known as I/O-complexity) to be closely related to the small-set expansion properties of the corresponding computation graphs. This graph expansion...

A popular method in combinatorial optimization is to express polytopes \(P\), which may potentially have exponentially many facets, as solutions of linear programs that use few extra variables to reduce the number of constraints down to a polynomial...

The Martians built an amazingly fast computer and they run it to answer the great question of life, the universe and everything. They claim that the answer is 42. Will they be able to convince us that this is the right answer, assuming that we do...

In this talk we will present two structural results concerning low degree polynomials over \(GF(2)\). The first states that for any degree d polynomial \(f\) in \(n\) variables over \(GF(2)\), there exists a subspace of \(GF(2)^n\) with dimension \(...

How many arithmetic operations does it take to multiply two square matrices? This question has captured the imagination of computer scientists ever since Strassen showed in 1969 that \(O(n^{2.81})\) operations suffice. We survey the classical theory...

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 our recent simplifications. One of the main ingredients in the proof is a...

How many arithmetic operations does it take to multiply two square matrices? This question has captured the imagination of computer scientists ever since Strassen showed in 1969 that \(O(n^{2.81})\) operations suffice. We survey the classical theory...