Madhu Sudan's Papers

Online papers

Ordering: Papers are sorted by their first publication date. To get full details on when/where the paper was published read the bibliography information.

Copyright warning: Most papers have appeared in, or will (hopefully) appear in, some journal or the proceedings of some conference. In all such cases, the copyright belongs to the publisher. The posting here is only for non-commercial, personal use. Please see the bibliographic information to find out who owns the copyright and other restrictions that apply.

Some of the links to papers published in 2004 and 2005 are broken. I am in the process of fixing them.

2008

Improved lower bound on the size of Kakeya sets over finite fields, (with Shubhangi Saraf). ( Previous version.)
2-transitivity is insufficient for local testability, (with Elena Grigorescu and Tali Kaufman); conf.pdf; full.pdf; bibliographic information.
Decodability of Group Homomorphisms beyond the Johnson Bound, (with Irit Dinur, Elena Grigorescu, and Swastik Kopparty); conf.pdf; full.pdf; bibliographic information.

2007

Algebraic Property Testing: The role of Invariance, (with Tali Kaufman); conf.pdf; full.pdf; bibliographic information.
Universal Semantic Communication I, (with Brendan Juba); conf.pdf; full.pdf; (an earlier version). bibliographic information.
Sparse Random Linear Codes are Locally Decodable and Testable, (with Tali Kaufman); conf.pdf; full.pdf; bibliographic information.
Amplifying Collision Resistance: A Complexity-Theoretic Treatment, (with Ran Canetti, Ronald L. Rivest, Luca Trevisan, Salil P. Vadhan, and Hoeteck Wee); conf.pdf; bibliographic information.

2006

On Dinur's Proof of the PCP Theorem, (with Jaikumar Radhakrishnan); paper.pdf; bibliographic information.
Local Decoding and Testing for Homomorphisms, (with Elena Grigorescu and Swastik Kopparty); conf.pdf; bibliographic information.
Robust local testability of tensor products of LDPC codes, (with Irit Dinur and Avi Wigderson); conf.pdf; bibliographic information.

2005

Reliable Transmission of Information, (A gentle introduction to the goals and techniques of coding theory. To be part of "The Princeton Companion to Mathematics" edited by Tim Gowers along with June Barrow-Green and Imre Leader); paper.pdf; bibliographic information.
Shorter PCPs verifiable in polylogarithmic time, (with E. Ben-Sasson, O. Goldreich, P. Harsha, and S. Vadhan); full.pdf; conf.pdf; bibliographic information.
Derandomizations of Auctions, (with G. Aggarwal, A. Fiat, A. Goldberg, J. Hartline, and N. Immorlica); conf.pdf; bibliographic information.
Simple PCPs with Poly-log Rate and Query Complexity, (with E. Ben-Sasson); full.ps; conf.ps; bibliographic information,
Optimal error-correction against computationally bounded noise, (with S. Micali, C. Peikert, and D. A. Wilson); full.ps; conf.ps; bibliographic information,

2004

Robust locally testable codes and products of codes (with E. Ben-Sasson); full.ps; conf.ps; bibliographic information,
Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding (with E. Ben-Sasson, O. Goldreich, P. Harsha, and S. Vadhan): full.ps; conf.ps; bibliographic information,

2003

Quick and Dirty Refereeing?: Summary, Full Text, bibliographic information.
Bounds on 2-query codeword testing (with E. Ben-Sasson and O. Goldreich): conf.ps, bibliographic information.
Derandomizing low degree tests via epsilon-biased spaces (with E. Ben-Sasson, S. Vadhan, and A. Wigderson): conf.ps, bibliographic information.
Reconstructing curves in three (and higher) dimensional spaces from noisy data (with D. Coppersmith): conf.ps, bibliographic information.

2002

