2007-2008 seminars

Current constructions of cryptographic primitives typically involve a large multiplicative computational overhead that grows with the desired level of security. We explore the possibility of implementing cryptographic primitives (such as encryption...

We introduce the notion of a Canonical Tester for a class of properties on distributions, that is, a tester strong and general enough that ``a distribution property in the class is testable if and only if the Canonical Tester tests it''. We...

The lecture will be a continuation of the previous week (March 4, 2008).

A Freiman isomorphism is a fundamental object in additive combinatorics that allows one to move an additive problem from one group to another, all while preserving the salient additive properties. In this talk, we will discuss a new mapping result...

The sign-rank of a real matrix M is the smallest rank of any real matrix whose entries have the same sign as the entries of M . We exhibit a 2^n x 2^n matrix computable by depth 2 circuits of polynomial size whose sign-rank is exponential in n . Our...

The disjointness function---determining if a number of sets share a common element---is a notorious example in communication complexity of a function which is hard, but it is hard to show it is hard. Determining both the randomized and quantum...

We present a tradeoff between the length of a 3-query probabilistically checkable proof of proximity (PCPP) and the best possible soundness obtained by querying it. Consider the task of distinguishing between "good" inputs w \in {0,1}^n that 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...