Madhu Sudan: 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.

2015

• Communication with Contextual Uncertainty, (with Badih Ghazi, Ilan Komargodski, and Pravesh Kothari); paper.pdf; bibliographic information.
• Communication Complexity of Permutation-Invariant Functions, (with Badih Ghazi and Pritish Kamath); paper.pdf; bibliographic information.
• Robust testing of lifted codes with applications to low-degree testing, (with Alan Guo and Elad Haramaty); conf.pdf; paper.pdf; bibliographic information.

2014

• Communication with Imperfectly Shared Randomness, (with Clément Canonne, Venkatesan Guruswami, and Raghu Meka); conf.pdf; paper.pdf; bibliographic information.
• Streaming Lower Bounds for Approximating MAX-CUT, (with Michael Kapralov and Sanjeev Khanna); conf.pdf; paper.pdf; bibliographic information.
• Limitations on Testable Affine-Invariant Codes in the High-Rate Regime., (with Venkatesan Guruswami, Ameya Velingker and Carol Wang); paper.pdf; paper.pdf; bibliographic information.
• List decoding group homomorphisms between supersolvable groups., (with Alan Guo); conf.pdf; paper.pdf; bibliographic information.
• Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem., (with David Gamarnik); paper.pdf; bibliographic information.
• Approximating matching size from random streams., (with Michael Kapralov and Sanjeev Khanna); conf.pdf; paper.pdf; bibliographic information.

2013

• Optimal Error Rates for Interactive Coding I: Adaptivity and Other Settings., (with Mohsen Ghaffari and Bernhard Haeupler); conf.pdf; paper.pdf; bibliographic information.
• Limits of local algorithms over sparse random graphs , (with David Gamarnik); conf.pdf; paper.pdf; bibliographic information.
• Absolutely Sound Testing of Lifted Codes, (with Elad Haramaty and Noga Ron-Zewi); conf.pdf; paper.pdf; bibliographic information.

2012

• Deterministic Compression with Uncertain Priors, (with Elad Haramaty); conf.pdf; paper.pdf; bibliographic information.
• Queueing with Future Information, (with Joel Spencer and Kuang Xu); paper.pdf; bibliographic information.
• New affine-invariant codes from liftings, (with Alan Guo and Swastik Kopparty); conf.pdf; paper.pdf; bibliographic information.
• Communication Amid Uncertainty, (brief introduction) paper.pdf; bibliographic information.
• Sparse affine-invariant linear codes are locally testable, (with Eli Ben-Sasson and Noga Ron-Zewi); conf.pdf; paper.pdf; bibliographic information.
• Some closure features of locally testable affine-invariant properties, (with Alan Guo); paper.pdf; bibliographic information.
• A new upper bound on the query complexity for testing generalized Reed-Muller codes, (with Noga Ron-Zewi); conf.pdf; paper.pdf; bibliographic information.

2011

• Physical Limits of Communication (Invited Talk) (brief announcement), paper.pdf; bibliographic information.
• Delays and the Capacity of Continuous-Time Channels, (with Sanjeev Khanna); conf.pdf; paper.pdf; bibliographic information.
• On Sums of Locally Testable Affine Invariant Properties, (with Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, and Amir Shpilka); conf.pdf; paper.pdf; bibliographic information.
• Optimal testing of multivariate polynomials over small prime fields, (with Elad Haramaty and Amir Shpilka); conf.pdf; paper.pdf; bibliographic information.
• Patterns hidden from simple algorithms, Introduction to ("Technical Perspective" on) Mark Braverman's CACM article "Polylogarithmic independence fools bounded-depth Boolean circuits", paper.pdf; bibliographic information.
• Testing linear properties: Some general themes, (a survey); paper.pdf; bibliographic information.
• Compression without a common prior: An information-theoretic justification for ambiguity in language, (with Adam Kalai, Sanjeev Khanna, and Brendan Juba); conf.pdf; bibliographic information.

2010

• Symmetric LDPC codes are not necessarily locally testable, (with Eli Ben-Sasson, Ghid Maatouk, and Amir Shpilka); conf.pdf; paper.pdf; bibliographic information.
• Property Testing via Set-Theoretic Operations, (with Victor Chen and Ning Xie); conf.pdf; full.pdf; bibliographic information.
• Efficient Semantic Communication via Compatible Beliefs, (with Brendan Juba); conf.pdf; full.pdf; bibliographic information.
• Testing Linear-Invariant Non-Linear Properties: A Short Report, (with Arnab Bhattacharyya, Victor Chen, and Ning Xie); bibliographic information.
• Limits on the rate of locally testable affine-invariant codes , (with Eli Ben-Sasson). conf.pdf; full.pdf; bibliographic information.
• The P vs. NP problem, (survey aimed at broad readership explaining computational complexity and the P vs. NP problem). bibliographic information.
• Tight Asymptotic Bounds for the Deletion Channel with Small Deletion Probabilities, (with Adam Kalai and Michael Mitzenmacher). bibliographic information.
• Invariance in Property Testing, (a survey). bibliographic information.
• Kakeya-type sets in finite vector spaces, (with Swastik Kopparty, Vsevolod F. Lev and Shubhangi Saraf); bibliographic information.

