Seminars

One of the major goals of complexity theory is to prove lower bounds for various models of computation. The theory often proceeds in buckets of three steps. The first is to come up with a collection of techniques. The second is to be frustrated at...

We study the control of a linear dynamical system with adversarial disturbances (as opposed to statistical noise). The objective we consider is one of regret: we desire an online control procedure that can do nearly as well as that of a procedure...

A set of n players, each holding a private input bit, communicate over a noisy broadcast channel. Their mutual goal is for all players to learn all inputs. At each round one of the players broadcasts a bit to all the other players, and the bit...

A linear matrix is a matrix whose entries are linear forms in some indeterminates $t_1,\dots, t_m$ with coefficients in some field $F$. The commutative rank of a linear matrix is obtained by interpreting it as a matrix with entries in the function...

Randomness dispersers are an important tool in the theory of pseudorandomness, with numerous applications. In this talk, we will consider one-bit strong dispersers and show their connection to erasure list-decodable codes and Ramsey graphs.

The...

Given an arbitrary graph, we show that if we are allowed to modify (say) 1% of the edges then it is possible to obtain a much smaller regular partition than in Szemeredi's original proof of the regularity lemma. Moreover, we show that it is...

In this talk, I will give an overview on how PCPs, combined with cryptographic tools, are used to generate succinct and efficiently verifiable proofs for the correctness of computations. I will focus on constructing (computationally sound) *succinct...

What is the largest number of projections onto k coordinates guaranteed in every family of m binary vectors of length n? This fundamental question is intimately connected to important topics and results in combinatorics and computer science (Turan...