Madhu Sudan: Papers  Bibliographic Information

Online algorithms for locating checkpoints.
 Authors: Marshall Bern, Daniel H. Greene,
Arvind Raghunathan, and Madhu Sudan.

Proceedings of the Twenty Second Annual ACM Symposium
on Theory of Computing,
pages 359368, Baltimore, Maryland, 1416 May 1990 (
conf.pdf).
 Algorithmica, 11(1): 3352, January 1994.

Selftesting/correcting for polynomials and for
approximate functions.
 Authors: Peter Gemmell, Richard Lipton, Ronitt Rubinfeld,
Madhu Sudan, and Avi Wigderson.
 Extended abstract. Paper 27 below
contains full reports of parts of this paper.

Proceedings of the Twenty Third Annual ACM Symposium
on Theory of Computing,
pages 3242, New Orleans, Louisiana, 68 May 1991.

Connectivity properties of matroids.
 Authors: Milena Mihail and Madhu Sudan.
 Technical Report, Computer Science Division,
University of California at Berkeley, CSD91662, 1991.

Selftesting polynomial functions efficiently and
over rational domains.
 Authors: Ronitt Rubinfeld and Madhu Sudan.
 Extended abstract. Paper 27 below
contains full reports of parts of this paper.

Proceedings of the Third Annual ACMSIAM Symposium on
Discrete Algorithms,
pages 2332, Orlando, Florida, 2729 January 1992.

Highly resilient correctors for multivariate polynomials.
 Authors: Peter Gemmell and Madhu Sudan.
 Information Processing Letters,
43(4): 169174, September 1992.

Efficient Checking of Polynomials and Proofs and the
Hardness of Approximation Problems.
 Author: Madhu Sudan.
 Ph.D. Thesis, Computer Science Division, University of
California at Berkeley, 1992.
 Republished as a research monograph as part of the
ACM Distinguished Theses Series.
Lecture Notes in Computer Science, no. 1001, Springer, 1996.

Proof verification and the hardness of approximation problems.
 Authors: Sanjeev Arora, Carsten Lund, Rajeev Motwani,
Madhu Sudan, and Mario Szegedy.

Proceedings of the 33rd Annual Symposium on Foundations
of Computer Science,
pages 1423, Pittsburgh, Pennsylvania, 2427 October 1992
(conf.pdf).
 Journal of the ACM, 45(3): 501555, May 1998.

Reconstructing algebraic functions from mixed data.
 Authors: Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld,
and Madhu Sudan.
 Proceedings of the 33rd Annual Symposium on Foundations
of Computer Science,
pages 503512, Pittsburgh, Pennsylvania, 2427 October 1992
(conf.pdf).
 SIAM Journal on Computing,
28(2): 487510, April 1999.

Efficient routing in optical networks.
 Authors: Alok Aggarwal, Amotz BarNoy, Don Coppersmith,
Rajeev Ramaswami, Baruch Schieber, and Madhu Sudan,

Conference version was titled
Efficient routing and scheduling algorithms for optical
networks.
 Proceedings of the Fifth Annual ACMSIAM Symposium on
Discrete Algorithms,
pages 412423, Philadelphia, Pennsylvania, 2325 January 1994
(conf.pdf).
 Journal of the ACM,
43(6):9731001, November 1996.

Improved nonapproximability results.
 Authors: Mihir Bellare and Madhu Sudan.

Proceedings of the Twenty Sixth Annual ACM Symposium
on Theory of Computing,
pages 184193, Montreal, Quebec, Canada, 2325 May 1994.

The minimum latency problem.
 Authors: Avrim Blum, Prasad Chalasani, Don Coppersmith,
Bill Pulleyblank, Prabhakar Raghavan, and Madhu Sudan.

Proceedings of the Twenty Sixth Annual ACM Symposium
on Theory of Computing,
pages 163171, Montreal, Quebec, Canada, 2325 May 1994.

Computing roots of graphs is hard.
 Authors: Rajeev Motwani and Madhu Sudan.
 Discrete Applied Mathematics,
54(1):8188, September 1994.

On syntactic versus computational views of approximability.
 Authors: Sanjeev Khanna, Rajeev Motwani,
Madhu Sudan, and Umesh Vazirani.
 Proceedings of the 35th Annual Symposium on
Foundations of Computer Science,
pages 819830, Santa Fe, New Mexico, 2022 November 1994
(conf.pdf).
 SIAM Journal on Computing,
28(1): 164191, February 1999.

Priority encoding transmission.
 Authors: Andres Albanese, Johannes Blomer, Jeff Edmonds,
Michael Luby, and Madhu Sudan,
 Proceedings of the 35th Annual Symposium on
Foundations of Computer Science,
pages 604612, Santa Fe, New Mexico, 2022 November 1994
(conf.pdf).
 IEEE Transactions on Information Theory,
42(6): 17371744, November 1996.

Motion planning on a graph.
 Authors: Christos Papadimitriou, Prabhakar Raghavan,
Madhu Sudan, and Hisao Tamaki.
 Proceedings of the 35th Annual Symposium on
Foundations of Computer Science,
pages 511520, Santa Fe, New Mexico, 2022 November 1994.

Approximate graph coloring by semidefinite programming.
 Authors: David Karger, Rajeev Motwani, and Madhu Sudan.
 Proceedings of the 35th Annual Symposium on
Foundations of Computer Science,
pages 213, Santa Fe, New Mexico, 2022 November 1994
(conf.pdf).
 Journal of the ACM,
45(2): 246265, March 1998.

On the role of algebra in the efficient verification of proofs.
 Authors: Madhu Sudan.
 Proceeings of the Workshop of Algebraic Methods in
Complexity Theory (AMCOT), Indian Institute of Mathematical Sciences,
Chennai, India, December 1994.

Some improvements to total degree tests.
 Authors: Katalin Friedl and Madhu Sudan.
 Proceedings of the 3rd Annual Israel Symposium on Theory
