2009-2010 Seminars

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...

Sex has been called "the queen of problems in evolutionary biology" since it is pervasive in nature yet its functional significance has not been known. It has often been assumed that the shuffling of genes due to sex is an adaptation that...

I will survey some constructions of expander graphs using variants of Kazhdan property T . First, I describe an approach to property T using bounded generation and then I will describe a recent method based on the geometric properties of...

An XOR game is a very simple model of evaluating a distributed function f(x,y) . With probability p(x,y) a Verifier sends questions x, y to Alice and Bob, respectively. Without communicating, Alice and Bob then output a, b in {-1,+1} in the hope...