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...
Fix a metric (Riemannian or Finsler) on a compact manifold M.
The critical points of the length function on the free loop space
LM of M are the closed geodesics on M. Filtration by the length
function gives a link between the geometry of closed...
A few years ago Ichino-Ikeda formulated a quantitative version
of the Gross-Prasad conjecture, modeled after the classical work of
Waldspurger. This is a powerful local-to-global principle which is
very suitable for analytic and arithmetic...
Incidence geometry is a part of combinatorics that studies the
intersection patterns of geometric objects. For example, suppose
that we have a set of L lines in the plane. A point is called
r-rich if it lies in r different lines from the set. For a...
