Madhu Sudan

Elena Grigorescu, Tali Kaufman, Madhu Sudan: 2-Transitivity is Insufficient for Local Testability. Computational Complexity 22(1): 137-158 (2013)

Alan Guo, Swastik Kopparty, Madhu Sudan: New affine-invariant codes from lifting. ITCS 2013: 529-540

David Gamarnik, Madhu Sudan: Limits of local algorithms over sparse random graphs. CoRR abs/1304.1831 (2013)

Elad Haramaty, Noga Ron-Zewi, Madhu Sudan: Absolutely Sound Testing of Lifted Codes. Electronic Colloquium on Computational Complexity (ECCC) 20: 30 (2013)

David Gamarnik, Madhu Sudan: Limits of local algorithms over sparse random graphs. Electronic Colloquium on Computational Complexity (ECCC) 20: 55 (2013)

Oded Goldreich, Brendan Juba, Madhu Sudan: A theory of goal-oriented communication. J. ACM 59(2): 8 (2012)

Elena Grigorescu, Tali Kaufman, Madhu Sudan: Succinct Representation of Codes with Applications to Testing. SIAM J. Discrete Math. 26(4): 1618-1634 (2012)

Noga Ron-Zewi, Madhu Sudan: A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller codes. APPROX-RANDOM 2012: 639-650

Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan: Sparse Affine-Invariant Linear Codes Are Locally Testable. FOCS 2012: 561-570

Noga Ron-Zewi, Madhu Sudan: A new upper bound on the query complexity for testing generalized Reed-Muller codes. CoRR abs/1204.5467 (2012)

Alan Guo, Madhu Sudan: New affine-invariant codes from lifting. CoRR abs/1208.5413 (2012)

Joel Spencer, Madhu Sudan, Kuang Xu: Queueing with Future Information. CoRR abs/1211.0618 (2012)

Elad Haramaty, Madhu Sudan: Deterministic Compression with Uncertain Priors. CoRR abs/1211.5718 (2012)

Madhu Sudan, Noga Zewi: A new upper bound on the query complexity for testing generalized Reed-Muller codes. Electronic Colloquium on Computational Complexity (ECCC) 19: 46 (2012)

Alan Guo, Madhu Sudan: Some closure features of locally testable affine-invariant properties. Electronic Colloquium on Computational Complexity (ECCC) 19: 48 (2012)

Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan: Sparse affine-invariant linear codes are locally testable. Electronic Colloquium on Computational Complexity (ECCC) 19: 49 (2012)

Alan Guo, Madhu Sudan: New affine-invariant codes from lifting. Electronic Colloquium on Computational Complexity (ECCC) 19: 106 (2012)

Alan Guo, Swastik Kopparty, Madhu Sudan: New affine-invariant codes from lifting. Electronic Colloquium on Computational Complexity (ECCC) 19: 149 (2012)

Elad Haramaty, Madhu Sudan: Deterministic Compression with Uncertain Priors. Electronic Colloquium on Computational Complexity (ECCC) 19: 166 (2012)

Madhu Sudan: Patterns hidden from simple algorithms: technical perspective. Commun. ACM 54(4): 107 (2011)

Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan: Derandomization of auctions. Games and Economic Behavior 72(1): 1-11 (2011)

Madhu Sudan: Guest column: testing linear properties: some general theme. SIGACT News 42(1): 59-80 (2011)

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie: Testing Linear-Invariant Non-Linear Properties. Theory of Computing 7(1): 75-99 (2011)

Oded Goldreich, Madhu Sudan, Luca Trevisan: From Logarithmic Advice to Single-Bit Advice. Studies in Complexity and Cryptography 2011: 109-113

Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan: On Sums of Locally Testable Affine Invariant Properties. APPROX-RANDOM 2011: 400-411

Eli Ben-Sasson, Madhu Sudan: Limits on the Rate of Locally Testable Affine-Invariant Codes. APPROX-RANDOM 2011: 412-423

Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan: Symmetric LDPC Codes are not Necessarily Locally Testable. IEEE Conference on Computational Complexity 2011: 55-65