2009

• Optimal testing of Reed-Muller codes, (with Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, and David Zuckerman); conf.pdf; full.pdf; bibliographic information.
• A Theory of Goal-Oriented Communication (with Oded Goldreich and Brendan Juba); bibliographic information.
• Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers (with Zeev Dvir, Swastik Kopparty, and Shubhangi Saraf); conf.pdf; full.pdf; bibliographic information.
• Succinct Representations of Codes with Applications to Testing (with Elena Grigorescu and Tali Kaufman); conf.pdf; full.pdf; bibliographic information.
• Locally Testable Codes Require Redundant Testers (with Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, and Michael Viderman); conf.pdf; full.pdf; bibliographic information.
• Probabilistically Checkable Proofs (a survey), bibliographic information.
• Testing Linear-Invariant Non-Linear Properties (with Arnab Bhattacharyya, Victor Chen, and Ning Xie); conf.pdf; full.pdf; bibliographic information.

2008

• Universal Semantic Communication II (with Brendan Juba) bibliographic information.
• Improved lower bound on the size of Kakeya sets over finite fields, (with Shubhangi Saraf); bibliographic information.
• Reliable Transmission of Information, (A gentle introduction to the goals and techniques of coding theory. Chapter VII.6 in "The Princeton Companion to Mathematics" edited by Tim Gowers along with June Barrow-Green and Imre Leader); bibliographic information.
• 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; early version; 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.

• Distributed Computing with Imperfect Randomness (with Shafi Goldwasser and Vinod Vaikuntanathan); full.pdf; conf.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); full.pdf; conf.pdf; bibliographic information.
• Short PCPs with Polylog Query Complexity (with E. Ben-Sasson); full.pdf; conf.pdf; bibliographic information.
• Optimal error-correction for computationally bounded noise (with S. Micali, C. Peikert, and D. A. Wilson); full.pdf; conf.pdf; bibliographic information.

2004

• Probabilistically Checkable Proofs, (Lecture notes, scribed by Venkatesan Guruswami); bibliographic information.
• From logarithmic advice to single-bit advice (with O. Goldreich and L. Trevisan); paper.pdf; bibliographic information.
• Robust locally testable codes and products of codes (with E. Ben-Sasson); full.pdf; conf.pdf; bibliographic information.
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding (with E. Ben-Sasson, O. Goldreich, P. Harsha, and S. Vadhan): full.pdf; conf.pdf; bibliographic information.

2003

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

2002

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

2001

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

2000

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

1999

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

1998

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

1997

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

1996

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

1995

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

1994

• On the role of algebra in the efficient verification of proofs: paper.pdf; bibliographic information,
• Approximate graph coloring by semidefinite programming (with D. Karger and R. Motwani): journal.pdf; conf.pdf; bibliographic information.
• Motion planning on a graph (with C. Papadimitriou, P. Raghavan, and Hisao Tamaki): conf.pdf; 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.pdf; conf.pdf; bibliographic information.
• On syntactic versus computational views of approximability (with S. Khanna, R. Motwani, and U. Vazirani): A journal.pdf; conf.pdf; bibliographic information.
• Computing roots of graphs is hard (with R. Motwani): journal.pdf; bibliographic information.
• The minimum latency problem (with A. Blum, P. Chalasani, D. Coppersmith, B. Pulleyblank, and P. Raghavan): conf.pdf; bibliographic information.
• Improved non-approximability results (with M. Bellare): conf.pdf; bibliographic information.
• Efficient routing and scheduling algorithms for optical networks (with A. Aggarwal, A. Bar-Noy, D. Coppersmith, R. Ramaswami, and Baruch Schieber): journal.pdf; conf.pdf; bibliographic information.

1993

• On leave?

1992

• Reconstructing algebraic functions from mixed data (with S. Ar, R. Lipton, and R. Rubinfeld): journal.pdf; conf.pdf; bibliographic information.
• Proof verification and hardness of approximation problems (with S. Arora, C. Lund, R. Motwani, and M. Szegedy): journal.pdf; conf.pdf; 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.pdf; bibliographic information.
• Self-testing polynomial functions efficiently and over rational domains (with R. Rubinfeld): conf.pdf; bibliographic information.

1991

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

1990

• Online algorithms for locating checkpoints (with Marshall Bern, Dan Greene, and Arvind Raghunathan): journal.pdf; conf.pdf; bibliographic information.