## The Complexity of Transforming Problem Instances

Andrew Drucker

Massachusetts Institute of Technology; Member, School of Mathematics

September 27, 2012

Andrew Drucker

Massachusetts Institute of Technology; Member, School of Mathematics

September 27, 2012

Klim Efremenko

Tel-Aviv University; Member, School of Mathematics

September 27, 2012

A code C is said to be Locally Decodable Code with q queries if it is possible to recover any symbol x_j of a message x by making at most q queries to C(x), such that even if a constant fraction of C(x) is corrupted, the decoding algorithm returns the correct answer with high probability.

Eric Finster

Ecole Polytechnique Federal de Lausanne; Member, School of Mathematics

September 27, 2012

Radhika Ganapathy

Purdue University; Member, School of Mathematics

September 27, 2012

David Geraghty

Princeton University/Institute for Advanced Study

September 27, 2012

Wushi Goldring

Universite Paris 13; Member, School of Mathematics

September 27, 2012

Benedikt Ahrens

Universite Nice Sophia Antipolis; Member, School of Mathematics

September 25, 2012

Marius Beceanu

Rutgers, The State University of New Jersey; Member, School of Mathematics

September 25, 2012

Stefanos Aretakis

University of Cambridge; Member, School of Mathematics

September 25, 2012

Bhargav Bhatt

University of Michigan; Member, School of Mathematics

September 25, 2012