of Computing and Systems,
pages 190198, Tel Aviv, Israel, 46 January 1995.
 Erratum: Due to a bizzare latexing error
that I failed to detect before sending the paper off, all capitalized
Greek letters are missing in the proceedings version of this paper.
As a result, it would be better to also cite the online version
as "Corrected version available online at
http://people.csail.mit.edu/madhu/papers/1995/friedl.pdf", or the
arxiv'ed version below.

arXiv:1307.3975 [cs.CC], 15 July 2013.
(arxiv.pdf.)

Guaranteeing fair service to persistent dependent tasks.
 Authors: Amotz BarNoy, Alain Mayer, Baruch Schieber,
and Madhu Sudan.
 Proceedings of the Sixth Annual ACMSIAM Symposium on
Discrete Algorithms,
pages 243252, San Francisco, California, 2224 January 1995
(conf.pdf).
 SIAM Journal on Computing,
27(4): 11681189, August 1998.

Approximating minimum feedback sets and multicuts in
directed graphs.
 Authors: Guy Even, Joseph (Seffi) Naor, Baruch Schieber,
and Madhu Sudan.
 Proceedings of the 4th MPS Conference on Integer
Programming and Combinatorial Optimization,
Copenhagen, Denmark, Lecture Notes in Computer Science, v. 920,
pages 1424, 1995
(conf.pdf).
 Algorithmica, 20(2): 151174, February 1998.

A geometric approach to betweenness.
 Authors: Benny Chor and Madhu Sudan.
 Third European Symposium on Algorithms,
Lecture Notes in Computer Science v. 979,
pages 227239, Corfu, Greece, 1995
(conf.pdf).
 SIAM Journal on Discrete Mathematics,
11(4): 511523, November 1998.

Linearity testing over characteristic two.
 Authors: Mihir Bellare, Don Coppersmith, Johan Håstad,
Marcos Kiwi, and Madhu Sudan.
 Proceedings of the 36th Annual Symposium on
Foundations of Computer Science,
pages 432441, Milwaukee, Wisconsin, 2325 October 1995
(conf.pdf).
 IEEE Transactions on Information Theory,
42(6): 17811795, November 1996.

Free bits, PCP and nonapproximability  towards
tight results.
 Authors: Mihir Bellare, Oded Goldreich, and Madhu Sudan.
 Proceedings of the 36th Annual Symposium on Foundations
of Computer Science,
pages 422431, Milwaukee, Wisconsin, 2325 October 1995
(conf.pdf).
 SIAM Journal on Computing,
27(3): 804915, June 1998.

Learning polynomials with queries: The highly noisy case.
 Authors: Oded Goldreich, Ronitt Rubinfeld, and Madhu Sudan.
 Proceedings of the 36th Annual Symposium on Foundations
of Computer Science,
pages 294303, Milwaukee, Wisconsin, 2325 October 1995
(conf.pdf).
 SIAM Journal on Discrete Mathematics,
13(4):535570, November 2000.

Private information retrieval.
 Authors: Benny Chor, Oded Goldreich, Eyal Kushilevitz,
and Madhu Sudan.
 Proceedings of the 36th Annual Symposium on Foundations
of Computer Science,
pages 4150, Milwaukee, Wisconsin, 2325 October 1995
(conf.pdf).
 Journal of the ACM,
45(6):965981, November 1998.

The optimization complexity of constraint satisfaction problems.
 Authors: Sanjeev Khanna and Madhu Sudan,
 Subsumed by paper 31 below.
 Technical Note, Stanford University, Computer
Science Department, CSTN9629, January 1996.

Robust characterizations of polynomials with applications to
program testing.
 Authors: Ronitt Rubinfeld and Madhu Sudan.
 Journal version of parts of the papers
2 and 4 above.
 SIAM Journal on Computing,
25(2):252271, April 1996.

Adversarial queueing theory.
 Authors: Allan Borodin, Jon Kleinberg, Prabhakar Raghavan,
Madhu Sudan, and David P. Williamson.
 Proceedings of the TwentyEighth Annual ACM Symposium
on the Theory of Computing,
pages 376385, Philadelphia, Pennsylvania, 2224 May 1996.
(conf.pdf).
 Journal of the ACM,
48(1):1338, January 2001.

Gadgets, approximation, and linear programming.
 Authors: Luca Trevisan, Gregory B. Sorkin, Madhu Sudan,
and David P. Williamson.
 Proceedings of the 37th Annual Symposium on Foundations
of Computer Science,
pages 617626, Burlington, Vermont, 1416 October 1996.
(conf.pdf, including errata).
 SIAM Journal on Computing,
29(6): 20742097, December 2000.

Decoding of Reed Solomon codes beyond the errorcorrection bound.
 Authors: Madhu Sudan.
 Conference version was titled
Maximum likelihood decoding of Reed Solomon codes.
 Proceedings of the 37th Annual Symposium on Foundations
of Computer Science,
pages 164172, Burlington, Vermont, 1416 October 1996
(conf.pdf).
 Journal of Complexity,
13(1): 180193, March 1997.

A complete classification of the approximability of
maximization problems derived from Boolean constraint
satisfaction.
 Authors: Sanjeev Khanna, Madhu Sudan, and David P. Williamson.
 Subsumes 26 above. Subsumed by
56 below.
 Proceedings of the TwentyNinth Annual ACM Symposium on
Theory of Computing,
pages 1120, El Paso, Texas, 46 May 1997.

Improved low degree testing and its applications.
 Authors: Sanjeev Arora and Madhu Sudan.
 Proceedings of the TwentyNinth Annual ACM Symposium
on Theory of Computing,
pages 485495, El Paso, Texas, 46 May 1997
(conf.pdf).
 Combinatorica, 23(3): 365426, 2003.

Constraint satisfaction:
The approximability of minimization problems.
 Authors: Sanjeev Khanna, Madhu Sudan, and Luca Trevisan.
 Subsumed by 56 below.
 Proceedings of the 12th Annual IEEE Conference on