Elad Haramaty, Amir Shpilka, Madhu Sudan: Optimal Testing of Multivariate Polynomials over Small Prime Fields. FOCS 2011: 629-637

Sanjeev Khanna, Madhu Sudan: Delays and the Capacity of Continuous-Time Channels. FOCS 2011: 758-767

Madhu Sudan: Physical limits of Communication (Invited Talk). FSTTCS 2011: 4-5

Brendan Juba, Madhu Sudan: Efficient Semantic Communication via Compatible Beliefs. ICS 2011: 22-31

Brendan Juba, Adam Tauman Kalai, Sanjeev Khanna, Madhu Sudan: Compression without a common prior: an information-theoretic justification for ambiguity in language. ICS 2011: 79-86

Victor Chen, Madhu Sudan, Ning Xie: Property Testing via Set-Theoretic Operations. ICS 2011: 211-222

Oded Goldreich, Brendan Juba, Madhu Sudan: A theory of goal-oriented communication. PODC 2011: 299-300

Sanjeev Khanna, Madhu Sudan: Delays and the Capacity of Continuous-time Channels. CoRR abs/1105.3425 (2011)

Madhu Sudan: Testing Linear Properties: Some general themes. Electronic Colloquium on Computational Complexity (ECCC) 18: 5 (2011)

Elad Haramaty, Amir Shpilka, Madhu Sudan: Optimal testing of multivariate polynomials over small prime fields. Electronic Colloquium on Computational Complexity (ECCC) 18: 59 (2011)

Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan: On Sums of Locally Testable Affine Invariant Properties. Electronic Colloquium on Computational Complexity (ECCC) 18: 79 (2011)

Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman: Locally Testable Codes Require Redundant Testers. SIAM J. Comput. 39(7): 3230-3247 (2010)

Silvio Micali, Chris Peikert, Madhu Sudan, David A. Wilson: Optimal Error Correction for Computationally Bounded Noise. IEEE Transactions on Information Theory 56(11): 5673-5680 (2010)

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman: Optimal Testing of Reed-Muller Codes. FOCS 2010: 488-497

Adam Kalai, Michael Mitzenmacher, Madhu Sudan: Tight asymptotic bounds for the deletion channel with small deletion probabilities. ISIT 2010: 997-1001

Madhu Sudan: Invariance in Property Testing. Property Testing 2010: 211-227

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie: Testing Linear-Invariant Non-linear Properties: A Short Report. Property Testing 2010: 260-268

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman: Optimal Testing of Reed-Muller Codes. Property Testing 2010: 269-275

Victor Chen, Madhu Sudan, Ning Xie: Property Testing via Set-Theoretic Operations. CoRR abs/1010.4925 (2010)

Madhu Sudan: Invariance in Property Testing. Electronic Colloquium on Computational Complexity (ECCC) 17: 51 (2010)

Eli Ben-Sasson, Madhu Sudan: Limits on the rate of locally testable affine-invariant codes. Electronic Colloquium on Computational Complexity (ECCC) 17: 108 (2010)

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie: Testing linear-invariant non-linear properties: A short report. Electronic Colloquium on Computational Complexity (ECCC) 17: 116 (2010)

Brendan Juba, Madhu Sudan: Efficient Semantic Communication via Compatible Beliefs. Electronic Colloquium on Computational Complexity (ECCC) 17: 155 (2010)

Victor Chen, Madhu Sudan, Ning Xie: Property Testing via Set-Theoretic Operations. Electronic Colloquium on Computational Complexity (ECCC) 17: 156 (2010)

Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan: Symmetric LDPC codes are not necessarily locally testable. Electronic Colloquium on Computational Complexity (ECCC) 17: 199 (2010)

Madhu Sudan: Probabilistically checkable proofs. Commun. ACM 52(3): 76-84 (2009)

