Date  Speaker  Title/Abstract 
November 6, 2011  Igor Shinkar  Title: Some results in additive combinatorics.
Abstract: I will talk about FriemanRuzsa theorem and BalogSzemerediGowers theorem. If we have time we will also see the result of Samorodnitsky on testing linearity of $f : \{0,1\}^n \to \{0,1\}^n$. 
November 10, 2011  Igor Shinkar  I'll talk about some more result related to sumsets in $\{0,1\}^n$. A theorem of Ben Green says that for any $A \seq \{0,1\}^n$ of size $\eps 2^n$, the sumset $A+A$ contains a subspace of dimension $\delta n$, where $delta>0$ is some function of $\eps$. For the upper bound there is a set $A \seq \{0,1\}^n$ of size $0.1 2^n$, such that $A+A$ contains no subspace of dimension $n  \sqrt{n}$. The situation for $A+A+A$ is somewhat simpler. Specifically we'll see that for any $A \seq \{0,1\}^n$ of size $\eps \cdot 2^n$ the set $A+A+A$ contains a subspace of constant codimension. I'm also planning to show some relations to hardness of approximation.

November 30, 2011  Yuri Lima  Title: Szemerédi Regularity Lemma.
Abstract: Szemerédi regularity lemma is an important tool in discrete mathematics, specially in graph theory and additive combinatorics. It says that, in some sense, all graphs can be approximated by randomlooking graphs. The lemma helps in proving theorems for arbitrary graphs whenever the corresponding result is easy for random graphs. One of its applications is the triangle removal lemma which, as observed by Ruzsa and Szemerédi, gives a proof of Roth theorem on the existence of arithmetic progressions of length 3 in subsets of the integers with positive density. 
December 7, 2011  Avraham BenAroya  Title: LinearAlgebraic List Decoding of Folded ReedSolomon Codes
Abstract: An error correcting code of distance d is a mapping that encodes messages into codewords such that every two codewords differ on at least d coordinates. Such a code allows uniquely decoding any corrupted codeword from up to d/2 errors. In the setting of listdecoding, the decoder is given a corrupted codeword and is allowed to output a short list of candidates that should contain the original codeword. This relaxed notion of decoding allows handling more errors than is possible in the unique decoding setting. In this talk I will briefly survey the recent history of constructions of listdecodable codes over large alphabets which are based on ReedSolomon codes. I will then go on to present the latest technology in this area from a recent work of Guruswami (from CCC 2011). 
December 14, 2011  Daniel Reichman  This week I will talk about Turan and ErdosStone theorems in extremal graph theory. I'll also discuss some open problems.

December 21, 2011  Gil Cohen  I will talk about applications of arithmetic combinatorics for extractors. No prior knowledge is assumed.

December 28, 2011  Gil Cohen  This week I will continue the talk about extractors. No prior knowledge is assumed. Not even the knowledge from the previous lecture.

January 4, 2012  Gilad Tsur  I will talk about lower bounds for property testing.

January 11, 2012  Danny Vilenchik  I will talk about Message Passing algorithms and random Constraint Satisfaction Problems.

January 25, 2012  Elazar Goldenberg  I will talk about Decoding Direct Product Code.

February 1, 2012  Shlomo Jozeph  I will talk about the Algebrization barrier in complexity.