Computational Complexity,
pages 282296, Ulm, Germany, 2427 June, 1997.

Decoding ReedSolomon codes beyond the errorcorrection diameter.
 Authors: Madhu Sudan.
 Proceedings of the 35th Annual Allerton Conference on
Communication, Control and Computing,
pages 215224, 29 September  1 October, 1997.

A statistical perspective on data mining.
 Authors: Jonathan Hosking, Edwin Pednault, and Madhu Sudan.
 Future Generation Computer Systems,
Special Issue on Data Mining, 13(23): 117134, November 1997.

Algorithmic issues in coding theory.
 Authors: Madhu Sudan.
 Proceedings of the 17th Annual Conference on Foundations
of Software Technology and Theoretical Computer Science,
Kharagpur, India, 1820 December, 1997.
S. Ramesh and G. Sivakumar (Eds.) Lecture Notes in Computer Science,
1346:184199, Springer, Berlin, 1997.

Computational indistinguishability: A sample hierarchy.
 Authors: Oded Goldreich and Madhu Sudan.
 Proceedings of the Thirteenth Annual IEEE Symposium on
Computational Complexity,
pages 2433, Buffalo, New York, 1518 June, 1998
(conf.pdf).
 Journal of Computer and System Sciences,
59(2): 253269, October 1999.

Probabilistic verification of proofs.
 Authors: Madhu Sudan.
 Proceedings of the International Congress of
Mathematicians, Berlin 1998, August 1827,
Documenta Mathematica, Extra Volume ICM 1998, III, 461470.

Improved decoding of ReedSolomon codes and algebraicgeometry
codes.
 Authors: Venkatesan Guruswami and Madhu Sudan.
 Proceedings of the 39th Annual Symposium on Foundations
of Computer Science,
pages 2837, Palo Alto, California, 811 November, 1998
(conf.pdf).
 IEEE Transactions on Information Theory,
45(6): 17571767, September 1999.

Probabilistically checkable proofs with low amortized
query complexity.
 Authors: Madhu Sudan and Luca Trevisan.
 Proceedings of the 39th Annual Symposium on Foundations
of Computer Science,
pages 1827, Palo Alto, California, 811 November, 1998.

A tight characterization of NP with 3query PCPs.
 Authors: Venkatesan Guruswami, Daniel Lewin, Madhu Sudan,
and Luca Trevisan.
 Proceedings of the 39th Annual Symposium on Foundations
of Computer Science,
pages 817, Palo Alto, California, 811 November, 1998.

Pseudorandom generators without the XOR Lemma.
 Authors: Madhu Sudan, Luca Trevisan, and Salil Vadhan.
 Proceedings of the ThirtyFirst Annual ACM Symposium
on Theory of Computing,
pages 537546, Atlanta, Georgia, 14 May 1999
(conf.pdf).
 Journal of Computer and System Sciences,
62(2): 236266, March 2001.

Chinese remaindering with errors.
 Authors: Oded Goldreich, Dana Ron, and Madhu Sudan.
 Proceedings of the ThirtyFirst Annual ACM Symposium
on Theory of Computing,
pages 225234, Atlanta, Georgia, 14 May 1999
(conf.pdf).
 IEEE Transactions on Information Theory,
46(4): 13301338, July 2000.

Linear consistency testing.
 Authors: Yonatan Aumann, Johan Håstad, Michael O. Rabin,
and Madhu Sudan.

Randomization, Approximation and Combinatorial Optimization,
D. Hochbaum et al. (Eds), Proceedings of the 3rd International
Workshop on Randomization and Approximation Techniques in Computer
Science, Berkeley, California, 811 August 1999.
Lecture Notes in Computer Science, vol. 1671, Springer, Berlin,
pages 109120, 1999
(conf.pdf).
 Journal of Computer and System Sciences,
62(4):589607, July 2001.

Hardness of approximating the minimum
distance of a linear code.
 Authors: Ilya Dumer, Daniele Micciancio, and Madhu Sudan.
 Proceedings of the 40th Annual Symposium on Foundations
of Computer Science,
pages 475484, New York City, New York, 1719 October, 1999
(conf.pdf).
 IEEE Transactions on Information Theory,
49(1):2237, January 2003.

List decoding: Algorithms and applications.
 Authors: Madhu Sudan.
 SIGACT News,
Volume 31, Number 1, pp. 1627, March 2000 (Whole Number 114).

Random walks with "Back Buttons".
 Authors: Ronald Fagin, Anna Karlin, Jon Kleinberg,
Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld,
Madhu Sudan, and Andrew Tomkins.
 Proceedings of the ThirtySecond Annual ACM Symposium
on Theory of Computing,
pages 484493, Portland, Oregon, 2123 May 2000
(conf.pdf).
 Annals of Applied Probability,
11(3): 810862, 2001.

List decoding algorithms for certain concatenated codes.
 Authors: Venkatesan Guruswami and Madhu Sudan.
 Proceedings of the ThirtySecond Annual ACM Symposium on
Theory of Computing,
pages 181190, Portland, Oregon, 2123 May 2000
(conf.pdf).
 Main link is to the unpublished fuller version.

List decoding: Algorithms and applications.
 Authors: Madhu Sudan.
 Proceedings of the International Conference IFIP TCS
2000, Sendai, Japan, 1719 August, 2000. In Lecture Notes in
Computer Science, Volume 1872, J. van Leeuwen, O. Watanabe,
M. Hagiya, P.D. Mosses, T. Ito (Eds.), Springer,
pages 2541, August 2000.

On representations of algebraicgeometric codes.
 Authors: Venkatesan Guruswami and Madhu Sudan.
 Conference version was titled
On representations of algebraicgeometric
codes for list decoding.
 Proceedings of the 8th Annual European Symposium on