Elena Grigorescu, Tali Kaufman, Madhu Sudan: Succinct Representation of Codes with Applications to Testing. APPROX-RANDOM 2009: 534-547

Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman: Locally Testable Codes Require Redundant Testers. IEEE Conference on Computational Complexity 2009: 52-61

Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan: Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers. FOCS 2009: 181-190

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie: Testing Linear-Invariant Non-Linear Properties. STACS 2009: 135-146

Elena Grigorescu, Tali Kaufman, Madhu Sudan: Succinct Representation of Codes with Applications to Testing. CoRR abs/0905.2919 (2009)

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman: Optimal Testing of Reed-Muller Codes. CoRR abs/0910.0641 (2009)

Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan: Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers. Electronic Colloquium on Computational Complexity (ECCC) 16: 4 (2009)

Elena Grigorescu, Tali Kaufman, Madhu Sudan: Succinct Representation of Codes with Applications to Testing. Electronic Colloquium on Computational Complexity (ECCC) 16: 43 (2009)

Oded Goldreich, Brendan Juba, Madhu Sudan: A Theory of Goal-Oriented Communication. Electronic Colloquium on Computational Complexity (ECCC) 16: 75 (2009)

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman: Optimal testing of Reed-Muller codes. Electronic Colloquium on Computational Complexity (ECCC) 16: 86 (2009)

Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman: Locally Testable Codes Require Redundant Testers. Electronic Colloquium on Computational Complexity (ECCC) 16: 126 (2009)

Eli Ben-Sasson, Madhu Sudan: Short PCPs with Polylog Query Complexity. SIAM J. Comput. 38(2): 551-607 (2008)

Elena Grigorescu, Tali Kaufman, Madhu Sudan: 2-Transitivity Is Insufficient for Local Testability. IEEE Conference on Computational Complexity 2008: 259-267

Madhu Sudan: Algebraic algorithms and coding theory. ISSAC 2008: 337

Brendan Juba, Madhu Sudan: Universal semantic communication I. STOC 2008: 123-132

Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan: Decodability of group homomorphisms beyond the johnson bound. STOC 2008: 275-284

Tali Kaufman, Madhu Sudan: Algebraic property testing: the role of invariance. STOC 2008: 403-412

Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan: Decodability of Group Homomorphisms beyond the Johnson Bound. Electronic Colloquium on Computational Complexity (ECCC) 15(020) (2008)

Elena Grigorescu, Tali Kaufman, Madhu Sudan: 2-Transitivity is Insufficient for Local Testability. Electronic Colloquium on Computational Complexity (ECCC) 15(033) (2008)

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie: Testing Linear-Invariant Non-Linear Properties. Electronic Colloquium on Computational Complexity (ECCC) 15(088) (2008)

Brendan Juba, Madhu Sudan: Universal Semantic Communication II: A Theory of Goal-Oriented Communication. Electronic Colloquium on Computational Complexity (ECCC) 15(095) (2008)

Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan: Guessing secrets efficiently via list decoding. ACM Transactions on Algorithms 3(4) (2007)

Ran Canetti, Ronald L. Rivest, Madhu Sudan, Luca Trevisan, Salil P. Vadhan, Hoeteck Wee: Amplifying Collision Resistance: A Complexity-Theoretic Treatment. CRYPTO 2007: 264-283

Tali Kaufman, Madhu Sudan: Sparse Random Linear Codes are Locally Decodable and Testable. FOCS 2007: 590-600

Tali Kaufman, Madhu Sudan: Sparse Random Linear Codes are Locally Decodable and Testable. Electronic Colloquium on Computational Complexity (ECCC) 14(060) (2007)

Brendan Juba, Madhu Sudan: Universal Semantic Communication I. Electronic Colloquium on Computational Complexity (ECCC) 14(084) (2007)

Tali Kaufman, Madhu Sudan: Algebraic Property Testing: The Role of Invariance. Electronic Colloquium on Computational Complexity (ECCC) 14(111) (2007)

Ari Juels, Madhu Sudan: A Fuzzy Vault Scheme. Des. Codes Cryptography 38(2): 237-257 (2006)

Oded Goldreich, Madhu Sudan: Locally testable codes and PCPs of almost-linear length. J. ACM 53(4): 558-655 (2006)

