☰

Madhu Sudan - Publications

Affiliations: 
Computer Science Harvard University, Cambridge, MA, United States 
Tree Info Similar researchers PubMed Report error

61 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2020 Sudan M, Tyagi H, Watanabe S. Communication for Generating Correlation: A Unifying Survey Ieee Transactions On Information Theory. 66: 5-37. DOI: 10.1109/Tit.2019.2946364  0.317
2020 Bafna M, Srinivasan S, Sudan M. Local decoding and testing of polynomials over grids Random Structures and Algorithms. 57: 658-694. DOI: 10.1002/Rsa.20933  0.322
2018 Ghazi B, Komargodski I, Kothari PK, Sudan M. Communication with Contextual Uncertainty Computational Complexity. 27: 463-509. DOI: 10.1007/S00037-017-0161-3  0.342
2017 Gamarnik D, Sudan M. Limits of local algorithms over sparse random graphs Annals of Probability. 45: 2353-2376. DOI: 10.1214/16-Aop1114  0.377
2017 Gamarnik D, Sudan M. Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem Siam Journal On Computing. 46: 590-619. DOI: 10.1137/140989728  0.361
2017 Canonne CL, Guruswami V, Meka R, Sudan M. Communication With Imperfectly Shared Randomness Ieee Transactions On Information Theory. 63: 6799-6818. DOI: 10.1109/Tit.2017.2734103  0.57
2016 Haramaty E, Sudan M. Deterministic Compression with Uncertain Priors Algorithmica. 1-24. DOI: 10.1007/S00453-015-0107-6  0.369
2015 Ben-Sasson E, Ron-Zewi N, Sudan M. Sparse affine-invariant linear codes are locally testable Computational Complexity. DOI: 10.1007/S00037-015-0115-6  0.382
2013 Haramaty E, Ron-Zewi N, Sudan M. Absolutely Sound Testing of Lifted Codes Theory of Computing. 11: 299-338. DOI: 10.4086/Toc.2015.V011A012  0.408
2013 Ron-Zewi N, Sudan M. A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes. Theory of Computing. 9: 783-807. DOI: 10.4086/Toc.2013.V009A025  0.393
2013 Haramaty E, Shpilka A, Sudan M. Optimal testing of multivariate polynomials over small prime fields Siam Journal On Computing. 42: 536-562. DOI: 10.1137/120879257  0.324
2013 Dvir Z, Kopparty S, Saraf S, Sudan M. Extensions to the method of multiplicities, with applications to kakeya sets and mergers Siam Journal On Computing. 42: 2305-2328. DOI: 10.1137/100783704  0.355
2013 Grigorescu E, Kaufman T, Sudan M. 2-Transitivity is Insufficient for Local Testability Computational Complexity. 22: 137-158. DOI: 10.1007/S00037-012-0055-3  0.421
2012 Grigorescu E, Kaufman T, Sudan M. Succinct representation of codes with applications to testing Siam Journal On Discrete Mathematics. 26: 1618-1634. DOI: 10.1137/100818364  0.436
2011 Bhattacharyya AA, Chen V, Sudan M, Xie N. Testing Linear-Invariant Non-Linear Properties Theory of Computing. 7: 75-99. DOI: 10.4086/Toc.2011.V007A006  0.327
2011 Sudan M. Guest column: testing linear properties: some general theme Sigact News. 42: 59-80. DOI: 10.1145/1959045.1959062  0.405
2011 Aggarwal G, Fiat A, Goldberg AV, Hartline JD, Immorlica N, Sudan M. Derandomization of auctions Games and Economic Behavior. 72: 1-11. DOI: 10.1016/J.Geb.2010.07.007  0.304
2010 Ben-Sasson E, Guruswami V, Kaufman T, Sudan M, Viderman M. Locally testable codes require redundant testers Siam Journal On Computing. 39: 3230-3247. DOI: 10.1137/090779875  0.629
2010 Micali S, Peikert C, Sudan M, Wilson DA. Optimal error correction for computationally bounded noise Ieee Transactions On Information Theory. 56: 5673-5680. DOI: 10.1109/Tit.2010.2070370  0.367
2010 Bhattacharyya A, Chen V, Sudan M, Xie N. Testing linear-invariant non-linear properties: A short report Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6390: 260-268. DOI: 10.1007/978-3-642-16367-8_18  0.314
2010 Sudan M. Invariance in property testing Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6390: 211-227. DOI: 10.1007/978-3-642-16367-8_12  0.323
2009 Sudan M. Probabilistically checkable proofs Communications of the Acm. 52: 76-84. DOI: 10.1145/1467247.1467267  0.392
2009 Grigorescu E, Kaufman T, Sudan M. Succinct Representation of Codes with Applications to Testing Lecture Notes in Computer Science. 5687: 534. DOI: 10.1007/978-3-642-03685-9_40  0.349
2008 Saraf S, Sudan M. An improved lower bound on the size of Kakeya sets over finite fields Analysis & Pde. 1: 375-379. DOI: 10.2140/Apde.2008.1.375  0.334
2008 Eli BS, Sudan M. Short PCPS with polylog query complexity Siam Journal On Computing. 38: 551-607. DOI: 10.1137/050646445  0.443
2007 Alon N, Guruswami V, Kaufman T, Sudan M. Guessing secrets efficiently via list decoding Acm Transactions On Algorithms. 3. DOI: 10.1145/1290672.1290679  0.6
2006 Goldreich O, Sudan M. Locally testable codes and PCPs of almost-linear length Journal of the Acm. 53: 558-655. DOI: 10.1145/1162349.1162351  0.449
2006 Ben-Sasson ELI, Goldreich O, Harsha P, Sudan M, Vadhan S. Robust PCPs of proximity, shorter PCPs, and applications to coding Siam Journal On Computing. 36: 889-974. DOI: 10.1137/S0097539705446810  0.438
2006 Radhakrishnan J, Sudan M. On Dinur’s proof of the PCP theorem Bulletin of the American Mathematical Society. 44: 19-61. DOI: 10.1090/S0273-0979-06-01143-8  0.361
2006 Ben-Sasson E, Sudan M. Robust locally testable codes and products of codes Random Structures and Algorithms. 28: 387-402. DOI: 10.1002/Rsa.V28:4  0.316
2006 Engebretsen L, Sudan M. Harmonic broadcasting is bandwidth-optimal assuming constant bit rate Networks. 47: 172-177. DOI: 10.1002/Net.V47:3  0.365
2003 Sudan M. Mathematics. Quick and dirty refereeing? Science (New York, N.Y.). 301: 1191-2. PMID 12947187 DOI: 10.1126/Science.1086262  0.32
2003 Arora S, Sudan M. Improved low-degree testing and its applications Combinatorica. 23: 365-426. DOI: 10.1007/S00493-003-0025-0  0.599
2002 Guruswami V, Håstad J, Sudan M. Hardness of approximate hypergraph coloring Siam Journal On Computing. 31: 1663-1686. DOI: 10.1137/S0097539700377165  0.614
2002 Guruswami V, Håstad J, Sudan M, Zuckerman D. Combinatorial bounds for list decoding Ieee Transactions On Information Theory. 48: 1021-1034. DOI: 10.1109/18.995539  0.607
2001 Khanna S, Sudan M, Trevisan L, Williamson DP. The Approximability of Constraint Satisfaction Problems Siam Journal On Computing. 30: 1863-1920. DOI: 10.1137/S0097539799349948  0.358
2001 Guruswami V, Sudan M. On representations of algebraic-geometric codes Ieee Transactions On Information Theory. 47: 1610-1613. DOI: 10.1109/18.923745  0.623
2001 Sudan M. Ideal Error-Correcting Codes: Unifying Algebraic and Number-Theoretic Algorithms Applicable Algebra in Engineering, Communication and Computing. 36-45. DOI: 10.1007/3-540-45624-4_4  0.419
2001 Aumann Y, Håstad J, Rabin MO, Sudan M. Linear-consistency testing Journal of Computer and System Sciences. 62: 589-607. DOI: 10.1006/Jcss.2001.1747  0.357
2000 Sudan M. List decoding: algorithms and applications Sigact News. 31: 16-27. DOI: 10.1145/346048.346049  0.403
2000 Goldreich O, Rubinfeld R, Sudan M. Learning Polynomials with Queries: The Highly Noisy Case Siam Journal On Discrete Mathematics. 13: 535-570. DOI: 10.1137/S0895480198344540  0.401
2000 Trevisan L, Sorkin GB, Sudan M, Williamson DP. Gadgets, approximation, and linear programming Siam Journal On Computing. 29: 2074-2097. DOI: 10.1137/S0097539797328847  0.399
2000 Goldreich O, Ron D, Sudan M. Chinese remaindering with errors Ieee Transactions On Information Theory. 46: 1330-1338. DOI: 10.1109/18.850672  0.357
2000 Harsha P, Sudan M. Small PCPs with low query complexity Computational Complexity. 9: 157-201. DOI: 10.1007/Pl00001606  0.373
1999 Ar S, Lipton RJ, Rubinfeld R, Sudan M. Reconstructing Algebraic Functions from Mixed Data Siam Journal On Computing. 28: 487-510. DOI: 10.1137/S0097539796297577  0.371
1999 Khanna S, Motwani R, Sudan M, Vazirani U. On Syntactic versus Computational Views of Approximability Siam Journal On Computing. 28: 164-191. DOI: 10.1137/S0097539795286612  0.643
1999 Guruswami V, Sudan M. Improved decoding of reed-solomon and algebraic-geometry codes Ieee Transactions On Information Theory. 45: 1757-1767. DOI: 10.1109/18.782097  0.646
1999 Goldreich O, Sudan M. Computational indistinguishability: A sample hierarchy Journal of Computer and System Sciences. 59: 253-269. DOI: 10.1006/Jcss.1999.1652  0.309
1998 Arora S, Lund C, Motwani R, Sudan M, Szegedy M. Proof verification and the hardness of approximation problems Journal of the Acm. 45: 501-555. DOI: 10.1145/278298.278306  0.617
1998 Karger D, Motwani R, Sudan M. Approximate graph coloring by semidefinite programming Journal of the Acm. 45: 246-265. DOI: 10.1145/274787.274791  0.4
1998 Chor B, Sudan M. A Geometric Approach to Betweenness Siam Journal On Discrete Mathematics. 11: 511-523. DOI: 10.1137/S0895480195296221  0.388
1998 Bellare M, Goldreich O, Sudan M. Free Bits, PCPs, and Nonapproximability---Towards Tight Results Siam Journal On Computing. 27: 804-915. DOI: 10.1137/S0097539796302531  0.447
1998 Bar-Noy A, Mayer A, Schieber B, Sudan M. Guaranteeing Fair Service to Persistent Dependent Tasks Siam Journal On Computing. 27: 1168-1189. DOI: 10.1137/S0097539795282092  0.312
1998 Even G, Naor J, Schieber B, Sudan M. Approximating Minimum Feedback Sets and Multicuts in Directed Graphs Algorithmica. 20: 151-174. DOI: 10.1007/Pl00009191  0.414
1997 Sudan M. Decoding of Reed Solomon codes beyond the error-correction bound Journal of Complexity. 13: 180-193. DOI: 10.1006/Jcom.1997.0439  0.459
1996 Rubinfeld R, Sudan M. Robust Characterizations of Polynomials withApplications to Program Testing Siam Journal On Computing. 25: 252-271. DOI: 10.1137/S0097539793255151  0.393
1996 Bellare M, Coppersmith D, Hâstad J, Kiwi M, Sudan M. Linearity testing in characteristic two Ieee Transactions On Information Theory. 42: 1781-1795. DOI: 10.1109/18.556674  0.307
1996 Albanese A, Blömer J, Edmonds J, Luby M, Sudan M. Priority encoding transmission Ieee Transactions On Information Theory. 42: 1737-1744. DOI: 10.1109/18.556670  0.346
1994 Motwani R, Sudan M. Computing roots of graphs is hard Discrete Applied Mathematics. 54: 81-88. DOI: 10.1016/0166-218X(94)00023-9  0.307
1994 Bern M, Greene DH, Raghunathan A, Sudan M. On-line algorithms for locating checkpoints Algorithmica. 11: 33-52. DOI: 10.1007/Bf01294262  0.362
1992 Gemmell P, Sudan M. Highly resilient correctors for polynomials Information Processing Letters. 43: 169-174. DOI: 10.1016/0020-0190(92)90195-2  0.368
Show low-probability matches.