Algorithms,
pages 244255, Saarbrucken, Germany, September 58, 2000
(conf.pdf).
 IEEE Transactions on Information Theory,
(Corresp.), 47(4):16101613, May 2001.

Combinatorial bounds for list decoding.
 Authors: Venkatesan Guruswami, Johan Håstad, Madhu Sudan,
and David Zuckerman.
 Proceedings of the 38th Annual Allerton
Conference on Communication, Control and Computing,
pages 603612, Monticello, Illinois,
46 October, 2000
(conf.pdf).
 IEEE Transactions on Information Theory,
48(5):10211035, May 2002.

Hardness of approximate hypergraph coloring.
 Authors: Venkatesan Guruswami, Johan Håstad, and Madhu Sudan.
 Proceedings of the 41st Annual Symposium on Foundations
of Computer Science,
pages 149158, Redondo Beach, California, 1214 November, 2000.
(conf.pdf).
 SIAM Journal on Computing, 31(6): 16631686, 2002.

"Softdecision" decoding of Chinese remainder codes.
 Authors: Venkatesan Guruswami, Amit Sahai, and Madhu Sudan.
 Proceedings of the 41st Annual Symposium on Foundations
of Computer Science,
pages 159168, Redondo Beach, California, 1214 November, 2000.

Small PCPs with low query complexity.
 Authors: Prahladh Harsha and Madhu Sudan.
 STACS 2001, Afonso Ferreira and Horst Reichel (Eds.)
Proceedings of the Eighteenth International
Symposium on Theoretical Aspects of Computer Science,
Dresden, Germany, 1517 February, 2001. Lecture Notes in Computer
Science, vol. 2010, Springer, Berlin, pages 327338, 2001
(conf.pdf).
 Computational Complexity,
9(34):157201, 2000.

Extensions to the Johnson bound.
 Authors: Venkatesan Guruswami and Madhu Sudan.
 Manuscript, February 2001.

The approximability of constraint satisfaction problems.
 Authors: Sanjeev Khanna, Madhu Sudan, Luca Trevisan,
and David P. Williamson.
 Journal version of 31 and
33 above.
 SIAM Journal on Computing,
30(6):18631920, March 2001.

Coding theory: Tutorial & Survey.
 Author: Madhu Sudan.
 Proceedings of the 42nd Annual Symposium on Foundations
of Computer Science,
pages 3653, Las Vegas, Nevada, 1417 October, 2001.

Ideal errorcorrecting codes: Unifying algebraic and
numbertheoretic algorithms.
 Author: Madhu Sudan.
 Proceedings of AAECC14, The Fourteenth Symposium
on Applied Algebra, Algebraic Algorithms and ErrorCorrecting
Codes Melbourne, Australia, 2630 November 2001.
In
Lecture Notes in Computer Science, Volume 2227,
Serdar Boztas and Igor E. Shparlinksi (Eds.),
Springer,
pages 3645, November 2001.

Complexity classifications of Boolean constraint satisfaction
problems.
 Authors: Nadia Creignou, Sanjeev Khanna, and Madhu Sudan.
 SIGACT News,
Volume 32, Number 4, Whole Number 121,
Complexity Theory Column 34,
pages 2433, November 2001.

Guessing secrets efficiently via listdecoding.
 Authors: Noga Alon, Venkatesan Guruswami, Tali Kaufman, and
Madhu Sudan.
 Proceedings of the Thirteenth Annual ACMSIAM Symposium
on Discrete Algorithms, pages 254262,
San Francisco, California, 68 January 2002.
(conf.pdf).
 ACM Transactions on Algorithms, 3(4):Article 42
(16 pages), 2007.

Harmonic broadcasting is bandwidthoptimal assuming constant bit rate.
 Authors: Lars Engebretsen and Madhu Sudan.
 Proceedings of the Thirteenth Annual ACMSIAM Symposium
on Discrete Algorithms, pages 431432, San Francisco, California,
68 January 2002.
(conf.pdf).
 Networks,
47(3):172177, February 2006.

Reflections on ``Improved Decoding of ReedSolomon
and AlgebraicGeometric Codes''.
 Authors: Venkatesan Guruswami and Madhu Sudan.
 IEEE Information Theory Society Newsletter,
Volume 52, Number 1, ISSN 10592362, pages 612, March 2002.

Decoding concatenated codes using soft information.
 Authors: Venkatesan Guruswami and Madhu Sudan.
 Proceedings of the Seventeenth IEEE Conference on Computational
Complexity, pages 148157, Montreal, Canada,
2124 May, 2002.

A fuzzy vault scheme.
 Authors: Ari Juels and Madhu Sudan.
 Proceedings of the 2002 IEEE International Symposium on
Information Theory, A. Lapidoth and E. Teletar, Eds.,
page 408, Lausanne, Switzerland,
30 June  5 July, 2002.
(conf.pdf).
 Designs, Codes and Cryptography,
38(2):237257, February 2006.

Locally testable codes and PCPs of almostlinear length.
 Authors: Oded Goldreich and Madhu Sudan.
 Proceedings of the 43rd Annual IEEE Symposium on
Foundations of Computer Science, pages 1322,
Vancouver, Canada,
1619 November, 2002.
(conf.pdf).
 Journal of the ACM, 53(4):558655, 2006.

Reconstructing curves in three (and higher) dimensional spaces from
noisy data.
 Authors: Don Coppersmith and Madhu Sudan.
 Proceedings of the 35th Annual ACM Symposium on
Theory of Computing, pages 136142,
San Diego, California,
911 June, 2003.

Derandomizing low degree tests via epsilonbiased spaces
noisy data.
 Authors: Eli BenSasson, Madhu Sudan, Salil
Vadhan, and Avi Wigderson
 Proceedings of the 35th Annual ACM Symposium on
Theory of Computing, pages 612621,
San Diego, California,
911 June, 2003.

Bounds on 2query codeword testing.
 Authors: Eli BenSasson, Oded Goldreich, and Madhu Sudan.
 In
