Harvard University homepage
HARVARD.EDU

Madhu Sudan: Papers

Papers are ordered reverse chronologically by first date of publication. Here are shorts cuts to papers from 2020, 2010, 2000, 1990.

2024

  1. Streaming Algorithms via Local Algorithms for Maximum Directed Cut. With Raghuvansh R. Saxena, Noah G. Singer, and Santhoshini Velusamy. (arxiv)
  2. Finding the root in random nearest neighbor trees. With Anna Brandenberger, Cassandra Marcussen, and Elchanan Mossel. (arxiv)
  3. Improved PIR Schemes using Matching Vectors and Derivatives. With Fatemeh Ghasemi and Swastik Kopparty. (arxiv)
  4. Low Degree Local Correction Over the Boolean Cube. With Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, and Srikanth Srinivasan. (arxiv)
  5. Testing Tensor Products of Algebraic Codes. With Sumegha Garg and Gabriel Wu. (arxiv)
  6. Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers. With Sanjeev Khanna and Aaron (Louie) Putterman. (arxiv, FOCS 2024).
  7. Efficient Algorithms and New Characterizations for CSP Sparsification. With Sanjeev Khanna and Aaron (Louie) Putterman. (arxiv).
  8. Sketching Approximability of All Finite CSPs. With Chi-Ning Chou, Alexander Golovnev, and Santhoshini Velusamy. (arxiv, JACM 2024).
  9. Local Correction of Linear Functions over the Boolean Cube. With Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, and Srikanth Srinivasan. (arxiv, STOC 2024). 
  10. Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs. With Sanjeev Khanna and Aaron (Louie) Putterman. (arxiv, ICALP 2024). 
  11. Spectral non-concentration near the top for unimodular random graphs. With Mikolaj Fraczyk, Ben Hayes, and Yufei Zhao. (arxiv).

2023

  1. An Improved Line-Point Low-Degree Test. With Prahladh Harsha, Mrinal Kumar, and Ramprasad Saptharishi, Madhu Sudan. (arxiv, FOCS 2024). 
  2. Code Sparsification and its Applications. With Sanjeev Khanna and Aaron (Louie) Putterman. (arxiv, SODA 2024). 
  3. Errors are Robustly Tamed in Cumulative Knowledge Processes. With Anna M. Brandenberger, Cassandra Marcussen, and Elchanan Mossel. (arxiv, COLT 2024).
  4. On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction. With Kuan Cheng, Elena Grigorescu, Xin Li,  and Minshen Zhu. (arxiv, ISIT 2024). 
  5. Low-Degree Testing over Grids. With Prashanth Amireddy and Srikanth Srinivasan. (arxiv, RANDOM 2023). 

2022

  1. Is this correct? Let’s check! With Omri Ben-Eliezer, Dan Mikulincer, and Elchanan Mossel. (arxiv, ITCS 2023). 
  2. Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots. With Raghuvansh R. Saxena, Noah G. Singer,  and Santhoshini Velusamy. (arxiv, FOCS 2023). 
  3. Streaming complexity of CSPs with randomly ordered constraints. With Raghuvansh R. Saxena, Noah Singer,  and Santhoshini Velusamy. (arxiv, SODA 2023). 
  4. Streaming and Sketching Complexity of CSPs: A survey. Madhu Sudan. (arxiv, ICALP 2022). 
  5. Sketching Approximability of (Weak) Monarchy Predicate. With Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, and Santhoshini Velusamy. (arxiv, APPROX 2022).
  6. General Strong Polarization. Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra and Madhu Sudan (merger of two conference papers). (arxiv, JACM).

