Seminars

Expander graphs are sparse graphs with good connectivity properties and they have become ubiquitous in theoretical computer science. Dimension expanders are a linear-algebraic variant where we ask for a constant number of linear maps that expand...

We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand. As an application, we give a monotonicity testing algorithm that makes $\tilde{O}(\sqrt{n}/\epsilon^2)$ non-adaptive queries to a function $f:\{0,1\}^n...

We construct publicly verifiable non-interactive arguments that can be used to delegate polynomial time computations. These computationally sound proof systems are completely non-interactive in the common reference string model. The verifier’s...

We prove a parallel repetition theorem for general games with value tending to 0. Previously Dinur and Steurer proved such a theorem for the special case of projection games. Our proofs also extend to the high value regime (value close to 1) and...

While this talk is a continuation of the one I gave on Tue Nov 25, it will be planned as an independent one. I will not assume knowledge from that talk, and will reintroduce that is needed. (That first lecture gave plenty of background material, and...

One of the great challenges posed by the laws of quantum mechanics is that the number of parameters required to describe a quantum state in general grows exponentially in the number of particles. This complexity is directly related to the phenomenon...

One of the great challenges posed by the laws of quantum mechanics is that the number of parameters required to describe a quantum state in general grows exponentially in the number of particles. This complexity is directly related to the phenomenon...

For a finitely presented group, the Word Problem asks for an algorithm which declares whether or not words on the generators represent the identity. The Dehn function is the time-complexity of a direct attack on the Word Problem by applying the...

The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game in terms of the value of the base game and the number of repetitions. In this work we give a simple transformation on games -- "fortification" -- and...