Sanjeev Arora, Klaus Jansen, José D. P. Rolim, Amit Sahai
(Eds.): Approximation, Randomization, and Combinatorial
Optimization: Algorithms and Techniques, 6th International
Workshop on Approximation Algorithms for Combinatorial
Optimization Problems, APPROX 2003 and 7th International
Workshop on Randomization and Approximation Techniques in
Computer Science, RANDOM 2003,
Lecture Notes in Computer Science 2764
Springer 2003, ISBN 3540407707, pages 216227.
Princeton, NY, USA,
August 2426, 2003.

Quick and Dirty Refereeing?
 Authors: Madhu Sudan.
 Science, 301(5637):11911192, 29 August 2003.
 Official version is no longer available. Here is a personal
version.

Robust PCPs of proximity, shorter PCPs, and applications
to coding
 Authors: Eli BenSasson, Oded Goldreich, Prahladh Harsha,
Madhu Sudan, and Salil Vadhan.

Proceedings of the Thirty Sixth Annual ACM Symposium
on Theory of Computing , pages 110,
Chicago, Illinois, June 1315, 2004.
(conf.pdf).
 SIAM Journal on Computing,
36(4):889974, 2006.

Robust locally testable codes and products of codes
 Authors: Eli BenSasson and Madhu Sudan.
 In Klaus Jansen, Sanjeev Khanna, José D. P. Rolim,
and Dana Ron (Eds.):
Approximation, Randomization, and Combinatorial
Optimization: Algorithms and Techniques, 7th International
Workshop on Approximation Algorithms for Combinatorial
Optimization Problems, APPROX 2004 and 7th International
Workshop on Randomization and Approximation Techniques in
Computer Science, RANDOM 2004,
pages 286297,
Radcliffe Institute, Cambridge, MA, USA, August 2224, 2004.
conf.pdf).
 Random Structures and Algorithms,
28(4):387402, 2006.

From logarithmic advice to singlebit advice.
 Authors: Oded Goldreich, Madhu Sudan, and Luca Trevisan.
 Electronic Colloquium on Computational Complexity,
Technical Report TR04093, November 2004.
 In Studies in Complexity and Cryptography,
Oded Goldreich (Ed.), Lecture Notes in Computer Science,
volume 6650, pages 109113, Springer, 2011.

Probabilistically Checkable Proofs.
 Lecture Notes, scribed by Venkatesan Guruswami.
 Book chapter in Computational Complexity Theory,
Steven Rudich and Avi Wigderson (Eds.), pages 349389,
IAS/Park City Mathematics Series, volume 10,
American Mathematical Society, 2004.

Optimal errorcorrection for computationally
bounded noise.
 Authors: Silvio Micali, Chris Peikert, Madhu Sudan,
and David A. Wilson.
 Preliminary version titled Optimal errorcorrection
against computationally bounded noise appeared in
Second Annual Theory of Cryptography Conference,
pages 116, MIT, Cambridge, Massachusetts, February 1012, 2005.
(conf.pdf).
 IEEE Transactions on Information Theory,
56(11):56735680, November 2010.

Short PCPs with Polylog Query Complexity.
 Authors: Eli BenSasson and Madhu Sudan.
 Preliminary version titled Simple PCPs with
polylogarithmic rate and query complexity appeared in
Proceedings of the Thirty Seventh Annual ACM Symposium
on Theory of Computing, pages 266275,
Baltimore, Maryland, May 2224, 2005.
(conf.pdf).
 SIAM Journal on Computing, 38(2):551607, 2008.

Derandomization of auctions.
 Authors: Gagan Aggarwal, Amos Fiat, Andrew Goldberg,
Jason Hartline, Nicole Immorlica, and Madhu Sudan.
 Proceedings of the Thirty Seventh Annual ACM Symposium
on Theory of Computing, pages 619625,
Baltimore, Maryland, May 2224, 2005.
(conf.pdf).
 Games and Economic Behavior, 72(1):111, May 2011.

Short PCPs verifiable in polylogarithmic time.
 Authors:
Eli BenSasson, Oded Goldriech, Prahladh Harsha, Madhu Sudan,
and Salil Vadhan.

Proceedings of the Twelfth Annual IEEE
Conference on Computational Complexity
,
pages 120134,
San Jose, California, June 1215, 2005.
(conf.pdf).
 Unpublished full version.

Distributed Computing with Imperfect Randomness.
 Authors: Shafi Goldwasser, Madhu Sudan, and
Vinod Vaikuntanathan.
 Proceedings of DISC 2005,
Cracow, Poland, September 2629, 2005,
Springer Lecture Notes in Computer Science, volume 3724,
pages 288302, 2005.
(conf.pdf).
 Unpublished full version.

Local Decoding and Testing for Homomorphisms.
 Authors: Elena Grigorescu, Swastik Kopparty, and Madhu Sudan.

Proceedings of RANDOM and APPROX,
August 2830 2006,
Barcelona, Spain,
Springer Lecture Notes in
Computer Science, vol. 4110, pages 375385, 2006.

Robust local testability of tensor products of LDPC codes.
 Authors: Irit Dinur, Madhu Sudan, and Avi Wigderson.

Proceedings of RANDOM and APPROX,
August 2830 2006, Barcelona, Spain, Springer Lecture Notes in
Computer Science, vol. 4110, pages 304315, 2006.

On Dinur's Proof of the PCP Theorem.

Amplifying Collision
Resistance: A ComplexityTheoretic Treatment.
 Authors: Ran Canetti, Ronald L. Rivest, Madhu Sudan,
Luca Trevisan, Salil P. Vadhan, and Hoeteck Wee.
 Proceedings of the 27th Annual International
Cryptology Conference (CRYPTO 2007),
Santa Barbara, CA, USA, August 1923, 2007,
pages 264283,
Alfred Menezes (Ed.), Lecture Notes in Computer Science,
Vol. 4622, Springer, 2007.