Locally testable codes and PCPs of almost linear length (with O. Goldreich): full.ps, conf.ps, bibliographic information.
A fuzzy vault scheme (with A. Juels): conf.pdf, bibliographic information.
Decoding concatenated codes using soft information (with V. Guruswami): conf.ps, bibliographic information.
Reflections on ``Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes'' (with V. Guruswami): paper.ps, bibliographic information.
Harmonic broadcasting is optimal (with L. Engebretsen): full.pdf, conf.ps; bibliographic information.
Guessing secrets efficiently via list-decoding (with N. Alon, V. Guruswami, and T. Kaufman): conf.ps, bibliographic information.
Extensions to the Johnson bound (with V. Guruswami): paper.ps; bibliographic information.

2001

Complexity classifications of Boolean constraint satisfaction problems (with N. Creignou and S. Khanna): paper.ps; bibliographic information,
Ideal error-correcting codes: Unifying algebraic and number-theoretic algorithms: paper.ps; bibliographic information,
Coding theory: Tutorial & survey: paper.ps; bibliographic information,
Small PCPs with low query complexity (with P. Harsha): full.ps; conf.ps; bibliographic information,
The approximability of constraint satisfaction problems (with S. Khanna, L. Trevisan, and D. P. Williamson): journal.ps; bibliographic information.

2000

"Soft-decision" decoding of Chinese remainder codes (V. Guruswami and A. Sahai): conf.ps; bibliographic information.
Hardness of approximate hypergraph coloring (with V. Guruswami and J. Håstad): full.ps; conf.ps; bibliographic information.
Combinatorial bounds for list decoding (with V. Guruswami, J. Håstad, D. Zuckerman): full.ps; conf.ps; bibliographic information.
On representations of algebraic-geometric codes (with V. Guruswami): journ.ps; conf.ps; bibliographic information.
List decoding: Algorithms and applications: paper.ps; bibliographic information.
List decoding algorithms for certain concatenated codes (with V. Guruswami): journal.ps; conf.ps; bibliographic information.
Random walks with "Back Buttons" (with R. Fagin, A. Karlin, J. Kleinberg, P. Raghavan, S. Rajagopalan, R. Rubinfeld, and A. Tomkins.) journal.ps; conf.ps; bibliographic information.
List decoding: Algorithms and applications: paper.ps; bibliographic information,

1999

Hardness of approximating the minimum distance of a linear code (with I. Dumer and D. Micciancio): full.ps; conf.ps; bibliographic information.
Linear consistency testing (with Y. Aumann, J. Håstad, and M. O. Rabin.): journal.ps; conf.ps; bibliographic information.
Chinese remaindering with errors (with O. Goldreich and D. Ron): journal.ps; conf.ps; bibliographic information.
Pseudorandom generators without the XOR lemma (with L. Trevisan and S. Vadhan): journal.ps; conf.ps; bibliographic information.

1998

A tight characterization of NP with 3-query PCPs (with V. Guruswami, D. Lewin, and L. Trevisan): conf.ps; bibliographic information.
Probabilistically checkable proofs with low amortized query (with L. Trevisan): conf.ps; bibliographic information.
Improved decoding of Reed-Solomon and algebraic-geometry codes (with V. Guruswami): journal.ps; conf.ps; bibliographic information.
Probabilistic verification of proofs: paper.ps; bibliographic information.
Computational indistinguishability: A sample hierarchy (with O. Goldreich): journal.ps; conf.ps; bibliographic information.

1997

Algorithmic issues in coding theory conf.ps; bibliographic information.
A statistical perspective on data mining (with J. Hosking and E. Pednault): journal.ps; bibliographic information.
Decoding Reed-Solomon codes beyond the error-correction diameter conf.ps; bibliographic information.
Constraint satisfaction: The approximability of minimization problems (with S. Khanna and Luca Trevisan) conf.ps; bibliographic information.
Improved low degree testing and its applications (with S. Arora): full.ps; conf.ps; bibliographic information.
A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction (with S. Khanna and D. P. Williamson): conf.ps; bibliographic information.

1996