Lars Engebretsen, Madhu Sudan: Harmonic broadcasting is bandwidth-optimal assuming constant bit rate. Networks 47(3): 172-177 (2006)

Eli Ben-Sasson, Madhu Sudan: Robust locally testable codes and products of codes. Random Struct. Algorithms 28(4): 387-402 (2006)

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan: Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. SIAM J. Comput. 36(4): 889-974 (2006)

Oded Goldreich, Madhu Sudan: Special Issue on Randomness and Complexity. SIAM J. Comput. 36(4) (2006)

Irit Dinur, Madhu Sudan, Avi Wigderson: Robust Local Testability of Tensor Products of LDPC Codes. APPROX-RANDOM 2006: 304-315

Elena Grigorescu, Swastik Kopparty, Madhu Sudan: Local Decoding and Testing for Homomorphisms. APPROX-RANDOM 2006: 375-385

Madhu Sudan: Modelling Errors and Recovery for Communication. LATIN 2006: 25-25

Irit Dinur, Madhu Sudan, Avi Wigderson: Robust Local Testability of Tensor Products of LDPC Codes. Electronic Colloquium on Computational Complexity (ECCC) 13(118) (2006)

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan: Short PCPs Verifiable in Polylogarithmic Time. IEEE Conference on Computational Complexity 2005: 120-134

Eli Ben-Sasson, Madhu Sudan: Simple PCPs with poly-log rate and query complexity. STOC 2005: 266-275

Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan: Derandomization of auctions. STOC 2005: 619-625

Silvio Micali, Chris Peikert, Madhu Sudan, David A. Wilson: Optimal Error Correction Against Computationally Bounded Noise. TCC 2005: 1-16

Shafi Goldwasser, Madhu Sudan, Vinod Vaikuntanathan: Distributed Computing with Imperfect Randomness. DISC 2005: 288-302

Eli Ben-Sasson, Madhu Sudan: Robust Locally Testable Codes and Products of Codes. APPROX-RANDOM 2004: 286-297

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan: Robust pcps of proximity, shorter pcps and applications to coding. STOC 2004: 1-10

Eli Ben-Sasson, Madhu Sudan: Robust Locally Testable Codes and Products of Codes. CoRR cs.IT/0408066 (2004)

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan: Robust PCPs of Proximity, Shorter PCPs and Applications to Coding. Electronic Colloquium on Computational Complexity (ECCC)(021) (2004)

Eli Ben-Sasson, Madhu Sudan: Robust Locally Testable Codes and Products of Codes. Electronic Colloquium on Computational Complexity (ECCC)(046) (2004)

Eli Ben-Sasson, Madhu Sudan: Simple PCPs with Poly-log Rate and Query Complexity. Electronic Colloquium on Computational Complexity (ECCC)(060) (2004)

Oded Goldreich, Madhu Sudan, Luca Trevisan: From logarithmic advice to single-bit advice. Electronic Colloquium on Computational Complexity (ECCC)(093) (2004)

Sanjeev Arora, Madhu Sudan: Improved Low-Degree Testing and its Applications. Combinatorica 23(3): 365-426 (2003)

Ilya Dumer, Daniele Micciancio, Madhu Sudan: Hardness of approximating the minimum distance of a linear code. IEEE Transactions on Information Theory 49(1): 22-37 (2003)

Eli Ben-Sasson, Oded Goldreich, Madhu Sudan: Bounds on 2-Query Codeword Testing. RANDOM-APPROX 2003: 216-227

Don Coppersmith, Madhu Sudan: Reconstructing curves in three (and higher) dimensional space from noisy data. STOC 2003: 136-142

Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, Avi Wigderson: Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. STOC 2003: 612-621

Eli Ben-Sasson, Oded Goldreich, Madhu Sudan: Bounds on 2-Query Codeword Testing. Electronic Colloquium on Computational Complexity (ECCC) 10(019) (2003)

Madhu Sudan: Foreword. J. Comput. Syst. Sci. 65(4): 611 (2002)