Sparse Random Linear
Codes are Locally Decodable and Testable.
 Authors: Tali Kaufman and Madhu Sudan.

Electronic Colloquium on Computational Complexity,
Technical Report No. TR 07060, July 12, 2007.

Proceedings of the 48th Annual IEEE Symposium on
Foundations of Computer Science (FOCS 2007),
pages 590600,
Providence, RI, USA,
October 2023, 2007.
(conf.pdf).

Universal Semantic Communication I.
 Authors: Brendan Juba and Madhu Sudan.
 Preliminary version posted at
http://people.csail.mit.edu/madhu/papers/2007/jubav0.pdf
on February 12, 2007.

Electronic Colloquium on Computational Complexity,
Technical Report No. TR 07084, September 4, 2007.

Proceedings of the 40th Annual ACM Symposium on Theory of
Computing, pages 123132, Victoria (BC), Canada, May 1720, 2008.
(conf.pdf).

Algebraic Property
Testing: The Role of Invariance.
 Authors: Tali Kaufman and Madhu Sudan.

Electronic Colloquium on Computational Complexity,
Technical Report No. TR 07111, November 2, 2007.

Proceedings of the 40th Annual ACM Symposium on Theory of
Computing, pages 403412, Victoria (BC), Canada, May 1720, 2008.
(conf.pdf).

Decodability of Group Homomorphisms beyond the Johnson Bound.
 Authors: Irit Dinur, Elena Grigorescu, Swastik Kopparty, and Madhu
Sudan.

Electronic Colloquium on Computational Complexity,
Technical Report No. TR 08020, March 7, 2008.

Proceedings of the 40th Annual ACM Symposium on Theory of
Computing, pages 275284, Victoria (BC), Canada,
May 1720, 2008.
(conf.pdf).

2Transitivity is
Insufficient for Local Testability.
 Authors: Elena Grigorescu, Tali Kaufman, and Madhu Sudan.

Electronic Colloquium on Computational Complexity,
Technical Report No. TR 08033, March 21, 2008.

Proceedings of the 23rd IEEE Conference on Computational
Complexity, pages 259267, University of Maryland,
College Park, Maryland, USA, June 2326th, 2008.
(conf.pdf).

Computational
Complexity 22(1): 137158, March 2013.
(full.pdf).

Reliable Transmission of Information.
 Author: Madhu Sudan.
 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 BarrowGreen and Imre Leader, Princeton University Press, 2008.

An improved lower bound
on the size of Kakeya sets over finite fields,
 Authors: Shubhangi Saraf and Madhu Sudan.

arXiv:0808.2499v2 [math.CO], 22 August, 2008.
 Analysis & PDE, 1(3): 375379, 2008.

Universal Semantic Communication II,
 Authors: Brendan Juba and Madhu Sudan.
 This early version is effectively replaced by
96 below.
 Electronic Colloquium on Computational Complexity,
Technical Report TR08095, October 2008. Revised February 13, 2009.

Testing LinearInvariant
NonLinear Properties,
 Authors: Arnab Bhattacharyya, Victor Chen, Madhu Sudan, and Ning Xie.

Proceedings of the 26th International Symposium on
Theoretical Aspects of Computer Science (STACS 2009),
pages 135146, Freiburg, Germany, February 2628, 2009.
(conf.pdf).
 Electronic Colloquium on Computational Complexity,
Technical Report TR08088, 23 September 2008. Revised April 18, 2009.

Probabilistically Checkable
Proofs,
 Authors: Madhu Sudan.

Communications of the ACM,
52(3):7684, March 2009.

Locally Testable Codes Require Redundant Testers.
 Authors: Eli BenSasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan,
and Michael Viderman.
 Proceedings of the 24th Annual IEEE Conference on Computational
Complexity, pages 5261, Paris, France, July 1518, 2009.
(conf.pdf).
 SIAM Journal on Computing, 39(7): 32303247, July 2010.

Succinct Representation of Codes with Applications to Testing.
 Authors: Elena Grigorescu, Tali Kaufman, and Madhu Sudan.
 Electronic Colloquium on Computational Complexity,
Technical Report TR 09043, May 18, 2009.
 Proceedings of RANDOMAPPROX 2009,
Lecture Notes in Computer Science, volume 5687, Springer 2009,
pages 534547, Berkeley, CA, USA, August 2123, 2009.
(conf.pdf).
 SIAM Journal of Discrete Mathematics,
26(4): 16181634, 2012.
(journ.pdf).

Extensions to the Method
of Multiplicities, with applications to Kakeya Sets
and Mergers.
 Authors: Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, and
Madhu Sudan.
 Electronic Colloquium on Computational Complexity,
Technical Report TR 09004, January 15, 2009. Revised May 19, 2009.
(eccc.pdf).
 Proceedings of the 50th Annual IEEE Symposium on
Foundations of Computer Science, pages 181190,
Atlanta, Georgia, October 2427, 2009.
(conf.pdf).

SIAM Journal on Computing, Special section on FOCS 2009,
42(6): 23052328, December 2013.
(journ.pdf).

A Theory of GoalOriented
Communication.
 Authors: Oded Goldreich, Brendan Juba, and
Madhu Sudan.
 Electronic Colloquium on Computational Complexity,
Technical Report TR 09075, September 17, 2009.
 Journal of the ACM, 59(2): Article 8 (65 pages), April 2012.
(journ.pdf).

Optimal testing of ReedMuller codes.
 Authors: Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck,
Madhu Sudan, and David Zuckerman.
 Electronic Colloquium on Computational Complexity,
Technical Report TR 09086, October 2, 2009.
 Proceedings of the 51st Annual IEEE Symposium on
Foundations of Computer Science, pages 488497,
Las Vegas, Nevada, October 2326, 2010.
(conf.pdf).

Kakeyatype sets in finite vector spaces.
 Authors: Swastik Kopparty, Vsevolod F. Lev, Shubhangi
