2007-2008 seminars

This will be a survey of old and new problems and results in additive number theory.

We show that random sparse binary linear codes are locally testable and locally decodable (under any linear encoding) with constant queries (with probability tending to one). By sparse, we mean that the code should have only polynomially many...

In this work we construct explicit deterministic extractors from polynomial sources, namely from distributions sampled by low degree multivariate polynomials over finite fields. This naturally generalizes previous work on extraction from affine...

Let A be subset of {1,...,n}. We say that A is square sum-free if the sum of any two different elements of A is not a square. Erdos and Sarkozy asked whether a square sum-free set can have more than n(1/3+epsilon) elements (motivated by the sequence...

In their great 1960 paper "On the Evolution of Random Graphs" Paul Erdos and Alfred Renyi expresses a special interest in the behavior of the random graph G(n,p) when np was near one. Today we view it through the prism of Percolation Theory. Write c...

We shall discuss joint work with I Z Ruzsa in which it is shown that if A is a subset of {1,..,N} such that its difference set contains no number of the form $p-1$ for $p$ a prime, then $|A|=O(N\exp(-c\sqrt{4}{\log N}))$ for some absolute $c>0$.

The sign-rank of a real matrix M is the least rank of a matrix R in which every entry has the same sign as the Corresponding entry of M. We determine the sign-rank of every matrix of the form M=[ D(|x AND y|) ]_{x,y}, where D:{0,1,...,n}->{-1,+1} is...