2021

  1. Streaming Approximation Resistance of Every Ordering CSP. Noah Singer, Madhu Sudan, Santhoshini Velusamy. (arxiv, Approx 2021, Computational Complexity).
  2. Ideal-Theoretic Explanation of Capacity-Achieving Decoding. Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan. (arxiv, Random 2021). 
  3. Approximability of all finite CSPs with linear sketches. Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy: (arxiv, FOCS 2021). 
  4. Approximability of all Boolean CSPs with linear sketches. Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy. (Theorems in this paper are subsumed by the one above but some of the proofs are simpler in this paper.) (arxiv). 
  5. Point-hyperplane incidence geometry and the log-rank conjecture. Noah Singer, Madhu Sudan. (arxiv, TOCT 2022).
  6. Linear Space Streaming Lower Bounds for Approximating CSPs. Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy. (arxiv, STOC 2022).
  7. Information Spread with Error Correction. Omri Ben-Eliezer, Elchanan Mossel, Madhu Sudan. (arxiv). 
  8. Elementary analysis of isolated zeroes of a polynomial system. Mitali Bafna, Madhu Sudan, Santhoshini Velusamy, David Xiang. (arxiv)

2020

  1. Decoding multivariate multiplicity codes on product sets. Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan. (arxiv, STOC 2021, IEEE Trans. IT). 
  2. Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance. Elena Grigorescu, Madhu Sudan, Minshen Zhu. (arxiv, ISIT 2021, IEEE IT 2022). 

2019

  1. Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time. Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, Madhu Sudan. (arxiv, FOCS2019). 
  2. Communication for Generating Correlation: A Survey. Madhu Sudan, Himanshu Tyagi, Shun Watanabe. (arxiv, IEEE IT 2020).
  3. Round Complexity of Common Randomness Generation: The Amortized Setting. Noah Golowich, Madhu Sudan. (arxiv, SODA 2020).
  4. A Self-contained Analysis of the Lempel-Ziv Compression Algorithm. Madhu Sudan, David Xiang. (arxiv).

2018

  1. Polar Codes with Exponentially Small Error at Finite Block Length. Jaroslaw Blasiok, Venkatesan Guruswami, Madhu Sudan. (arxiv, random 2018, full JACM 2022 version (merged with paper below.)). 
  2. General strong polarization. Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan. (arxiv, STOC 2018, full JACM 2022 version (merged with paper above.)). 
  3. Synchronization Strings: List Decoding for Insertions and Deletions. Bernhard Haeupler, Amirbehshad Shahrasbi, Madhu Sudan.  (arxiv, ICALP 2018).
  4. Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation. Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan. (arxiv, SODA 2019). 
  5. Algorithmic Polarization for Hidden Markov Models. Venkatesan Guruswami, Preetum Nakkiran, Madhu Sudan. (arxiv, ITCS 2019). 