Saraf, and Madhu Sudan.

arXiv:1003.3736v1 [math.NT], March 19, 2010.

Invariance in Property Testing.
 Authors: Madhu Sudan.
 Electronic Colloquium on Computational Complexity,
Technical Report TR 10051, March 26, 2010.
 In Property Testing: Current Research and Surveys,
Oded Goldreich (Ed.), Lecture Notes in Computer Science, volume
6390, pages 211227, Springer, July 2010.

Tight Asymptotic Bounds for the Deletion Channel with Small
Deletion Probabilities.
 Authors: Adam Kalai, Michael Mitzenmacher, and Madhu Sudan.
 Proceedings of the 2010 IEEE International Symposium on Information Theory, pages
9971001, Austin, Texas, USA, June 1318, 2010.

The P vs. NP Problem.
 Authors: Madhu Sudan.
 An Italian translation appears titled Il problema P = NP
in La matematica, vol. 4, Pensare il mondo, edited by
Claudio Bartocci and Piergiorgio Odifreddi, pages 161179,
Einaudi, Torino, 2010.

Limits on the rate of locally testable affineinvariant codes
.
 Authors: Eli BenSasson and Madhu Sudan.
 Electronic Colloquium on Computational Complexity,
Technical Report TR 10108, July 10, 2010.
 Proceedings of RANDOMAPPROX 2011,
Lecture Notes in Computer Science, volume 6845, Springer 2011,
pages 412423, Princeton, NJ, USA, August 1719, 2011.
(conf.pdf).

Testing LinearInvariant NonLinear Properties: A short report.
 Authors: Arnab Bhattacharyya, Victor Chen, Madhu Sudan, and Ning Xie.
 Short survey based on the paper 91 above.
 Electronic Colloquium on Computational Complexity,
Technical Report TR 10116, July 20, 2010.
 In Property Testing: Current Research and Surveys,
Oded Goldreich (Ed.), Lecture Notes in Computer Science, volume
6390, pages 260268, Springer, July 2010.

Efficient Semantic Communication via Compatible Beliefs.
 Authors: Brendan Juba and Madhu Sudan.
 Electronic Colloquium on Computational Complexity,
Technical Report TR 10155, October 14, 2010.
 Proceedings of Innovations in Computer Science,
pages 2231, Tsinghua University, Beijing, China, January 79 2011.
(conf.pdf).

Property Testing via SetTheoretic Operations.
 Authors: Victor Chen, Madhu Sudan, and Ning Xie.
 Electronic Colloquium on Computational Complexity,
Technical Report TR 10156, October 24, 2010.

arXiv:1010.4925v1 [cs.DS], October 24, 2010.
 Proceedings of Innovations in Computer Science,
pages 211222, Tsinghua University, Beijing, China, January 79 2011.
(conf.pdf).

Symmetric LDPC codes are not necessarily locally testable.
 Authors: Eli BenSasson, Ghid Maatouk, Amir Shpilka, and Madhu Sudan.
 Electronic Colloquium on Computational Complexity,
Technical Report TR 10199, December 14, 2010.
 Proceedings of the 26th Annual IEEE Conference on
Computational Complexity (CCC 2011),
pages 5565, San Jose, California, USA, June 810, 2011.
(conf.pdf).

Compression without a common prior: An informationtheoretic
justification for ambiguity in language.
 Authors: Brendan Juba, Adam Tauman Kalai, Sanjeev Khanna,
and Madhu Sudan.
 Proceedings of Innovations in Computer Science,
pages 7986, Tsinghua University, Beijing, China, January 79 2011.

Testing linear properties: Some general themes.
 Authors: Madhu Sudan.
 Electronic Colloquium on Computational Complexity,
Technical Report TR 11005, January 20, 2011.
 SIGACT News,
Complexity Theory Column,
42(1):5980, March 2011.

Patterns hidden from simple algorithms.
 Authors: Madhu Sudan.
 "Technical Perspective" on Mark Braverman's
article Polylogarithmic independence fools
boundeddepth Boolean
circuits, in CACM, 54(4): 108115 (2011).
 Communications of the ACM, 54(4):107, April 2011.

Optimal testing of multivariate polynomials over small prime fields.
 Authors: Elad Haramaty, Amir Shpilka, and Madhu Sudan.
 Electronic Colloquium on Computational Complexity,
Technical Report TR 11059, April 15, 2011.
(eccc.pdf).
 Proceedings of the 52nd Annual IEEE Symposium on
Foundations of Computer Science, pages 629637,
Palm Springs, California, October 2325, 2011
(conf.pdf).
 SIAM Journal on Computing,
42(2): 536562, April 2013.
(journ.pdf).

On Sums of Locally Testable Affine Invariant Properties.
 Authors: Eli BenSasson, Elena Grigorescu, Ghid Maatouk,
Amir Shpilka, and Madhu Sudan.
 Electronic Colloquium on Computational Complexity,
Technical Report TR 11079, May 9, 2011.
 Proceedings of RANDOMAPPROX 2011,
Lecture Notes in Computer Science, volume 6845, Springer 2011,
pages 400411, Princeton, NJ, USA, August 1719, 2011.
(conf.pdf).

Delays and the Capacity of Continuoustime Channels.
 Authors: Sanjeev Khanna and Madhu Sudan.

arXiv:1105.3425v1 [cs.IT], 17 May, 2011.
 Proceedings of the 52nd Annual IEEE Symposium on
Foundations of Computer Science, pages 758767,
Palm Springs, California, October 2325, 2011
(conf.pdf).

Physical Limits of Communication (Invited Talk).
 Authors: Madhu Sudan.
 Gives brief description of the work
112 above.
 Proceedings of the IARCS Annual Conference on Foundations
of Software Technology and Theoretical Computer Science, FSTTCS 2011,
December 1214, 2011, Mumbai, India, pages 45, LIPIcs vol.
13, 2011.

