| Date | Speaker | Title/Abstract |
| November 6, 2011 | Igor Shinkar | Title: Some results in additive combinatorics.
Abstract: I will talk about Frieman-Ruzsa theorem and Balog-Szemeredi-Gowers 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: Szemeredi Regularity Lemma.
Abstract: Szemeredi 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 random-looking 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 Szemeredi, 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 Ben-Aroya | Title: Linear-Algebraic List Decoding of Folded Reed-Solomon 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 list-decoding, 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 list-decodable codes over large alphabets which are based on Reed-Solomon 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 Erdos-Stone 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.
|