2017

  1. Local decoding and testing of polynomials over grids. Mitali Bafna, Srikanth Srinivasan, Madhu Sudan. (arxiv, ITCS 2018, RSA 2020). 
  2. The Power of Shared Randomness in Uncertain Communication. Badih Ghazi, Madhu Sudan. (arxiv, ICALP 2017).
  3. Compression in a Distributed Setting. Badih Ghazi, Elad Haramaty, Pritish Kamath, Madhu Sudan. (ITCS 2017).
  4. (1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space. Michael Kapralov, Sanjeev Khanna, Madhu Sudan, Ameya Velingker. (SODA 2017).

2016

  1. Decidability of Non-interactive Simulation of Joint Distributions. Badih Ghazi, Pritish Kamath, Madhu Sudan. (arxiv, FOCS 2016).
  2. Optimality of Correlated Sampling Strategies. Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, Madhu Sudan. (arxiv, TOC 2020). 

2015

  1. Communication with Contextual Uncertainty. Badih Ghazi, Ilan Komargodski, Pravesh K. Kothari, Madhu Sudan. (arxiv (early version), SODA 2016, Comp. Compl. 2018.)
  2. Communication Complexity of Permutation-Invariant Functions. Badih Ghazi, Pritish Kamath, Madhu Sudan. (ECCC, SODA 2016.)
  3. Robust Testing of Lifted Codes with Applications to Low-Degree Testing. Alan Guo, Elad Haramaty, Madhu Sudan. (ECCC, FOCS 2015.)

2014

  1. Communication With Imperfectly Shared Randomness. Clément L. Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan. (arxiv, ITCS 2015, IEEE IT 2017.) 
  2. Streaming Lower Bounds for Approximating MAX-CUT. Michael Kapralov, Sanjeev Khanna, Madhu Sudan. (arxiv, SODA 2015.)
  3. Limitations on Testable Affine-Invariant Codes in the High-Rate Regime. Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang. (ECCC, SODA 2015.)
  4. List decoding group homomorphisms between supersolvable groups. Alan Guo, Madhu Sudan. (arxiv, Random 2014. Erratum + Amendment (with Tim Black and Angela Wu, unpublished. See Section 1.6 for description of error and fix.)
  5. Performance of Sequential Local Algorithms for the Random NAE-K-SAT Problem. David Gamarnik, Madhu Sudan. (arxiv (early version), SICOMP 2017.) 
  6. Approximating matching size from random streams. Michael Kapralov, Sanjeev Khanna, Madhu Sudan. (SODA 2014.)

2013

  1. Optimal Error Rates for Interactive Coding I: Adaptivity and Other Settings. Mohsen Ghaffari, Bernhard Haeupler, Madhu Sudan. (arxiv, STOC 2014, Errata.)
  2. Limits of local algorithms over sparse random graphs. David Gamarnik, Madhu Sudan. (arxiv, ITCS 2014, Annals Prob. 2017.)
  3. Absolutely Sound Testing of Lifted Codes. Elad Haramaty, Noga Ron-Zewi, Madhu Sudan. (ECCC, Random 2013, TOC 2015). 
  4. Universal Communication via Robust Coordination. Jacob D. Leshno, Madhu Sudan. (Manuscript.)

2012

  1. Deterministic Compression with Uncertain Priors. Elad Haramaty, Madhu Sudan. (arxiv, ITCS 2014, Algorithmica 2016.)
  2. Queueing with future information. Joel Spencer, Madhu Sudan, Kuang Xu. (arxiv, SIGMETRICS PER 2013, Annals Appl. Prob. 2014.)
  3. New affine-invariant codes from lifting. Alan Guo, Swastik Kopparty, Madhu Sudan. (arxiv, ITCS 2013.)
  4. Communication amid uncertainty. Madhu Sudan. (ITW 2012.)
  5. Sparse affine-invariant linear codes are locally testable. Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan. (ECCC, FOCS 2012, Comp. Comp. 2017.) 
  6. Some closure features of locally testable affine-invariant properties. Alan Guo, Madhu Sudan. (ECCC.)
  7. A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes. Noga Ron-Zewi, Madhu Sudan. (arxiv, Random 2012, TOC 2013.) 

2011

  1. Physical limits of Communication (Invited Talk). Madhu Sudan. (FSTTCS.)
  2. Delays and the Capacity of Continuous-Time Channels. Sanjeev Khanna, Madhu Sudan. (arxiv, FOCS 2011.)
  3. On Sums of Locally Testable Affine Invariant Properties. Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan. (ECCC, Random 2011.) 
  4. Optimal Testing of Multivariate Polynomials over Small Prime Fields. Elad Haramaty, Amir Shpilka, Madhu Sudan. (ECCC, FOCS 2011, SICOMP 2013.) 
  5. Patterns hidden from simple algorithms: technical perspective. Madhu Sudan. (CACM.)
  6. Testing linear properties: Some general themes. Madhu Sudan. (ECCC, SIGACT News Guest Column 2011.)
  7. Compression without a common prior: an information-theoretic justification for ambiguity in language. Brendan Juba, Adam Tauman Kalai, Sanjeev Khanna, Madhu Sudan. (ICS 2011.)

2010

  1. Symmetric LDPC Codes are not Necessarily Locally Testable. Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan. (ECCC, CCC 2011.)
  2. Property Testing via Set-Theoretic Operations. Victor Chen, Madhu Sudan, Ning Xie. (arxiv, ICS 2011.) 
  3. Efficient Semantic Communication via Compatible Beliefs. Brendan Juba, Madhu Sudan. (ECCC, ICS 2011.)
  4. Testing Linear-Invariant Non-linear Properties: A Short Report. Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie. (ECCC, LNCS 2010.)
  5. Limits on the Rate of Locally Testable Affine-Invariant Codes. Eli Ben-Sasson, Madhu Sudan. (ECCC, Random 2011) 
  6. The P vs. NP problem. Madhu Sudan. (English original. An Italian translation titled Il problema P = NP appears in La matematica, vol. 4, Pensare il mondo, edited by Claudio Bartocci and Piergiorgio Odifreddi, pages 161–179, Einaudi, Torino, 2010.)
  7. Tight asymptotic bounds for the deletion channel with small deletion probabilities. Adam Kalai, Michael Mitzenmacher, Madhu Sudan. (ISIT 2010.)
  8. Invariance in Property Testing. Madhu Sudan. (ECCC, LNCS 2010.)
  9. Kakeya-type sets in finite vector spaces. Swastik Kopparty, Vsevolod F. Lev, Shubhangi Saraf, Madhu Sudan. (arxiv, J. Alg. Comb. 2011.)

2009

  1. Optimal Testing of Reed-Muller Codes. Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman. (arxiv 2009, LNCS 2010, FOCS 2010.) 
  2. A theory of goal-oriented communication. Oded Goldreich, Brendan Juba, Madhu Sudan. (ECCC, PODC 2011, JACM 2012.) 
  3. Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers. Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan. (ECCC, FOCS 2009, SICOMP 2013.)
  4. Succinct Representation of Codes with Applications to Testing. Elena Grigorescu, Tali Kaufman, Madhu Sudan. (arxiv, Random 2009, SIDMA 2012.)
  5. Locally Testable Codes Require Redundant Testers. Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman. (ECCC, CCC 2009, SICOMP 2010.)
  6. Probabilistically checkable proofs. Madhu Sudan. (CACM 2009.)

2008

  1. Universal Semantic Communication II: A Theory of Goal-Oriented Communication. Brendan Juba, Madhu Sudan. (ECCC. This paper is subsumed by the paper “A theory of goal-oriented communication” from 2009. )
  2. Improved lower bound on the size of Kakeya sets over finite fields. Shubhangi Saraf, Madhu Sudan. (Anal. PDE.)
  3. Reliable Transmission of Information. Madhu Sudan. (Chapter VII.6 in “The Princeton Companion to Mathematics” edited by Tim Gowers along with June Barrow-Green and Imre Leader.)
  4. 2-Transitivity is Insufficient for Local Testability. Elena Grigorescu, Tali Kaufman, Madhu Sudan. (ECCC, CCC 2008, Comp. Comp. 2013.)
  5. Decodability of Group Homomorphisms beyond the Johnson Bound. Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan. (ECCC, STOC 2008.)
  6. Testing Linear-Invariant Non-Linear Properties. Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie. (ECCC, STACS 2009, TOC 2011.)
  7. Algebraic algorithms and coding theory. Madhu Sudan. (ISSAC 2008.) 

2007

  1. Algebraic property testing: the role of invariance. Tali Kaufman, Madhu Sudan. (ECCC, STOC 2008.)
  2. Universal semantic communication I. Brendan Juba, Madhu Sudan. (early version, ECCC, STOC 2008.)
  3. Sparse Random Linear Codes are Locally Decodable and Testable. Tali Kaufman, Madhu Sudan. (ECCC, FOCS 2007.) 
  4. Amplifying Collision Resistance: A Complexity-Theoretic Treatment. Ran Canetti, Ronald L. Rivest, Madhu Sudan, Luca Trevisan, Salil P. Vadhan, Hoeteck Wee. (CRYPTO 2007.)

2006

  1. On Dinur’s Proof of the PCP Theorem. Jaikumar Radhakrishnan, Madhu Sudan. (Bull. AMS 2006. Merges this paper by Jaikumar Radhakrishnan, and this paper by Madhu Sudan. Clarification 2022.)
  2. Local Decoding and Testing for Homomorphisms. Elena Grigorescu, Swastik Kopparty, Madhu Sudan. (Random 2006.)
  3. Robust local testability of tensor products of LDPC codes. Irit Dinur, Madhu Sudan, Avi Wigderson. (ECCC, Random 2006.)
  4. Modelling Errors and Recovery for Communication. Madhu Sudan. (LATIN 2006.)

2005

  1. Distributed Computing with Imperfect Randomness. Shafi Goldwasser, Madhu Sudan, Vinod Vaikuntanathan. (Manuscript, DISC 2005.) 
  2. Short PCPs Verifiable in Polylogarithmic Time. Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan. (Manuscript, CCC 2005.) 
  3. Derandomization of auctions. Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan. (STOC 2005, GEB 2011.)
  4. Optimal Error Correction for Computationally Bounded Noise. Silvio Micali, Chris Peikert, Madhu Sudan, David A. Wilson. (TCC 2005, IEEE IT 2010.) 

2004

  1. Probabilistically Checkable Proofs. Madhu Sudan (Scribe: Venkatesan Guruswami). (Book chapter in Computational Complexity Theory 2004.)
  2. From Logarithmic Advice to Single-Bit Advice. Oded Goldreich, Madhu Sudan, Luca Trevisan. (ECCC, LNCS 2011.)
  3. Robust locally testable codes and products of codes. Eli Ben-Sasson, Madhu Sudan. (arxiv, Random 2004, RSA 2006.)
  4. Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan. (ECCC, STOC 2004, SICOMP 2006.)
  5. Short PCPs with Polylog Query Complexity. Eli Ben-Sasson, Madhu Sudan. (ECCC, STOC 2005, SICOMP 2008.)

2003

  1. Quick and Dirty Refereeing? Madhu Sudan. (Science 2003. Personal version.)
  2. Bounds on 2-Query Codeword Testing. Eli Ben-Sasson, Oded Goldreich, Madhu Sudan. (ECCC, Random 2003.)
  3. Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, Avi Wigderson. (STOC 2003.)
  4. Reconstructing curves in three (and higher) dimensional space from noisy data. Don Coppersmith, Madhu Sudan. (STOC 2003.)

2002

  1. Locally testable codes and PCPs of almost-linear length. Oded Goldreich, Madhu Sudan. (ECCC, FOCS 2002, JACM 2006.) 
  2. A Fuzzy Vault Scheme. Ari Juels, Madhu Sudan. (IACR 2002, Des. Codes Cryp. 2006.)  
  3. Decoding Concatenated Codes using Soft Information. Venkatesan Guruswami, Madhu Sudan. (CCC 2002.)
  4. Reflections on “Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes”. Venkatesan Guruswami, Madhu Sudan. (IEEE IT Soc. Newsletter 2002.)
  5. Harmonic broadcasting is bandwidth-optimal assuming constant bit rate. Lars Engebretsen, Madhu Sudan. (SODA 2002, Networks 2006.) 
  6. Guessing secrets efficiently via list decoding. Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan. (SODA 2002, TALG 2007.)

2001

  1. Extensions to the Johnson bound. Venkatesan Guruswami, Madhu Sudan. (Manuscript 2001.)
  2. Complexity classifications of Boolean constraint satisfaction problems. Nadia Creignou, Sanjeev Khanna, Madhu Sudan.  (SIGACT News 2001.)
  3. Complexity classifications of Boolean constraint satisfaction problems. Nadia Creignou, Sanjeev Khanna, Madhu Sudan. (SIAM monograph 2001. Alas no public online version only this link.)
  4. Ideal Error-Correcting Codes: Unifying Algebraic and Number-Theoretic Algorithms. Madhu Sudan. (AAECC 2001.)
  5. Coding Theory: Tutorial and Survey. Madhu Sudan. (FOCS 2001.)

2000

  1. “Soft-decision” Decoding of Chinese Remainder Codes. Venkatesan Guruswami, Amit Sahai, Madhu Sudan. (FOCS 2000.)
  2. Hardness of Approximate Hypergraph Coloring. Venkatesan Guruswami, Johan Håstad, Madhu Sudan. (ECCC, FOCS 2000, SICOMP 2002.)
  3. Combinatorial bounds for list decoding. Venkatesan Guruswami, Johan Håstad, Madhu Sudan, David Zuckerman. (Allerton 2000. IEEE IT 2002.)
  4. On representations of algebraic-geometry codes.  (ESA 2000, IEEE IT 2001.)
  5. List decoding: algorithms and applications. Madhu Sudan. (SIGACT News 2000.)
  6. List decoding: Algorithms and applications. Madhu Sudan. (IFIP TCS 2000.)
  7. List decoding algorithms for certain concatenated codes. Venkatesan Guruswami, Madhu Sudan. (Manuscript 2000, STOC 2000.)
  8. Random walks with “back buttons”. Ronald Fagin, Anna R. Karlin, Jon M. Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, Madhu Sudan, Andrew Tomkins. (STOC 2000, Annals Appl. Prob. 2001.) 
  9. Small PCPs with Low Query Complexity. Prahladh Harsha, Madhu Sudan. (ECCC, STACS 2001, Comp. Comp. 2000.) 
  10. The Approximability of Constraint Satisfaction Problems. Sanjeev Khanna, Madhu Sudan, Luca Trevisan, David P. Williamson. (SICOMP 2000.) 

1999

  1. Hardness of approximating the minimum distance of a linear code. Ilya Dumer, Daniele Micciancio, Madhu Sudan. (ECCC, FOCS 1999, IEEE IT 2003.)
  2. Linear-Consistency Testing. Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan. (ECCC, Random 1999, JCSS 2001.)

1998

  1. A Tight Characterization of NP with 3 Query PCPs. Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan. (ECCC, FOCS 1998.)
  2. Probabilistically Checkable Proofs with Low Amortized Query Complexity. Madhu Sudan, Luca Trevisan. (ECCC, FOCS 1998.)
  3. Improved decoding of Reed-Solomon and algebraic-geometry codes. Venkatesan Guruswami, Madhu Sudan. (ECCC, FOCS 1998, IEEE IT 1999.)
  4. Probabilistic verification of proofs. Madhu Sudan. (ICM 1998.)
  5. Computational Indistinguishability: A Sample Hierarchy. Oded Goldreich, Madhu Sudan. (ECCC, CCC 1998, JCSS 1999.)
  6. Chinese remaindering with errors. Oded Goldreich, Dana Ron, Madhu Sudan. (ECCC, STOC 1999, IEEE IT 2000.) 
  7. Pseudorandom Generators without the XOR Lemma. Madhu Sudan, Luca Trevisan, Salil P. Vadhan. (ECCC, STOC 1999, CCC 1999, JCSS 2001.)

1997

  1. Algorithmic issues in coding theory. Madhu Sudan. (FSTTCS 1997.) 
  2. A statistical perspective on data mining. Jonathan R. M. Hosking, Edwin P. D. Pednault, Madhu Sudan. (FGCS 1997.)
  3. Decoding Reed-Solomon codes beyond the error-correction diameter. Madhu Sudan. (Allerton 1997.)
  4. Improved Low-Degree Testing and its Applications. Sanjeev Arora, Madhu Sudan. (ECCC, STOC 1997, Combinatorica 2003.)

1996

  1. A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. Sanjeev Khanna, Madhu Sudan, David P. Williamson. (ECCC, STOC 1997, SICOMP 2000 (full version of paper merged with paper below).)
  2. Constraint Satisfaction: The Approximability of Minimization Problems. Sanjeev Khanna, Madhu Sudan, Luca Trevisan. (ECCC, CCC 1997, SICOMP 2000 (full version of paper merged with paper above).)
  3. Decoding of Reed Solomon Codes beyond the Error-Correction Bound. Madhu Sudan. (FOCS 1996 (with a different title), J. Complexity 1997.)
  4. Gadgets, Approximation, and Linear Programming. Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson. (FOCS 1996 (includes an errata page), SICOMP 2000.)
  5. Adversarial queuing theory. Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson. (STOC 1996, JACM 2001.) 
  6. Robust Characterizations of Polynomials with Applications to Program Testing. Ronitt Rubinfeld, Madhu Sudan. (SICOMP 1996.) 
  7. The Optimization Complexity of Constraint Satisfaction Problems. Sanjeev Khanna, Madhu Sudan. (ECCC.) 

1995

  1. Private Information Retrieval. Benny Chor, Eyal Kushilevitz, Oded Goldreich, Madhu Sudan. (FOCS 1995, JACM 1998.)
  2. Learning Polynomials with Queries: The Highly Noisy Case. Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan. (FOCS 1995, ECCC 1998, SIDMA 2000.) 
  3. Free Bits, PCPs, and Nonapproximability-Towards Tight Results. Mihir Bellare, Oded Goldreich, Madhu Sudan. (ECCC, FOCS 1995, SICOMP 1998.)
  4. Linearity testing in characteristic two. Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, Madhu Sudan. (FOCS 1995, IEEE IT 1996.)
  5. A Geometric Approach to Betweenness. Benny Chor, Madhu Sudan. (ESA 1995, SIDMA 1998.)
  6. Approximating Minimum Feedback Sets and Multicuts in Directed Graphs. Guy Even, Joseph Naor, Baruch Schieber, Madhu Sudan. (IPCO 1995, Algorithmica 1998.)
  7. Guaranteeing Fair Service to Persistent Dependent Tasks. Amotz Bar-Noy, Alain J. Mayer, Baruch Schieber, Madhu Sudan. (SODA 1995, SICOMP 1998.)
  8. Some Improvements to Total Degree Tests. Katalin Friedl, Madhu Sudan. (ISTCS 1995, Arxiv 2013.) 
  9. Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems. Madhu Sudan. (Springer LNCS 1995. No pdf – just an online link.)

1994

  1. On the role of algebra in the efficient verification of proofs. Madhu Sudan. (AMCOT 1994.)
  2. Approximate Graph Coloring by Semidefinite Programming. David R. Karger, Rajeev Motwani, Madhu Sudan. (FOCS 1994, Arxiv 1988, JACM 1998.)
  3. Motion Planning on a Graph. Christos H. Papadimitriou, Prabhakar Raghavan, Madhu Sudan, Hisao Tamaki. (FOCS 1994, Fuller version (+appendix).)
  4. Priority encoding transmission. Andres Albanese, Johannes Blömer, Jeff Edmonds, Michael Luby, Madhu Sudan. (FOCS 1994, IEEE IT 1996.)
  5. On Syntactic versus Computational Views of Approximability. Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani. (FOCS 1994, ECCC 1995, SICOMP 1998.)
  6. Computing Roots of Graphs Is Hard. Rajeev Motwani, Madhu Sudan. (Disc. Appl. Math 1994.)
  7. The minimum latency problem. Avrim Blum, Prasad Chalasani, Don Coppersmith, William R. Pulleyblank, Prabhakar Raghavan, Madhu Sudan. (arxiv, STOC 1994.)
  8. Improved non-approximability results. Mihir Bellare, Madhu Sudan. (STOC 1994.)
  9. Efficient Routing in Optical Networks. Alok Aggarwal, Amotz Bar-Noy, Don Coppersmith, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan. (SODA 1994, JACM 1996.)

1993

(Intentionally blank)

1992

  1. Reconstructing Algebraic Functions from Mixed Data. Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan. (FOCS 1992, SICOMP 1998.)
  2. Proof Verification and the Hardness of Approximation Problems. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy. (FOCS 1992, ECCC 1998, JACM 1998.)
  3. Efficient checking of polynomials and proofs, and the hardness of approximation problems. Madhu Sudan. (UCBerkeley PhD Thesis 1992.)
  4. Highly Resilient Correctors for Polynomials. Peter Gemmell, Madhu Sudan. (IPL 1992.)
  5. Self-Testing Polynomial Functions Efficiently and Over Rational Domains. Ronitt Rubinfeld, Madhu Sudan. (SODA 1992.)

1991

  1. Connectivity properties of matroids. Milena Mihail, Madhu Sudan. (UCB TR #CSD-91-662 1991.)
  2. Self-Testing/Correcting for Polynomials and for Approximate Functions. Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson. (STOC 1991.)

1990

  1. On-Line Algorithms for Locating Checkpoints. Marshall W. Bern, Daniel H. Greene, Arvind Raghunathan, Madhu Sudan. (STOC 1990, Algorithmica 1994.)