Venkatesan Guruswami, Johan Håstad, Madhu Sudan: Hardness of Approximate Hypergraph Coloring. SIAM J. Comput. 31(6): 1663-1686 (2002)

Venkatesan Guruswami, Johan Håstad, Madhu Sudan, David Zuckerman: Combinatorial bounds for list decoding. IEEE Transactions on Information Theory 48(5): 1021-1034 (2002)

Venkatesan Guruswami, Madhu Sudan: Decoding Concatenated Codes using Soft Information. IEEE Conference on Computational Complexity 2002: 148-157

Oded Goldreich, Madhu Sudan: Locally Testable Codes and PCPs of Almost-Linear Length. FOCS 2002: 13-22

Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan: Guessing secrets efficiently via list decoding. SODA 2002: 254-262

Lars Engebretsen, Madhu Sudan: Harmonic broadcasting is optimal. SODA 2002: 431-432

Oded Goldreich, Madhu Sudan: Locally Testable Codes and PCPs of Almost-Linear Length. Electronic Colloquium on Computational Complexity (ECCC)(050) (2002)

Ari Juels, Madhu Sudan: A Fuzzy Vault Scheme. IACR Cryptology ePrint Archive 2002: 93 (2002)

Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson: Adversarial queuing theory. J. ACM 48(1): 13-38 (2001)

Madhu Sudan, Luca Trevisan, Salil P. Vadhan: Pseudorandom Generators without the XOR Lemma. J. Comput. Syst. Sci. 62(2): 236-266 (2001)

Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan: Linear-Consistency Testing. J. Comput. Syst. Sci. 62(4): 589-607 (2001)

Venkatesan Guruswami, Madhu Sudan: On representations of algebraic-geometry codes. IEEE Transactions on Information Theory 47(4): 1610-1613 (2001)

Madhu Sudan: Ideal Error-Correcting Codes: Unifying Algebraic and Number-Theoretic Algorithms. AAECC 2001: 36-45

Madhu Sudan: Coding Theory: Tutorial and Survey. FOCS 2001: 36-53

Prahladh Harsha, Madhu Sudan: Small PCPs with Low Query Complexity. STACS 2001: 327-338

Prahladh Harsha, Madhu Sudan: Small PCPs with low query complexity. Computational Complexity 9(3-4): 157-201 (2000)

Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson: Gadgets, Approximation, and Linear Programming. SIAM J. Comput. 29(6): 2074-2097 (2000)

Sanjeev Khanna, Madhu Sudan, Luca Trevisan, David P. Williamson: The Approximability of Constraint Satisfaction Problems. SIAM J. Comput. 30(6): 1863-1920 (2000)

Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan: Learning Polynomials with Queries: The Highly Noisy Case. SIAM J. Discrete Math. 13(4): 535-570 (2000)

Madhu Sudan: List decoding: algorithms and applications. SIGACT News 31(1): 16-27 (2000)

Oded Goldreich, Dana Ron, Madhu Sudan: Chinese remaindering with errors. IEEE Transactions on Information Theory 46(4): 1330-1338 (2000)

Venkatesan Guruswami, Madhu Sudan: On Representations of Algebraic-Geometric Codes for List Decoding. ESA 2000: 244-255

Venkatesan Guruswami, Johan Håstad, Madhu Sudan: Hardness of Approximate Hypergraph Coloring. FOCS 2000: 149-158

Venkatesan Guruswami, Amit Sahai, Madhu Sudan: "Soft-decision" Decoding of Chinese Remainder Codes. FOCS 2000: 159-168

Madhu Sudan: List Decoding: Algorithms and Applications. IFIP TCS 2000: 25-41

Venkatesan Guruswami, Madhu Sudan: List decoding algorithms for certain concatenated codes. STOC 2000: 181-190

Ronald Fagin, Anna R. Karlin, Jon M. Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, Madhu Sudan, Andrew Tomkins: Random walks with ``back buttons'' (extended abstract). STOC 2000: 484-493