A new upper bound on the query complexity for testing generalized ReedMuller codes.
 Authors: Noga RonZewi and Madhu Sudan.
 Electronic Colloquium on Computational Complexity,
Technical Report TR 12046, April 24, 2012.

Proceedings of RANDOMAPPROX 2012,
pages 639650, Cambridge, MA, USA, August 1517, 2012.
(conf.pdf).
 Theory of Computing, 9: 783807, 2013.
(journ.pdf).

Some closure features of locally testable affineinvariant properties.
 Authors: Alan Guo and Madhu Sudan.
 Electronic Colloquium on Computational Complexity,
Technical Report TR 12048, April 24, 2012.

Communication amid uncertainty.
 Authors: Madhu Sudan.
 Gives brief introduction to the works
84,
96,
104, and
107 above.
 Proceedings of the IEEE Information Theory Workshop (ITW
2012), pages 158161, Lausanne, Switzerland, September 37,
2012.

Sparse affineinvariant linear codes are locally testable.
 Authors: Eli BenSasson, Noga RonZewi and Madhu Sudan.
 Electronic Colloquium on Computational Complexity,
Technical Report TR 12049, April 27, 2012.
 Proceedings of the 53rd Annual IEEE Symposium on
Foundations of Computer Science, pages 561570,
New Brunswick, New Jersey, October 2023, 2012
(conf.pdf).

New affineinvariant codes from lifts.
 Authors: Alan Guo, Swastik Kopparty and Madhu Sudan.

Electronic Colloquium on Computational Complexity,
Technical Report TR 12149, November 8, 2012.
(Previous version appeared as ECCC
Technical Report TR 12106, August 27, 2012.)
 Proceedings of Innovations in Theoretical Computer
Science, {ITCS} '13, Berkeley,
CA, USA, pages 529540, January 912, 2013.
(conf.pdf).

Queueing with Future Information.
 Authors: Joel Spencer, Madhu Sudan and Kuang Xu.

arXiv:1211.0618v1 [math.PR], 3 November 2012.
 SIGMETRICS Performance Evaluation Review,
41(3):4042, 2013.
(conf.pdf).
 Annals of Applied Probability,
24(5): 20912142, 2014.
(journ.pdf).

Deterministic compression with uncertain priors.
 Authors: Elad Haramaty and Madhu Sudan.

Electronic Colloquium on Computational Complexity,
Technical Report TR 12166, November 26, 2012.
 Proceedings of Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 1214,
2014, pages 377386.
(conf.pdf).

Absolutely Sound Testing of Lifted Codes.
 Authors: Elad Haramaty, Noga RonZewi and Madhu Sudan.

Electronic Colloquium on Computational Complexity,
Technical Report TR 13030, February 20, 2013.
 Proceedings of
APPROX/RANDOM'13,
16th International Workshop, {APPROX} 2013, and 17th
International Workshop, {RANDOM} 2013,
Berkeley, CA, USA, August 2123,
2013.
(conf.pdf).

Limits of local algorithms over sparse random graphs.
 Authors: David Gamarnik and Madhu Sudan.

Electronic Colloquium on Computational Complexity,
Technical Report TR 13055, February 20, 2013.
 Proceedings of Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 1214,
2014, pages 369376.
(conf.pdf).

Optimal Error Rates for Interactive Coding I: Adaptivity and
Other Settings..
 Authors: Mohsen Ghaffari, Bernhard Haeupler, and Madhu Sudan.

arXiv:1312.1764 [cs.DS], 6 December 2013.

Proceedings of the 46th Annual ACM Symposium on Theory of
Computing, pages 794803, New York, NY, USA,
May 31June 03, 2014.
(conf.pdf).

Approximating matching size from random streams.
 Authors: Michael Kapralov, Sanjeev Khanna, and Madhu Sudan.
 Proceedings of the TwentyFifth Annual {ACMSIAM} Symposium
on Discrete Algorithms, {SODA} 2014, Portland, Oregon, USA,
January 57, 2014, pages 734751.
(conf.pdf).

Performance of the Survey Propagationguided decimation algorithm
for the random NAEKSAT problem.
 Authors: David Gamarnik and Madhu Sudan.

arXiv:1402.0052 [math.PR], February 1, 2014.

List decoding group homomorphisms between supersolvable
groups.
 Authors: Alan Guo and Madhu Sudan.

arXiv:1404.4273 [cs.IT], April 16, 2014.

Proceedings of APPROX/RANDOM'14,
http://www.dagstuhl.de/dagpub/9783939897743,
17th Int’l Workshop
on Approximation Algorithms for Combinatorial Optimization
Problems (APPROX’14) / 18th Int’l Workshop on Randomization and
Computation (RANDOM’14),
September 46 2014,
Barcelona, Spain, pages 737747, LIPICS vol. 28.
(conf.pdf).

Limitations on Testable AffineInvariant Codes in the HighRate
Regime.
 Authors: Venkatesan Guruswami, Madhu Sudan, Ameya Velingker,
and Carol Wang.
 Electronic Colloquium on Computational Complexity,
Technical Report TR 14067, May 4, 2014.

Streaming Lower Bounds for Approximating MAXCUT .
 Authors: Michael Kapralov, Sanjeev Khanna, and Madhu Sudan.

arXiv:1409.2138 [CS.DS], September 7, 2014.

Communication with Imperfectly Shared Randomness.
 Authors: Clément Canonne, Venkatesan Guruswami, Raghu Meka, and Madhu Sudan.

arXiv:1411.3603 [CS.CC], November 13, 2014.

Robust testing of lifted codes with applications to lowdegree testing.
 Authors: Alan Guo, Elad Haramaty, and Madhu Sudan.

Communication Complexity of PermutationInvariant Functions.
 Authors: Badih Ghazi, Pritish Kamath, and Madhu Sudan.

Communication with Contextual Uncertainty.
 Authors: Badih Ghazi, Ilan Komargodski, Pravesh Kothari, and Madhu
Sudan.