Consider a group of measure preserving transformations acting on
a probability space. The limiting behavior of the nonconventional
ergodic averages associated with this action has been the subject
of much attention since the work of Furstenberg on...
Locally decodable codes (LDCs) are error-correcting codes that
allow for highly-efficient recovery of "pieces" of information even
after arbitrary corruption of a codeword. Locally testable codes
(LTCs) are those that allow for highly-efficient...
There are two important measures of the complexity of a boolean
function: the sensitivity and block sensitivity. Whether or not
they are polynomial related remains a major open question. In this
talk I will survey some known results on this...
The PCP theorem (Arora et. al., J. ACM 45(1,3)) says that every
NP-proof can be encoded to another proof, namely, a
probabilistically checkable proof (PCP), which can be tested by a
verifier that queries only a small part of the PCP. A
natural...