Prahladh Harsha, Madhu Sudan: Small PCPs with low query complexity. Electronic Colloquium on Computational Complexity (ECCC) 7(61) (2000)

Venkatesan Guruswami, Johan Håstad, Madhu Sudan: Hardness of approximate hypergraph coloring. Electronic Colloquium on Computational Complexity (ECCC) 7(62) (2000)

Oded Goldreich, Madhu Sudan: Computational Indistinguishability: A Sample Hierarchy. J. Comput. Syst. Sci. 59(2): 253-269 (1999)

Venkatesan Guruswami, Madhu Sudan: Improved decoding of Reed-Solomon and algebraic-geometry codes. IEEE Transactions on Information Theory 45(6): 1757-1767 (1999)

Madhu Sudan, Luca Trevisan, Salil P. Vadhan: Pseudorandom Generators without the XOR Lemma (Abstract). IEEE Conference on Computational Complexity 1999: 4

Ilya Dumer, Daniele Micciancio, Madhu Sudan: Hardness of Approximating the Minimum Distance of a Linear Code. FOCS 1999: 475-485

Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan: Linear Consistency Testing. RANDOM-APPROX 1999: 109-120

Oded Goldreich, Dana Ron, Madhu Sudan: Chinese Remaindering with Errors. STOC 1999: 225-234

Madhu Sudan, Luca Trevisan, Salil P. Vadhan: Pseudorandom Generators Without the XOR Lemma (Extended Abstract). STOC 1999: 537-546

Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan: Linear Consistency Testing. Electronic Colloquium on Computational Complexity (ECCC) 6(25) (1999)

Ilya Dumer, Daniele Micciancio, Madhu Sudan: Hardness of Approximating the Minimum Distance of a Linear Code. Electronic Colloquium on Computational Complexity (ECCC) 6(29) (1999)

Guy Even, Joseph Naor, Baruch Schieber, Madhu Sudan: Approximating Minimum Feedback Sets and Multicuts in Directed Graphs. Algorithmica 20(2): 151-174 (1998)

David R. Karger, Rajeev Motwani, Madhu Sudan: Approximate Graph Coloring by Semidefinite Programming. J. ACM 45(2): 246-265 (1998)

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy: Proof Verification and the Hardness of Approximation Problems. J. ACM 45(3): 501-555 (1998)

Benny Chor, Eyal Kushilevitz, Oded Goldreich, Madhu Sudan: Private Information Retrieval. J. ACM 45(6): 965-981 (1998)

Mihir Bellare, Oded Goldreich, Madhu Sudan: Free Bits, PCPs, and Nonapproximability-Towards Tight Results. SIAM J. Comput. 27(3): 804-915 (1998)

Amotz Bar-Noy, Alain J. Mayer, Baruch Schieber, Madhu Sudan: Guaranteeing Fair Service to Persistent Dependent Tasks. SIAM J. Comput. 27(4): 1168-1189 (1998)

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani: On Syntactic versus Computational Views of Approximability. SIAM J. Comput. 28(1): 164-191 (1998)

Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan: Reconstructing Algebraic Functions from Mixed Data. SIAM J. Comput. 28(2): 487-510 (1998)

Benny Chor, Madhu Sudan: A Geometric Approach to Betweenness. SIAM J. Discrete Math. 11(4): 511-523 (1998)

Oded Goldreich, Madhu Sudan: Computational Indistinguishability: A Sample Hierarchy. IEEE Conference on Computational Complexity 1998: 24-33

Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan: A Tight Characterization of NP with 3 Query PCPs. FOCS 1998: 8-17

Madhu Sudan, Luca Trevisan: Probabilistically Checkable Proofs with Low Amortized Query Complexity. FOCS 1998: 18-27

Venkatesan Guruswami, Madhu Sudan: Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes. FOCS 1998: 28-39

David R. Karger, Rajeev Motwani, Madhu Sudan: Approximate Graph Coloring by Semidefinite Programming. CoRR cs.DS/9812008 (1998)

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy: Proof verification and the hardness of approximation problems. Electronic Colloquium on Computational Complexity (ECCC) 5(8) (1998)

