Video Lectures

In this survey lecture (which will be continued), I plan to explain basic aspects of the representation theory of finite groups, and how these are applied to various questions regarding expansion and random walks on groups. These applications...

Algorithms spend time on performing arithmetic computations, but often more on moving data, between the levels of a memory hierarchy and between parallel computing entities. Judging by the hardware evolution of the last few decades, the fraction of...

We give an algorithmic proof of Forster's Theorem, a fundamental result in communication complexity. Our proof is based on a geometric notion we call radial isotropic position which is related to the well-known isotropic position of a set of vectors...

The question whether or not parallel repetition reduces the soundness error is a fundamental question in the theory of protocols. While parallel repetition reduces (at an exponential rate) the error in interactive proofs and (at a weak exponential...

Green and Tao used the existence of a dense subset indistinguishable from the primes under certain tests from a certain class to prove the existence of arbitrarily long prime arithmetic progressions. Reingold, Trevisan, Tulsiani and Vadhan, and...

I will discuss the Green-Tao proof for existence of arbitrarily long arithmetic progressions in the primes. The focus will primarily be on the parts of the proof which are related to notions in complexity theory. In particular, I will try to...

Research in the area of privacy of data analysis has been flourishing recently, with a rigorous notion such as differential privacy regarding the desired level of privacy and sanitizing algorithms matching the definition for many problems. Most of...

I will first give an overview of several constructions of graph sparsifiers and their properties. I will then present a method of sparsifying a subgraph W of a graph G with optimal number of edges and talk about the implications of subgraph...