School of Mathematics

New Locally Decodable Codes from Lifting

Madhu Sudan
Microsoft Research
March 25, 2013

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 testing to see if some given word is close to a codeword. Codes derived from evaluations of low-degree multivariate polynomials give the simplest

Sensitivity Versus Block Sensitivity, II

Hao Huang
University of California, Los Angeles; Member, School of Mathematics
March 19, 2013

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 conjecture, and its connection with various combinatorial problems.