Oded Goldreich, Madhu Sudan: Computational Indistinguishability: A Sample Hierarchy. Electronic Colloquium on Computational Complexity (ECCC) 5(17) (1998)

Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan: A tight characterization of NP with 3 query PCPs. Electronic Colloquium on Computational Complexity (ECCC) 5(34) (1998)

Madhu Sudan, Luca Trevisan: Probabilistically checkable proofs with low amortized query complexity. Electronic Colloquium on Computational Complexity (ECCC) 5(40) (1998)

Venkatesan Guruswami, Madhu Sudan: Improved decoding of Reed-Solomon and algebraic-geometric codes. Electronic Colloquium on Computational Complexity (ECCC) 5(43) (1998)

Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan: Learning Polynomials with Queries - The Highly Noisy Case. Electronic Colloquium on Computational Complexity (ECCC) 5(60) (1998)

Oded Goldreich, Dana Ron, Madhu Sudan: Chinese Remaindering with Errors. Electronic Colloquium on Computational Complexity (ECCC) 5(62) (1998)

Madhu Sudan, Luca Trevisan, Salil P. Vadhan: Pseudorandom generators without the XOR Lemma. Electronic Colloquium on Computational Complexity (ECCC) 5(74) (1998)

Madhu Sudan: Decoding of Reed Solomon Codes beyond the Error-Correction Bound. J. Complexity 13(1): 180-193 (1997)

Sanjeev Khanna, Madhu Sudan, Luca Trevisan: Constraint Satisfaction: The Approximability of Minimization Problems. IEEE Conference on Computational Complexity 1997: 282-296

Madhu Sudan: Algorithmic Issues in Coding Theory. FSTTCS 1997: 184-199

Nachum Shacham, Madhu Sudan, Michael Brown: Conducting a Multiparty Multimedia Session over ATM using Hierarchically Encoded Data. ICC (2) 1997: 811-815

Madhu Sudan, Nachum Shacham: Gateway Based Approach for Conducting Multiparty Multimedia Sessions over Heterogeneous Signaling Domains. INFOCOM 1997: 701-710

Sanjeev Khanna, Madhu Sudan, David P. Williamson: A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. STOC 1997: 11-20

Sanjeev Arora, Madhu Sudan: Improved Low-Degree Testing and its Applications. STOC 1997: 485-495

Sanjeev Arora, Madhu Sudan: Improved low-degree testing and its applications. Electronic Colloquium on Computational Complexity (ECCC) 4(3) (1997)

Alok Aggarwal, Amotz Bar-Noy, Don Coppersmith, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan: Efficient Routing in Optical Networks. J. ACM 43(6): 973-1001 (1996)

Ronitt Rubinfeld, Madhu Sudan: Robust Characterizations of Polynomials with Applications to Program Testing. SIAM J. Comput. 25(2): 252-271 (1996)

Andres Albanese, Johannes Blömer, Jeff Edmonds, Michael Luby, Madhu Sudan: Priority encoding transmission. IEEE Transactions on Information Theory 42(6): 1737-1744 (1996)

Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, Madhu Sudan: Linearity testing in characteristic two. IEEE Transactions on Information Theory 42(6): 1781-1795 (1996)

Madhu Sudan: Maximum Likelihood Decoding of Reed Solomon Codes. FOCS 1996: 164-172

Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson: Gadgets, Approximation, and Linear Programming (extended abstract). FOCS 1996: 617-626

Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson: Adversarial Queueing Theory. STOC 1996: 376-385

Sanjeev Khanna, Madhu Sudan: The Optimization Complexity of Constraint Satisfaction Problems. Electronic Colloquium on Computational Complexity (ECCC) 3(28) (1996)

Sanjeev Khanna, Madhu Sudan, David P. Williamson: A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. Electronic Colloquium on Computational Complexity (ECCC) 3(62) (1996)

Sanjeev Khanna, Madhu Sudan, Luca Trevisan: Constraint satisfaction: The approximability of minimization problems. Electronic Colloquium on Computational Complexity (ECCC) 3(64) (1996)

