 | 2009 |
|---|
| 155 |       | Elena Grigorescu,
Tali Kaufman,
Madhu Sudan:
Succinct Representation of Codes with Applications to Testing.
APPROX-RANDOM 2009: 534-547 |
| 154 | | 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 |
| 153 | | Arnab Bhattacharyya,
Victor Chen,
Madhu Sudan,
Ning Xie:
Testing Linear-Invariant Non-Linear Properties.
STACS 2009: 135-146 |
| 152 | | Elena Grigorescu,
Tali Kaufman,
Madhu Sudan:
Succinct Representation of Codes with Applications to Testing
CoRR abs/0905.2919: (2009) |
| 151 | | Arnab Bhattacharyya,
Swastik Kopparty,
Grant Schoenebeck,
Madhu Sudan,
David Zuckerman:
Optimal Testing of Reed-Muller Codes
CoRR abs/0910.0641: (2009) |
| 150 | | Madhu Sudan:
Probabilistically checkable proofs.
Commun. ACM 52(3): 76-84 (2009) |
| 2008 |
|---|
| 149 | | Elena Grigorescu,
Tali Kaufman,
Madhu Sudan:
2-Transitivity Is Insufficient for Local Testability.
IEEE Conference on Computational Complexity 2008: 259-267 |
| 148 | | Madhu Sudan:
Algebraic algorithms and coding theory.
ISSAC 2008: 337 |
| 147 | | Brendan Juba,
Madhu Sudan:
Universal semantic communication I.
STOC 2008: 123-132 |
| 146 | | Irit Dinur,
Elena Grigorescu,
Swastik Kopparty,
Madhu Sudan:
Decodability of group homomorphisms beyond the johnson bound.
STOC 2008: 275-284 |
| 145 | | Tali Kaufman,
Madhu Sudan:
Algebraic property testing: the role of invariance.
STOC 2008: 403-412 |
| 144 | | 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) |
| 143 | | Elena Grigorescu,
Tali Kaufman,
Madhu Sudan:
2-Transitivity is Insufficient for Local Testability.
Electronic Colloquium on Computational Complexity (ECCC) 15(033): (2008) |
| 142 | | Arnab Bhattacharyya,
Victor Chen,
Madhu Sudan,
Ning Xie:
Testing Linear-Invariant Non-Linear Properties.
Electronic Colloquium on Computational Complexity (ECCC) 15(088): (2008) |
| 141 | | Brendan Juba,
Madhu Sudan:
Universal Semantic Communication II: A Theory of Goal-Oriented Communication.
Electronic Colloquium on Computational Complexity (ECCC) 15(095): (2008) |
| 140 | | Eli Ben-Sasson,
Madhu Sudan:
Short PCPs with Polylog Query Complexity.
SIAM J. Comput. 38(2): 551-607 (2008) |
| 2007 |
|---|
| 139 | | 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 |
| 138 | | Tali Kaufman,
Madhu Sudan:
Sparse Random Linear Codes are Locally Decodable and Testable.
FOCS 2007: 590-600 |
| 137 | | Noga Alon,
Venkatesan Guruswami,
Tali Kaufman,
Madhu Sudan:
Guessing secrets efficiently via list decoding.
ACM Transactions on Algorithms 3(4): (2007) |
| 136 | | Tali Kaufman,
Madhu Sudan:
Sparse Random Linear Codes are Locally Decodable and Testable.
Electronic Colloquium on Computational Complexity (ECCC) 14(060): (2007) |
| 135 | | Brendan Juba,
Madhu Sudan:
Universal Semantic Communication I.
Electronic Colloquium on Computational Complexity (ECCC) 14(084): (2007) |
| 134 | | Tali Kaufman,
Madhu Sudan:
Algebraic Property Testing: The Role of Invariance.
Electronic Colloquium on Computational Complexity (ECCC) 14(111): (2007) |
| 2006 |
|---|
| 133 | | Irit Dinur,
Madhu Sudan,
Avi Wigderson:
Robust Local Testability of Tensor Products of LDPC Codes.
APPROX-RANDOM 2006: 304-315 |
| 132 | | Elena Grigorescu,
Swastik Kopparty,
Madhu Sudan:
Local Decoding and Testing for Homomorphisms.
APPROX-RANDOM 2006: 375-385 |
| 131 | | Madhu Sudan:
Modelling Errors and Recovery for Communication.
LATIN 2006: 25-25 |
| 130 | | Ari Juels,
Madhu Sudan:
A Fuzzy Vault Scheme.
Des. Codes Cryptography 38(2): 237-257 (2006) |
| 129 | | Irit Dinur,
Madhu Sudan,
Avi Wigderson:
Robust Local Testability of Tensor Products of LDPC Codes.
Electronic Colloquium on Computational Complexity (ECCC) 13(118): (2006) |
| 128 | | Oded Goldreich,
Madhu Sudan:
Locally testable codes and PCPs of almost-linear length.
J. ACM 53(4): 558-655 (2006) |
| 127 | | Lars Engebretsen,
Madhu Sudan:
Harmonic broadcasting is bandwidth-optimal assuming constant bit rate.
Networks 47(3): 172-177 (2006) |
| 126 | | Eli Ben-Sasson,
Madhu Sudan:
Robust locally testable codes and products of codes.
Random Struct. Algorithms 28(4): 387-402 (2006) |
| 125 | | 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) |
| 124 |  | Oded Goldreich,
Madhu Sudan:
Special Issue on Randomness and Complexity.
SIAM J. Comput. 36(4): (2006) |
| 2005 |
|---|
| 123 | | Shafi Goldwasser,
Madhu Sudan,
Vinod Vaikuntanathan:
Distributed Computing with Imperfect Randomness.
DISC 2005: 288-302 |
| 122 | | 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 |
| 121 | | Eli Ben-Sasson,
Madhu Sudan:
Simple PCPs with poly-log rate and query complexity.
STOC 2005: 266-275 |
| 120 | | Gagan Aggarwal,
Amos Fiat,
Andrew V. Goldberg,
Jason D. Hartline,
Nicole Immorlica,
Madhu Sudan:
Derandomization of auctions.
STOC 2005: 619-625 |
| 119 | | Silvio Micali,
Chris Peikert,
Madhu Sudan,
David A. Wilson:
Optimal Error Correction Against Computationally Bounded Noise.
TCC 2005: 1-16 |
| 2004 |
|---|
| 118 | | Eli Ben-Sasson,
Madhu Sudan:
Robust Locally Testable Codes and Products of Codes.
APPROX-RANDOM 2004: 286-297 |
| 117 | | 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 |
| 116 | | Eli Ben-Sasson,
Madhu Sudan:
Robust Locally Testable Codes and Products of Codes
CoRR cs.IT/0408066: (2004) |
| 115 | | 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) |
| 114 | | Eli Ben-Sasson,
Madhu Sudan:
Robust Locally Testable Codes and Products of Codes
Electronic Colloquium on Computational Complexity (ECCC)(046): (2004) |
| 113 | | Eli Ben-Sasson,
Madhu Sudan:
Simple PCPs with Poly-log Rate and Query Complexity
Electronic Colloquium on Computational Complexity (ECCC)(060): (2004) |
| 112 | | Oded Goldreich,
Madhu Sudan,
Luca Trevisan:
From logarithmic advice to single-bit advice
Electronic Colloquium on Computational Complexity (ECCC)(093): (2004) |
| 2003 |
|---|
| 111 | | Eli Ben-Sasson,
Oded Goldreich,
Madhu Sudan:
Bounds on 2-Query Codeword Testing.
RANDOM-APPROX 2003: 216-227 |
| 110 | | Don Coppersmith,
Madhu Sudan:
Reconstructing curves in three (and higher) dimensional space from noisy data.
STOC 2003: 136-142 |
| 109 | | 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 |
| 108 | | Sanjeev Arora,
Madhu Sudan:
Improved Low-Degree Testing and its Applications.
Combinatorica 23(3): 365-426 (2003) |
| 107 | | Eli Ben-Sasson,
Oded Goldreich,
Madhu Sudan:
Bounds on 2-Query Codeword Testing.
Electronic Colloquium on Computational Complexity (ECCC) 10(019): (2003) |
| 106 | | 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) |
| 2002 |
|---|
| 105 | | Oded Goldreich,
Madhu Sudan:
Locally Testable Codes and PCPs of Almost-Linear Length.
FOCS 2002: 13-22 |
| 104 | | Venkatesan Guruswami,
Madhu Sudan:
Decoding Concatenated Codes using Soft Information.
IEEE Conference on Computational Complexity 2002: 148-157 |
| 103 | | Noga Alon,
Venkatesan Guruswami,
Tali Kaufman,
Madhu Sudan:
Guessing secrets efficiently via list decoding.
SODA 2002: 254-262 |
| 102 | | Lars Engebretsen,
Madhu Sudan:
Harmonic broadcasting is optimal.
SODA 2002: 431-432 |
| 101 | | Oded Goldreich,
Madhu Sudan:
Locally Testable Codes and PCPs of Almost-Linear Length
Electronic Colloquium on Computational Complexity (ECCC)(050): (2002) |
| 100 | | Venkatesan Guruswami,
Johan Håstad,
Madhu Sudan,
David Zuckerman:
Combinatorial bounds for list decoding.
IEEE Transactions on Information Theory 48(5): 1021-1034 (2002) |
| 99 | | Madhu Sudan:
Foreword.
J. Comput. Syst. Sci. 65(4): 611 (2002) |
| 98 | | Venkatesan Guruswami,
Johan Håstad,
Madhu Sudan:
Hardness of Approximate Hypergraph Coloring.
SIAM J. Comput. 31(6): 1663-1686 (2002) |
| 2001 |
|---|
| 97 | | Madhu Sudan:
Ideal Error-Correcting Codes: Unifying Algebraic and Number-Theoretic Algorithms.
AAECC 2001: 36-45 |
| 96 | | Madhu Sudan:
Coding Theory: Tutorial and Survey.
FOCS 2001: 36-53 |
| 95 | | Prahladh Harsha,
Madhu Sudan:
Small PCPs with Low Query Complexity.
STACS 2001: 327-338 |
| 94 | | Venkatesan Guruswami,
Madhu Sudan:
On representations of algebraic-geometry codes.
IEEE Transactions on Information Theory 47(4): 1610-1613 (2001) |
| 93 | | Allan Borodin,
Jon M. Kleinberg,
Prabhakar Raghavan,
Madhu Sudan,
David P. Williamson:
Adversarial queuing theory.
J. ACM 48(1): 13-38 (2001) |
| 92 | | Madhu Sudan,
Luca Trevisan,
Salil P. Vadhan:
Pseudorandom Generators without the XOR Lemma.
J. Comput. Syst. Sci. 62(2): 236-266 (2001) |
| 91 | | Yonatan Aumann,
Johan Håstad,
Michael O. Rabin,
Madhu Sudan:
Linear-Consistency Testing.
J. Comput. Syst. Sci. 62(4): 589-607 (2001) |
| 2000 |
|---|
| 90 | | Venkatesan Guruswami,
Madhu Sudan:
On Representations of Algebraic-Geometric Codes for List Decoding.
ESA 2000: 244-255 |
| 89 | | Venkatesan Guruswami,
Johan Håstad,
Madhu Sudan:
Hardness of Approximate Hypergraph Coloring.
FOCS 2000: 149-158 |
| 88 | | Venkatesan Guruswami,
Amit Sahai,
Madhu Sudan:
"Soft-decision" Decoding of Chinese Remainder Codes.
FOCS 2000: 159-168 |
| 87 | | Madhu Sudan:
List Decoding: Algorithms and Applications.
IFIP TCS 2000: 25-41 |
| 86 | | Venkatesan Guruswami,
Madhu Sudan:
List decoding algorithms for certain concatenated codes.
STOC 2000: 181-190 |
| 85 | | 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 |
| 84 | | Prahladh Harsha,
Madhu Sudan:
Small PCPs with low query complexity.
Computational Complexity 9(3-4): 157-201 (2000) |
| 83 | | Prahladh Harsha,
Madhu Sudan:
Small PCPs with low query complexity
Electronic Colloquium on Computational Complexity (ECCC) 7(61): (2000) |
| 82 | | Venkatesan Guruswami,
Johan Håstad,
Madhu Sudan:
Hardness of approximate hypergraph coloring
Electronic Colloquium on Computational Complexity (ECCC) 7(62): (2000) |
| 81 | | Oded Goldreich,
Dana Ron,
Madhu Sudan:
Chinese remaindering with errors.
IEEE Transactions on Information Theory 46(4): 1330-1338 (2000) |
| 80 | | Luca Trevisan,
Gregory B. Sorkin,
Madhu Sudan,
David P. Williamson:
Gadgets, Approximation, and Linear Programming.
SIAM J. Comput. 29(6): 2074-2097 (2000) |
| 79 | | Sanjeev Khanna,
Madhu Sudan,
Luca Trevisan,
David P. Williamson:
The Approximability of Constraint Satisfaction Problems.
SIAM J. Comput. 30(6): 1863-1920 (2000) |
| 78 | | Oded Goldreich,
Ronitt Rubinfeld,
Madhu Sudan:
Learning Polynomials with Queries: The Highly Noisy Case.
SIAM J. Discrete Math. 13(4): 535-570 (2000) |
| 77 | | Madhu Sudan:
List decoding: algorithms and applications.
SIGACT News 31(1): 16-27 (2000) |
| 1999 |
|---|
| 76 | | Ilya Dumer,
Daniele Micciancio,
Madhu Sudan:
Hardness of Approximating the Minimum Distance of a Linear Code.
FOCS 1999: 475-485 |
| 75 | | Madhu Sudan,
Luca Trevisan,
Salil P. Vadhan:
Pseudorandom Generators without the XOR Lemma (Abstract).
IEEE Conference on Computational Complexity 1999: 4 |
| 74 | | Yonatan Aumann,
Johan Håstad,
Michael O. Rabin,
Madhu Sudan:
Linear Consistency Testing.
RANDOM-APPROX 1999: 109-120 |
| 73 | | Oded Goldreich,
Dana Ron,
Madhu Sudan:
Chinese Remaindering with Errors.
STOC 1999: 225-234 |
| 72 | | Madhu Sudan,
Luca Trevisan,
Salil P. Vadhan:
Pseudorandom Generators Without the XOR Lemma (Extended Abstract).
STOC 1999: 537-546 |
| 71 | | Yonatan Aumann,
Johan Håstad,
Michael O. Rabin,
Madhu Sudan:
Linear Consistency Testing
Electronic Colloquium on Computational Complexity (ECCC) 6(25): (1999) |
| 70 | | 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) |
| 69 | | Venkatesan Guruswami,
Madhu Sudan:
Improved decoding of Reed-Solomon and algebraic-geometry codes.
IEEE Transactions on Information Theory 45(6): 1757-1767 (1999) |
| 68 | | Oded Goldreich,
Madhu Sudan:
Computational Indistinguishability: A Sample Hierarchy.
J. Comput. Syst. Sci. 59(2): 253-269 (1999) |
| 1998 |
|---|
| 67 | | Madhu Sudan,
Luca Trevisan:
Probabilistically Checkable Proofs with Low Amortized Query Complexity.
FOCS 1998: 18-27 |
| 66 | | Venkatesan Guruswami,
Madhu Sudan:
Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes.
FOCS 1998: 28-39 |
| 65 | | Venkatesan Guruswami,
Daniel Lewin,
Madhu Sudan,
Luca Trevisan:
A Tight Characterization of NP with 3 Query PCPs.
FOCS 1998: 8-17 |
| 64 | | Oded Goldreich,
Madhu Sudan:
Computational Indistinguishability: A Sample Hierarchy.
IEEE Conference on Computational Complexity 1998: 24-33 |
| 63 | | Guy Even,
Joseph Naor,
Baruch Schieber,
Madhu Sudan:
Approximating Minimum Feedback Sets and Multicuts in Directed Graphs.
Algorithmica 20(2): 151-174 (1998) |
| 62 | | David R. Karger,
Rajeev Motwani,
Madhu Sudan:
Approximate Graph Coloring by Semidefinite Programming
CoRR cs.DS/9812008: (1998) |
| 61 | | Oded Goldreich,
Madhu Sudan:
Computational Indistinguishability: A Sample Hierarchy
Electronic Colloquium on Computational Complexity (ECCC) 5(17): (1998) |
| 60 | | 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) |
| 59 | | Madhu Sudan,
Luca Trevisan:
Probabilistically checkable proofs with low amortized query complexity
Electronic Colloquium on Computational Complexity (ECCC) 5(40): (1998) |
| 58 | | Venkatesan Guruswami,
Madhu Sudan:
Improved decoding of Reed-Solomon and algebraic-geometric codes.
Electronic Colloquium on Computational Complexity (ECCC) 5(43): (1998) |
| 57 | | Oded Goldreich,
Ronitt Rubinfeld,
Madhu Sudan:
Learning Polynomials with Queries - The Highly Noisy Case.
Electronic Colloquium on Computational Complexity (ECCC) 5(60): (1998) |
| 56 | | Oded Goldreich,
Dana Ron,
Madhu Sudan:
Chinese Remaindering with Errors
Electronic Colloquium on Computational Complexity (ECCC) 5(62): (1998) |
| 55 | | Madhu Sudan,
Luca Trevisan,
Salil P. Vadhan:
Pseudorandom generators without the XOR Lemma
Electronic Colloquium on Computational Complexity (ECCC) 5(74): (1998) |
| 54 | | 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) |
| 53 | | David R. Karger,
Rajeev Motwani,
Madhu Sudan:
Approximate Graph Coloring by Semidefinite Programming.
J. ACM 45(2): 246-265 (1998) |
| 52 | | 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) |
| 51 | | Benny Chor,
Eyal Kushilevitz,
Oded Goldreich,
Madhu Sudan:
Private Information Retrieval.
J. ACM 45(6): 965-981 (1998) |
| 50 | | Mihir Bellare,
Oded Goldreich,
Madhu Sudan:
Free Bits, PCPs, and Nonapproximability-Towards Tight Results.
SIAM J. Comput. 27(3): 804-915 (1998) |
| 49 | | 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) |
| 48 | | Sanjeev Khanna,
Rajeev Motwani,
Madhu Sudan,
Umesh V. Vazirani:
On Syntactic versus Computational Views of Approximability.
SIAM J. Comput. 28(1): 164-191 (1998) |
| 47 | | Sigal Ar,
Richard J. Lipton,
Ronitt Rubinfeld,
Madhu Sudan:
Reconstructing Algebraic Functions from Mixed Data.
SIAM J. Comput. 28(2): 487-510 (1998) |
| 46 | | Benny Chor,
Madhu Sudan:
A Geometric Approach to Betweenness.
SIAM J. Discrete Math. 11(4): 511-523 (1998) |
| 1997 |
|---|
| 45 | | Madhu Sudan:
Algorithmic Issues in Coding Theory.
FSTTCS 1997: 184-199 |
| 44 | | Nachum Shacham,
Madhu Sudan,
Michael Brown:
Conducting a Multiparty Multimedia Session over ATM using Hierarchically Encoded Data.
ICC (2) 1997: 811-815 |
| 43 | | Sanjeev Khanna,
Madhu Sudan,
Luca Trevisan:
Constraint Satisfaction: The Approximability of Minimization Problems.
IEEE Conference on Computational Complexity 1997: 282-296 |
| 42 | | Madhu Sudan,
Nachum Shacham:
Gateway Based Approach for Conducting Multiparty Multimedia Sessions over Heterogeneous Signaling Domains.
INFOCOM 1997: 701-710 |
| 41 | | 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 |
| 40 | | Sanjeev Arora,
Madhu Sudan:
Improved Low-Degree Testing and its Applications.
STOC 1997: 485-495 |
| 39 | | Sanjeev Arora,
Madhu Sudan:
Improved low-degree testing and its applications
Electronic Colloquium on Computational Complexity (ECCC) 4(3): (1997) |
| 38 | | Madhu Sudan:
Decoding of Reed Solomon Codes beyond the Error-Correction Bound.
J. Complexity 13(1): 180-193 (1997) |
| 1996 |
|---|
| 37 | | Madhu Sudan:
Maximum Likelihood Decoding of Reed Solomon Codes.
FOCS 1996: 164-172 |
| 36 | | Luca Trevisan,
Gregory B. Sorkin,
Madhu Sudan,
David P. Williamson:
Gadgets, Approximation, and Linear Programming (extended abstract).
FOCS 1996: 617-626 |
| 35 | | Allan Borodin,
Jon M. Kleinberg,
Prabhakar Raghavan,
Madhu Sudan,
David P. Williamson:
Adversarial Queueing Theory.
STOC 1996: 376-385 |
| 34 | | Sanjeev Khanna,
Madhu Sudan:
The Optimization Complexity of Constraint Satisfaction Problems
Electronic Colloquium on Computational Complexity (ECCC) 3(28): (1996) |
| 33 | | 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) |
| 32 | | Sanjeev Khanna,
Madhu Sudan,
Luca Trevisan:
Constraint satisfaction: The approximability of minimization problems.
Electronic Colloquium on Computational Complexity (ECCC) 3(64): (1996) |
| 31 | | Andres Albanese,
Johannes Blömer,
Jeff Edmonds,
Michael Luby,
Madhu Sudan:
Priority encoding transmission.
IEEE Transactions on Information Theory 42(6): 1737-1744 (1996) |
| 30 | | 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) |
| 29 | | 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) |
| 28 | | Ronitt Rubinfeld,
Madhu Sudan:
Robust Characterizations of Polynomials with Applications to Program Testing.
SIAM J. Comput. 25(2): 252-271 (1996) |
| 1995 |
|---|
| 27 | | Madhu Sudan:
Efficient Checking of Polynomials and Proofs anf the Hardness of Approximation Problems
Springer 1995 |
| 26 | | Rajendra Yavatkar,
Jim Griffioen,
Madhu Sudan:
A Reliable Dissemination Protocol for Interactive Collaborative Applications.
ACM Multimedia 1995: 333-344 |
| 25 | | Benny Chor,
Madhu Sudan:
A Geometric Approach to Betweenness.
ESA 1995: 227-237 |
| 24 | | Oded Goldreich,
Ronitt Rubinfeld,
Madhu Sudan:
Learning Polynomials with Queries: The Highly Noisy Case.
FOCS 1995: 294-303 |
| 23 | | Benny Chor,
Oded Goldreich,
Eyal Kushilevitz,
Madhu Sudan:
Private Information Retrieval.
FOCS 1995: 41-50 |
| 22 | | Mihir Bellare,
Oded Goldreich,
Madhu Sudan:
Free Bits, PCPs and Non-Approximability - Towards Tight Results.
FOCS 1995: 422-431 |
| 21 | | Mihir Bellare,
Don Coppersmith,
Johan Håstad,
Marcos A. Kiwi,
Madhu Sudan:
Linearity Testing in Characteristic Two.
FOCS 1995: 432-441 |
| 20 | | Guy Even,
Joseph Naor,
Baruch Schieber,
Madhu Sudan:
Approximating Minimum Feedback Sets and Multi-Cuts in Directed Graphs.
IPCO 1995: 14-28 |
| 19 | | Katalin Friedl,
Madhu Sudan:
Some Improvements to Total Degree Tests.
ISTCS 1995: 190-198 |
| 18 | | Amotz Bar-Noy,
Alain J. Mayer,
Baruch Schieber,
Madhu Sudan:
Guaranteeing Fair Service to Persistent Dependent Tasks.
SODA 1995: 243-252 |
| 17 | | 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) |
| 16 | | Mihir Bellare,
Oded Goldreich,
Madhu Sudan:
Free Bits, PCP and Non-Approximability - Towards Tight Results
Electronic Colloquium on Computational Complexity (ECCC) 2(24): (1995) |
| 1994 |
|---|
| 15 | | David R. Karger,
Rajeev Motwani,
Madhu Sudan:
Approximate Graph Coloring by Semidefinite Programming
FOCS 1994: 2-13 |
| 14 | | Christos H. Papadimitriou,
Prabhakar Raghavan,
Madhu Sudan,
Hisao Tamaki:
Motion Planning on a Graph (Extended Abstract)
FOCS 1994: 511-520 |
| 13 | | Andres Albanese,
Johannes Blömer,
Jeff Edmonds,
Michael Luby,
Madhu Sudan:
Priority Encoding Transmission
FOCS 1994: 604-612 |
| 12 | | Sanjeev Khanna,
Rajeev Motwani,
Madhu Sudan,
Umesh V. Vazirani:
On Syntactic versus Computational Views of Approximability
FOCS 1994: 819-830 |
| 11 | | 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 |
| 10 | | Avrim Blum,
Prasad Chalasani,
Don Coppersmith,
William R. Pulleyblank,
Prabhakar Raghavan,
Madhu Sudan:
The minimum latency problem.
STOC 1994: 163-171 |
| 9 | | Mihir Bellare,
Madhu Sudan:
Improved non-approximability results.
STOC 1994: 184-193 |
| 8 | | Marshall W. Bern,
Daniel H. Greene,
Arvind Raghunathan,
Madhu Sudan:
On-Line Algorithms for Locating Checkpoints.
Algorithmica 11(1): 33-52 (1994) |
| 7 | | Rajeev Motwani,
Madhu Sudan:
Computing Roots of Graphs Is Hard.
Discrete Applied Mathematics 54(1): 81-88 (1994) |
| 1992 |
|---|
| 6 | | Sanjeev Arora,
Carsten Lund,
Rajeev Motwani,
Madhu Sudan,
Mario Szegedy:
Proof Verification and Hardness of Approximation Problems
FOCS 1992: 14-23 |
| 5 | | Sigal Ar,
Richard J. Lipton,
Ronitt Rubinfeld,
Madhu Sudan:
Reconstructing Algebraic Functions from Mixed Data
FOCS 1992: 503-512 |
| 4 | | Ronitt Rubinfeld,
Madhu Sudan:
Self-Testing Polynomial Functions Efficiently and Over Rational Domains.
SODA 1992: 23-32 |
| 3 | | Peter Gemmell,
Madhu Sudan:
Highly Resilient Correctors for Polynomials.
Inf. Process. Lett. 43(4): 169-174 (1992) |
| 1991 |
|---|
| 2 | | Peter Gemmell,
Richard J. Lipton,
Ronitt Rubinfeld,
Madhu Sudan,
Avi Wigderson:
Self-Testing/Correcting for Polynomials and for Approximate Functions
STOC 1991: 32-42 |
| 1990 |
|---|
| 1 | | Marshall W. Bern,
Daniel H. Greene,
Arvind Raghunathan,
Madhu Sudan:
Online Algorithms for Locating Checkpoints
STOC 1990: 359-368 |