Decoding of Reed-Solomon codes beyond the error-correction bound: journal.ps; conf.ps; bibliographic information.
Gadgets, approximation, and linear programming (with L. Trevisan, G. B. Sorkin, and D. P. Williamson) journal.ps; (conf.ps + errata.ps); bibliographic information.
Adversarial queueing theory (with A. Borodin, J. Kleinberg, P. Raghavan, and D. P. Williamson): journal.ps; conf.ps; bibliographic information.
Robust characterizations of polynomials with applications to program testing (with R. Rubinfeld): journal.ps; bibliographic information.
The optimization complexity of constraint satisfaction problems (with S. Khanna): paper.ps; bibliographic information,

1995

Private information retrieval (with B. Chor, O. Goldreich, and E. Kushilevitz): journal.ps; conf.ps; bibliographic information.
Learning polynomials with queries: The highly noisy case (with O. Goldreich and R. Rubinfeld): journal.ps; conf.ps; bibliographic information.
Free bits, PCPs and non-approximability -- towards tight results (with M. Bellare and O. Goldreich): journal.ps; conf.ps; bibliographic information.
Linearity testing in characteristic two (with M. Bellare, D. Coppersmith, J. Håstad, and M. Kiwi): journal.ps; conf.ps; bibliographic information.
A geometric approach to betweenness (with B. Chor): journal.ps; conf.ps; bibliographic information.
Approximating minimum feedback sets and multicuts in directed graphs (with G. Even, J. Naor, and B. Schieber): journal.ps; conf.ps; bibliographic information.
Guaranteeing fair service to persistent dependent tasks (with A. Bar-Noy, A. Mayer, and B. Schieber): journal.ps; conf.ps; bibliographic information.
Some improvements to total degree tests (with K. Friedl): conf.ps; bibliographic information.

1994

On the role of algebra in the efficient verification of proofs: paper.ps; bibliographic information,
Approximate graph coloring by semidefinite programming (with D. Karger and R. Motwani): journal.ps; conf.ps; bibliographic information.
Motion planning on a graph (with C. Papadimitriou, P. Raghavan, and Hisao Tamaki): conf.ps; bibliographic information. A journal version of this paper is unlikely. Here is a fuller version and an appendix.
Priority encoding transmission (with A. Albanese, J. Bl\"omer, J. Edmonds, and M. Luby): journal.ps; conf.ps; bibliographic information.
On syntactic versus computational views of approximability (with S. Khanna, R. Motwani, and U. Vazirani): journal.ps; conf.ps; bibliographic information.
Computing roots of graphs is hard (with R. Motwani): journal.ps; bibliographic information.
The minimum latency problem (with A. Blum, P. Chalasani, D. Coppersmith, B. Pulleyblank, and P. Raghavan): conf.ps; bibliographic information.
Improved non-approximability results (with M. Bellare): conf.ps; bibliographic information.
Efficient routing and scheduling algorithms for optical networks (with A. Aggarwal, A. Bar-Noy, D. Coppersmith, R. Ramaswami, and Baruch Schieber): journal.ps; conf.ps; bibliographic information.

1993

On leave?

1992

Reconstructing algebraic functions from mixed data (with S. Ar, R. Lipton, and R. Rubinfeld): journal.ps; conf.ps; bibliographic information.
Proof verification and hardness of approximation problems (with S. Arora, C. Lund, R. Motwani, and M. Szegedy): journal.ps; conf.ps; bibliographic information.
Efficient checking of polynomials and proofs, and the hardness of approximation problems: Sorry - no online version; of this one - here's a pointer, though: Springer. Bibliographic information.
Highly resilient correctors for multivariate polynomials (with P. Gemmell): journal.ps; bibliographic information.
Self-testing polynomial functions efficiently and over rational domains (with R. Rubinfeld): conf.ps; bibliographic information.

1991

Connectivity properties of matroids (with M. Mihail) paper.ps; bibliographic information.
Self-testing/correcting for polynomials and for approximate functions (with P. Gemmell, R. Lipton, R. Rubinfeld, and A. Wigderson): conf.ps; bibliographic information.

1990

Online algorithms for locating checkpoints (with M. Bern, D. Greene, and A. Raghunathan): journal.ps; conf.ps; bibliographic information.