Madhu Sudan: Efficient Checking of Polynomials and Proofs anf the Hardness of Approximation Problems. Lecture Notes in Computer Science 1001, Springer 1995, isbn 3-540-60615-7

Benny Chor, Madhu Sudan: A Geometric Approach to Betweenness. ESA 1995: 227-237

Benny Chor, Oded Goldreich, Eyal Kushilevitz, Madhu Sudan: Private Information Retrieval. FOCS 1995: 41-50

Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan: Learning Polynomials with Queries: The Highly Noisy Case. FOCS 1995: 294-303

Mihir Bellare, Oded Goldreich, Madhu Sudan: Free Bits, PCPs and Non-Approximability - Towards Tight Results. FOCS 1995: 422-431

Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, Madhu Sudan: Linearity Testing in Characteristic Two. FOCS 1995: 432-441

Guy Even, Joseph Naor, Baruch Schieber, Madhu Sudan: Approximating Minimum Feedback Sets and Multi-Cuts in Directed Graphs. IPCO 1995: 14-28

Katalin Friedl, Madhu Sudan: Some Improvements to Total Degree Tests. ISTCS 1995: 190-198

Rajendra Yavatkar, Jim Griffioen, Madhu Sudan: A Reliable Dissemination Protocol for Interactive Collaborative Applications. ACM Multimedia 1995: 333-344

Amotz Bar-Noy, Alain J. Mayer, Baruch Schieber, Madhu Sudan: Guaranteeing Fair Service to Persistent Dependent Tasks. SODA 1995: 243-252

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani: On Syntactic versus Computational Views of Approximability. Electronic Colloquium on Computational Complexity (ECCC) 2(23) (1995)

Mihir Bellare, Oded Goldreich, Madhu Sudan: Free Bits, PCP and Non-Approximability - Towards Tight Results. Electronic Colloquium on Computational Complexity (ECCC) 2(24) (1995)

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

Rajeev Motwani, Madhu Sudan: Computing Roots of Graphs Is Hard. Discrete Applied Mathematics 54(1): 81-88 (1994)

David R. Karger, Rajeev Motwani, Madhu Sudan: Approximate Graph Coloring by Semidefinite Programming. FOCS 1994: 2-13

Christos H. Papadimitriou, Prabhakar Raghavan, Madhu Sudan, Hisao Tamaki: Motion Planning on a Graph (Extended Abstract). FOCS 1994: 511-520

Andres Albanese, Johannes Blömer, Jeff Edmonds, Michael Luby, Madhu Sudan: Priority Encoding Transmission. FOCS 1994: 604-612

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani: On Syntactic versus Computational Views of Approximability. FOCS 1994: 819-830

Alok Aggarwal, Amotz Bar-Noy, Don Coppersmith, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan: Efficient Routing and Scheduling Algorithms for Optical Networks. SODA 1994: 412-423

Avrim Blum, Prasad Chalasani, Don Coppersmith, William R. Pulleyblank, Prabhakar Raghavan, Madhu Sudan: The minimum latency problem. STOC 1994: 163-171

Mihir Bellare, Madhu Sudan: Improved non-approximability results. STOC 1994: 184-193

Peter Gemmell, Madhu Sudan: Highly Resilient Correctors for Polynomials. Inf. Process. Lett. 43(4): 169-174 (1992)

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy: Proof Verification and Hardness of Approximation Problems. FOCS 1992: 14-23

Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan: Reconstructing Algebraic Functions from Mixed Data. FOCS 1992: 503-512

Ronitt Rubinfeld, Madhu Sudan: Self-Testing Polynomial Functions Efficiently and Over Rational Domains. SODA 1992: 23-32

Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson: Self-Testing/Correcting for Polynomials and for Approximate Functions. STOC 1991: 32-42

Marshall W. Bern, Daniel H. Greene, Arvind Raghunathan, Madhu Sudan: Online Algorithms for Locating Checkpoints. STOC 1990: 359-368