Previous Conferences & Workshops

Oct
02
2007

Arithmetic Combinatorics

Difference Sets and the Primes
2:00pm|S-101

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

Oct
02
2007

Computer Science/Discrete Mathematics Seminar II

Unbounded-Error Communication Complexity of Symmetric Functions
Alexander Sherstov
10:30am|S-101

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