2007-2008 seminars

Moran, Naor and Segev have asked what is the minimal r = r(n, k) for which there exists an (n,k)-monotone encoding of length r , i.e., a monotone injective function from subsets of size up to k of {1, 2,...,n} to r bits. Monotone encodings are...

In this work we re-visit the question of building cryptographic primitives that remain secure even when queried on inputs that depend on the secret key. This was investigated by Black, Rogaway, and Shrimpton in the context of randomized encryption...

I will describe a lower bound for the rank of any real matrix in which all diagonal entries are significantly larger in absolute value than all other entries. This simple result has a surprising number of applications in Geometry, Coding Theory...

Let G be a finitely generated group equipped with the word metric. Assume that G does not admit a bi-Lipschitz embedding into Hilbert space. How can we quantify the extent to which G is non-Hilbertian? A natural approach is to consider the Hilbert...

We give a probabilistic protocol that allows any two points in R^d to agree on a nearby integer lattice point in Z^d . The protocol uses shared randomness, but no communication. If the distance between the two points is delta, the probability of...

We prove that every key exchange protocol in the random oracle model in which the honest users make at most $n$ queries to the oracle can be broken by an adversary making $O(n^2)$ queries to the oracle. This improves on the previous $\Tilde{O}(n^6)$...

I will present a recent result of Green and Tao showing the following. Let P:F^n --> F be a polynomial in n variables over F of degree at most d . We say that P is "equidistributed" if it takes on each of its |F| values close to equally often. We...

Learning theory, and in particular PAC learning, was introduced by Valiant in 1984 and has since become a major area of research in theoretical and applied computer science. One natural question that was posed at the very inception of the field is...