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...
The Hirschman family, friends, colleagues, and former students
gathered on March 24, 2013, to remember and celebrate the life and
work of Albert O. Hirschman (1915–2012), Professor in the
School of Social Science at the
Institute.
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...
Discussions about constructive mathematics are usually derailed
by philosophical opinions and meta-mathematics. But how does it
actually feel to do constructive mathematics? A famous
mathematician wrote that "taking the principle of excluded
middle...
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...