Edit Profile (opens in new tab) Sudan, Madhu Co-Author Distance Author ID: sudan.madhu Published as: Sudan, Madhu; Sudan, M. Homepage: http://madhu.seas.harvard.edu/ External Links: MGP · Wikidata · dblp · GND · IdRef Awards: Nevanlinna Prize (2002) Documents Indexed: 162 Publications since 1992, including 2 Books and 8 Additional arXiv Preprints 4 Contributions as Editor · 1 Further Contribution Biographic References: 3 Publications Co-Authors: 133 Co-Authors with 156 Joint Publications 3,809 Co-Co-Authors all top 5 Co-Authors 10 single-authored 21 Goldreich, Oded 16 Guruswami, Venkatesan 12 Ben-Sasson, Eli 9 Vadhan, Salil P. 8 Grigorescu, Elena 8 Haramaty, Elad 8 Kaufman, Tali 8 Khanna, Sanjeev 8 Rubinfeld, Ronitt 7 Ghazi, Badih 7 Kopparty, Swastik 7 Trevisan, Luca 6 Bellare, Mihir 6 Coppersmith, Don 6 Harsha, Prahladh 6 Håstad, Johan Torkel 6 Schieber, Baruch 5 Motwani, Rajeev 5 Raghavan, Prabhakar 5 Ron-Zewi, Noga 5 Williamson, David P. 4 Arora, Sanjeev 4 Bar-Noy, Amotz 4 Bhattacharyya, Arnab 4 Chor, Benny 4 Gamarnik, David 4 Kleinberg, Jon Michael 4 Saraf, Shubhangi 3 Bafna, Mitali 3 Błasiok, Jarosław 3 Chen, Victor C. 3 Kamath, Pritish 3 Kapralov, Michael 3 Mossel, Elchanan 3 Nakkiran, Preetum 3 Ron, Dana 3 Shpilka, Amir 3 Velingker, Ameya 3 Velusamy, Santhoshini 3 Wigderson, Avi 3 Xie, Ning 3 Zuckerman, David 2 Aggarwal, Alok 2 Aggarwal, Gagan 2 Alon, Noga 2 Ar, Sigal 2 Aumann, Yonatan 2 Ben-Eliezer, Omri 2 Bhandari, Siddharth 2 Borodin, Allan B. 2 Bürgisser, Peter 2 Canonne, Clement Louis 2 Dinur, Irit 2 Dvir, Zeev 2 Engebretsen, Lars 2 Even, Guy 2 Fagin, Ronald 2 Fiat, Amos 2 Goldberg, Andrew V. 2 Goldwasser, Shafi 2 Golowich, Noah 2 Guo, Alan 2 Haeupler, Bernhard 2 Hartline, Jason D. 2 Immorlica, Nicole 2 Juba, Brendan 2 Karlin, Anna R. 2 Kiwi, Marcos A. 2 Komargodski, Ilan 2 Kothari, Pravesh K. 2 Kumar, Mrinal 2 Kushilevitz, Eyal 2 Lipton, Richard Jay 2 Lund, Carsten 2 Mayer, Alain J. 2 Meka, Raghu 2 Micali, Silvio 2 Naor, Joseph Seffi 2 Peikert, Chris 2 Rabin, Michael O. 2 Rajagopalan, Sridhar 2 Ramaswami, Rajiv 2 Rivest, Ronald Linn 2 Rudra, Atri 2 Singer, Noah 2 Srinivasan, Srikanth 2 Szegedy, Mario 2 Tomkins, Andrew 2 von zur Gathen, Joachim 2 Wilson, David A. 2 Zhu, Minshen 1 Albanese, Andres 1 Avigad, Lidor 1 Bavarian, Mohammad 1 Bern, Marshall W. 1 Blömer, Johannes 1 Blum, Avrim L. 1 Brakerski, Zvika 1 Brandenberger, Anna M. 1 Canetti, Ran ...and 38 more Co-Authors all top 5 Serials 14 SIAM Journal on Computing 11 IEEE Transactions on Information Theory 8 Journal of the ACM 4 Computational Complexity 4 Oberwolfach Reports 4 Theory of Computing 3 Journal of Computer and System Sciences 3 Algorithmica 3 SIAM Journal on Discrete Mathematics 2 Random Structures & Algorithms 2 The Annals of Applied Probability 2 Lecture Notes in Computer Science 1 Discrete Applied Mathematics 1 Information Processing Letters 1 The Annals of Probability 1 Networks 1 Combinatorica 1 Journal of Complexity 1 Designs, Codes and Cryptography 1 Games and Economic Behavior 1 Bulletin of the American Mathematical Society. New Series 1 Journal of Algebraic Combinatorics 1 Documenta Mathematica 1 SIAM Monographs on Discrete Mathematics and Applications 1 Science 1 Analysis & PDE 1 ACM Transactions on Algorithms all top 5 Fields 122 Computer science (68-XX) 68 Information and communication theory, circuits (94-XX) 12 Combinatorics (05-XX) 10 Operations research, mathematical programming (90-XX) 9 Number theory (11-XX) 8 Probability theory and stochastic processes (60-XX) 5 General and overarching topics; collections (00-XX) 5 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 3 Numerical analysis (65-XX) 3 Statistical mechanics, structure of matter (82-XX) 2 Mathematical logic and foundations (03-XX) 2 Harmonic analysis on Euclidean spaces (42-XX) 2 Statistics (62-XX) 1 Field theory and polynomials (12-XX) 1 Geometry (51-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 129 Publications have been cited 2,976 times in 2,010 Documents Cited by ▼ Year ▼ Proof verification and the hardness of approximation problems. Zbl 1065.68570 Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario 279 1998 Robust characterizations of polynomials with applications to program testing. Zbl 0844.68062 Rubinfeld, Ronitt; Sudan, Madhu 200 1996 Proof verification and hardness of approximation problems. Zbl 0977.68539 Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario 177 1992 Complexity classifications of Boolean constraint satisfaction problems. Zbl 0981.68058 Creignou, Nadia; Khanna, Sanjeev; Sudan, Madhu 128 2001 Improved decoding of Reed-Solomon and algebraic-geometry codes. Zbl 0958.94036 Guruswami, Venkatesan; Sudan, Madhu 117 1999 Approximate graph coloring by semidefinite programming. Zbl 0904.68116 Karger, David; Motwani, Rajeev; Sudan, Madhu 98 1998 Free bits, PCPs, and nonapproximability – towards tight results. Zbl 0912.68041 Bellare, Mihir; Goldreich, Oded; Sudan, Madhu 91 1998 Decoding of Reed Solomon codes beyond the error-correction bound. Zbl 0872.68026 Sudan, Madhu 90 1997 Private information retrieval. Zbl 1065.68524 Chor, Benny; Goldreich, Oded; Kushilevitz, Eyal; Sudan, Madhu 85 1998 Robust PCPs of proximity, shorter PCPs, and applications to coding. Zbl 1118.68071 Ben-Sasson, Eli; Goldreich, Oded; Harsha, Prahladh; Sudan, Madhu; Vadhan, Salil 80 2006 Private information retrieval. Zbl 0938.68625 Chor, Benny; Goldreich, Oded; Kushilevitz, Eyal; Sudan, Madhu 75 1995 The minimum latency problem. Zbl 1345.90073 Blum, Avrim; Chalasani, Prasad; Coppersmith, Don; Pulleyblank, Bill; Raghavan, Prabhakar; Sudan, Madhu 68 1994 On syntactic versus computational views of approximability. Zbl 0915.68068 Khanna, Sanjeev; Motwani, Rajeev; Sudan, Madhu; Vazirani, Umesh 65 1998 Approximating minimum feedback sets and multicuts in directed graphs. Zbl 0897.68078 Even, G.; Naor, J.; Schieber, B.; Sudan, M. 59 1998 The approximability of constraint satisfaction problems. Zbl 0992.68059 Khanna, Sanjeev; Sudan, Madhu; Trevisan, Luca; Williamson, David P. 54 2001 Pseudorandom generators without the XOR lemma. Zbl 1005.65006 Sudan, Madhu; Trevisan, Luca; Vadhan, Salil 54 2001 A theory of goal-oriented communication. Zbl 1281.94004 Goldreich, Oded; Juba, Brendan; Sudan, Madhu 48 2012 Gadgets, approximation, and linear programming. Zbl 0957.68048 Trevisan, Luca; Sorkin, Gregory B.; Sudan, Madhu; Williamson, David P. 46 2000 Locally testable codes and PCPs of almost-linear length. Zbl 1315.94144 Goldreich, Oded; Sudan, Madhu 46 2006 Adversarial queuing theory. Zbl 1320.68053 Borodin, Allan; Kleinberg, Jon; Raghavan, Prabhakar; Sudan, Madhu; Williamson, David P. 46 2001 Short PCPs with polylog query complexity. Zbl 1172.68025 Ben-Sasson, Eli; Sudan, Madhu 42 2009 Linearity testing in characteristic two. Zbl 0867.68060 Bellare, Mihir; Coppersmith, Don; Håstad, Johan; Kiwi, Marcos; Sudan, Madhu 39 1996 Algebraic property testing: the role of invariance. Zbl 1231.68290 Kaufman, Tali; Sudan, Madhu 38 2008 Improved low-degree testing and its applications. Zbl 1101.68572 Arora, Sanjeev; Sudan, Madhu 34 2003 Computing roots of graphs is hard. Zbl 0812.68103 Motwani, Rajeev; Sudan, Madhu 34 1994 Extensions to the method of multiplicities, with applications to Kakeya sets and mergers. Zbl 1285.68116 Dvir, Zeev; Kopparty, Swastik; Saraf, Shubhangi; Sudan, Madhu 31 2013 Limits of local algorithms over sparse random graphs (extended abstract). Zbl 1365.05277 Gamarnik, David; Sudan, Madhu 30 2014 Improved non-approximability results. Zbl 1344.68094 Bellare, Mihir; Sudan, Madhu 29 1994 A fuzzy vault scheme. Zbl 1172.94578 Juels, Ari; Sudan, Madhu 26 2006 Highly resilient correctors for polynomials. Zbl 0767.68075 Gemmell, Peter; Sudan, Madhu 26 1992 Extensions to the method of multiplicities, with applications to Kakeya sets and mergers. Zbl 1292.68119 Dvir, Zeev; Kopparty, Swastik; Saraf, Shubhangi; Sudan, Madhu 26 2009 An improved lower bound on the size of Kakeya sets over finite fields. Zbl 1335.42017 Saraf, Shubhangi; Sudan, Madhu 25 2008 Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. Zbl 1192.94089 Ben-Sasson, Eli; Sudan, Madhu; Vadhan, Salil; Wigderson, Avi 25 2003 Free bits, PCPs and non-approximability – towards tight results. Zbl 0938.68820 Bellare, Mihir; Goldreich, Oded; Sudan, Madhu 22 1995 Hardness of approximating the minimum distance of a linear code. Zbl 1063.68055 Dumer, Ilya; Micciancio, Daniele; Sudan, Madhu 22 2003 A geometric approach to betweenness. Zbl 0912.68058 Chor, Benny; Sudan, Madhu 21 1998 Optimal testing of Reed-Muller codes. Zbl 1310.68227 Bhattacharyya, Arnab; Kopparty, Swastik; Schoenebeck, Grant; Sudan, Madhu; Zuckerman, David 20 2010 Improved low degree testing and its applications. Zbl 0968.68145 Arora, Sanjeev; Sudan, Madhu 19 1999 Robust locally testable codes and products of codes. Zbl 1103.90080 Ben-Sasson, Eli; Sudan, Madhu 19 2006 New affine-invariant codes from lifting. Zbl 1364.94606 Guo, Alan; Kopparty, Swastik; Sudan, Madhu 18 2013 Chinese remaindering with errors. Zbl 1007.94026 Goldreich, Oded; Ron, Dana; Sudan, Madhu 17 2000 Learning polynomials with queries: The highly noisy case. Zbl 0968.68063 Goldreich, Oded; Rubinfeld, Ronitt; Sudan, Madhu 16 2000 Limits of local algorithms over sparse random graphs. Zbl 1371.05265 Gamarnik, David; Sudan, Madhu 16 2017 Hardness of approximate hypergraph coloring. Zbl 1008.68052 Guruswami, Venkatesan; Hastad, Johan; Sudan, Madhu 16 2002 Optimal error rates for interactive coding. I: Adaptivity and other settings. Zbl 1315.94122 Ghaffari, Mohsen; Haeupler, Bernhard; Sudan, Madhu 15 2014 Efficient routing and scheduling algorithms for optical networks. Zbl 0874.68018 Aggarwal, Alok; Bar-Noy, Amotz; Coppersmith, Don; Ramaswami, Rajiv; Schieber, Baruch; Sudan, Madhu 14 1994 A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction. Zbl 0962.68068 Khanna, Sanjeev; Sudan, Madhu; Williamson, David P. 13 1999 Performance of sequential local algorithms for the random NAE-\(K\)-SAT problem. Zbl 1388.60037 Gamarnik, David; Sudan, Madhu 13 2017 Pseudorandom generators without the XOR lemma (extended abstract). Zbl 1345.68138 Sudan, Madhu; Trevisan, Luca; Vadhan, Salil 13 1999 Approximating matching size from random streams. Zbl 1423.68344 Kapralov, Michael; Khanna, Sanjeev; Sudan, Madhu 13 2014 Self-testing polynomial functions efficiently and over rational domains. Zbl 0834.68076 Rubinfeld, Ronitt; Sudan, Madhu 12 1992 Derandomization of auctions. Zbl 1192.91095 Aggarwal, Gagan; Fiat, Amos; Goldberg, Andrew V.; Hartline, Jason D.; Immorlica, Nicole; Sudan, Madhu 12 2005 Robust local testability of tensor products of LDPC codes. Zbl 1155.94402 Dinur, Irit; Sudan, Madhu; Wigderson, Avi 11 2006 Efficient checking of polynomials and proofs and the hardness of approximation problems. Zbl 0861.68042 Sudan, Madhu 11 1995 Simple PCPs with poly-log rate and query complexity. Zbl 1192.68287 Ben-Sasson, Eli; Sudan, Madhu 11 2005 Learning polynomials with queries: The highly noisy case. Zbl 0938.68642 Goldreich, Oded; Rubinfeld, Ronitt; Sudan, Madhu 10 1995 Amplifying collision resistance: a complexity-theoretic treatment. Zbl 1215.94036 Canetti, Ran; Rivest, Ron; Sudan, Madhu; Trevisan, Luca; Vadhan, Salil; Wee, Hoeteck 10 2007 Priority encoding transmission. Zbl 0867.94038 Albanese, Andres; Blömer, Johannes; Edmonds, Jeff; Luby, Michael; Sudan, Madhu 10 1996 List decoding algorithms for certain concatenated codes. Zbl 1296.94170 Guruswami, Venkatesan; Sudan, Madhu 10 2000 Combinatorial bounds for list decoding. Zbl 1061.94074 Guruswami, Venkatesan; Håstad, Johan; Sudan, Madhu; Zuckerman, David 9 2002 2-transitivity is insufficient for local testability. Zbl 1283.94130 Grigorescu, Elena; Kaufman, Tali; Sudan, Madhu 9 2013 Locally testable codes require redundant testers. Zbl 1209.68265 Ben-Sasson, Eli; Guruswami, Venkatesan; Kaufman, Tali; Sudan, Madhu; Viderman, Michael 8 2010 Kakeya-type sets in finite vector spaces. Zbl 1230.42027 Kopparty, Swastik; Lev, Vsevolod F.; Saraf, Shubhangi; Sudan, Madhu 8 2011 Small PCPs with low query complexity. Zbl 0986.68134 Harsha, Prahladh; Sudan, Madhu 8 2000 Succinct representation of codes with applications to testing. Zbl 1255.94082 Grigorescu, Elena; Kaufman, Tali; Sudan, Madhu 8 2009 Optimal error correction against computationally bounded noise. Zbl 1079.94565 Micali, Silvio; Peikert, Chris; Sudan, Madhu; Wilson, David A. 8 2005 Efficient routing in optical networks. Zbl 0885.68083 Aggarwal, Alok; Bar-Noy, Amotz; Coppersmith, Don; Ramaswami, Rajiv; Schieber, Baruch; Sudan, Madhu 8 1996 On sums of locally testable affine invariant properties. Zbl 1343.68287 Ben-Sasson, Eli; Grigorescu, Elena; Maatouk, Ghid; Shpilka, Amir; Sudan, Madhu 7 2011 Limits on the rate of locally testable affine-invariant codes. Zbl 1343.68288 Ben-Sasson, Eli; Sudan, Madhu 7 2011 Reconstructing algebraic functions from mixed data. Zbl 0915.68088 Ar, Sigal; Lipton, Richard J.; Rubinfeld, Ronitt; Sudan, Madhu 7 1998 List decoding: Algorithms and applications. Zbl 1009.94572 Sudan, Madhu 7 2000 Linearity testing in characteristic two. Zbl 0938.68926 Bellare, M.; Coppersmith, D.; Håstad, J.; Kiwi, M.; Sudan, M. 7 1995 Ideal error-correcting codes: Unifying algebraic and number-theoretic algorithms. Zbl 1057.94516 Sudan, Madhu 7 2001 Guessing secrets efficiently via list decoding. Zbl 1058.94023 Alon, Noga; Guruswami, Venkatesan; Kaufman, Tali; Sudan, Madhu 7 2002 Streaming lower bounds for approximating max-cut. Zbl 1371.68213 Kapralov, Michael; Khanna, Sanjeev; Sudan, Madhu 7 2015 Invariance in property testing. Zbl 1309.68055 Sudan, Madhu 7 2010 Bounds on \(2\)-query codeword testing. Zbl 1279.94142 Ben-Sasson, Eli; Goldreich, Oded; Sudan, Madhu 6 2003 Distributed computing with imperfect randomness. Zbl 1171.68860 Goldwasser, Shafi; Sudan, Madhu; Vaikuntanathan, Vinod 6 2005 Testing linear-invariant non-linear properties. Zbl 1246.68259 Bhattacharyya, Arnab; Chen, Victor; Sudan, Madhu; Xie, Ning 6 2011 On representations of algebraic-geometry codes. Zbl 1002.94041 Guruswami, Venkatesan; Sudan, Madhu 6 2001 Robust PSPs of proximity, shorter PSPs and applications to coding. Zbl 1192.68286 Ben-Sasson, Eli; Goldreich, Oded; Harsha, Prahladh; Sudan, Madhu; Vadhan, Salil 6 2004 Chinese remaindering with errors. Zbl 1345.94105 Goldreich, Oded; Ron, Dana; Sudan, Madhu 6 1999 On Dinur’s proof of the PCP theorem. Zbl 1112.68117 Radhakrishnan, Jaikumar; Sudan, Madhu 5 2007 Testing linear-invariant non-linear properties. Zbl 1236.68289 Bhattacharyya, Arnab; Chen, Victor; Sudan, Madhu; Xie, Ning 5 2009 Harmonic broadcasting is bandwidth-optimal assuming constant bit rate. Zbl 1093.94018 Engebretsen, Lars; Sudan, Madhu 5 2006 Communication for generating correlation: a unifying survey. Zbl 1433.94107 Sudan, Madhu; Tyagi, Himanshu; Watanabe, Shun 5 2020 \((1 + \Omega(1))\)-approximation to MAX-CUT requires linear space. Zbl 1410.68169 Kapralov, Michael; Khanna, Sanjeev; Sudan, Madhu; Velingker, Ameya 5 2017 Adversarial queueing theory. Zbl 0934.60079 Borodin, Allan; Kleinberg, Jon; Raghavan, Prabhakar; Sudan, Madhu; Williamson, David P. 4 1996 Probabilistically checkable proofs. Zbl 1161.68021 Sudan, Madhu 4 2004 Queuing with future information. Zbl 1309.60090 Spencer, Joel; Sudan, Madhu; Xu, Kuang 4 2014 Random walks with “back buttons”. Zbl 1021.60031 Fagin, Ronald; Karlin, Anna R.; Kleinberg, Jon; Raghavan, Prabhakar; Rajagopalan, Sridhar; Rubinfeld, Ronitt; Sudan, Madhu; Tomkins, Andrew 4 2001 Derandomization of auctions. Zbl 1236.91072 Aggarwal, Gagan; Fiat, Amos; Goldberg, Andrew V.; Hartline, Jason D.; Immorlica, Nicole; Sudan, Madhu 3 2011 Guaranteeing fair service to persistent dependent tasks. Zbl 0910.90174 Bar-Noy, Amotz; Mayer, Alain; Schieber, Baruch; Sudan, Madhu 3 1998 Robust locally testable codes and products of codes. Zbl 1105.68346 Ben-Sasson, Eli; Sudan, Madhu 3 2004 Linear-consistency testing. Zbl 1052.68122 Aumann, Yonatan; Håstad, Johan; Rabin, Michael O.; Sudan, Madhu 3 2001 Reconsructing algebraic functions from mixed data. Zbl 0925.68221 Ar, Sigal; Lipton, Richard J.; Rubinfeld, Ronitt; Sudan, Madhu 3 1992 Universal semantic communication. Zbl 1231.68244 Juba, Brendan; Sudan, Madhu 3 2008 Decodability of group homomorphisms beyond the Johnson bound. Zbl 1231.94061 Dinur, Irit; Grigorescu, Elena; Kopparty, Swastik; Sudan, Madhu 3 2008 On-line algorithms for locating checkpoints. Zbl 0784.68031 Bern, Marshall; Greene, Daniel H.; Raghunathan, Arvind; Sudan, Madhu 3 1994 Random walks with “back buttons” (extended abstract). Zbl 1296.60191 Fagin, Ronald; Karlin, Anna R.; Kleinberg, Jon; Raghavan, Prabhakar; Rajagopalan, Sridhar; Rubinfeld, Ronitt; Sudan, Madhu; Tomkins, Andrew 3 2000 Decoding multivariate multiplicity codes on product sets. Zbl 07765264 Bhandari, Siddharth; Harsha, Prahladh; Kumar, Mrinal; Sudan, Madhu 1 2021 Communication for generating correlation: a unifying survey. Zbl 1433.94107 Sudan, Madhu; Tyagi, Himanshu; Watanabe, Shun 5 2020 Algorithmic polarization for hidden Markov models. Zbl 07559082 Guruswami, Venkatesan; Nakkiran, Preetum; Sudan, Madhu 2 2019 Synchronization strings: list decoding for insertions and deletions. Zbl 1512.94171 Haeupler, Bernhard; Shahrasbi, Amirbehshad; Sudan, Madhu 3 2018 Polar codes with exponentially small error at finite block length. Zbl 1527.94084 Błasiok, Jarosław; Guruswami, Venkatesan; Sudan, Madhu 2 2018 General strong polarization. Zbl 1427.94089 Błasiok, Jarosław; Guruswami, Venkatesan; Nakkiran, Preetum; Rudra, Atri; Sudan, Madhu 2 2018 Limits of local algorithms over sparse random graphs. Zbl 1371.05265 Gamarnik, David; Sudan, Madhu 16 2017 Performance of sequential local algorithms for the random NAE-\(K\)-SAT problem. Zbl 1388.60037 Gamarnik, David; Sudan, Madhu 13 2017 \((1 + \Omega(1))\)-approximation to MAX-CUT requires linear space. Zbl 1410.68169 Kapralov, Michael; Khanna, Sanjeev; Sudan, Madhu; Velingker, Ameya 5 2017 Sparse affine-invariant linear codes are locally testable. Zbl 1381.94114 Ben-Sasson, Eli; Ron-Zewi, Noga; Sudan, Madhu 1 2017 Deterministic compression with uncertain priors. Zbl 1353.68075 Haramaty, Elad; Sudan, Madhu 1 2016 Communication complexity of permutation-invariant functions. Zbl 1410.68129 Ghazi, Badih; Kamath, Pritish; Sudan, Madhu 1 2016 Streaming lower bounds for approximating max-cut. Zbl 1371.68213 Kapralov, Michael; Khanna, Sanjeev; Sudan, Madhu 7 2015 Communication with imperfectly shared randomness. Zbl 1364.68192 Canonne, Clement Louis; Guruswami, Venkatesan; Meka, Raghu; Sudan, Madhu 2 2015 Absolutely sound testing of lifted codes. Zbl 1337.68289 Haramaty, Elad; Ron-Zewi, Noga; Sudan, Madhu 2 2015 Complexity theory. Abstracts from the workshop held November 15–21, 2015. Zbl 1380.00044 1 2015 Limits of local algorithms over sparse random graphs (extended abstract). Zbl 1365.05277 Gamarnik, David; Sudan, Madhu 30 2014 Optimal error rates for interactive coding. I: Adaptivity and other settings. Zbl 1315.94122 Ghaffari, Mohsen; Haeupler, Bernhard; Sudan, Madhu 15 2014 Approximating matching size from random streams. Zbl 1423.68344 Kapralov, Michael; Khanna, Sanjeev; Sudan, Madhu 13 2014 Queuing with future information. Zbl 1309.60090 Spencer, Joel; Sudan, Madhu; Xu, Kuang 4 2014 Deterministic compression with uncertain priors (extended abstract). Zbl 1364.68185 Haramaty, Elad; Sudan, Madhu 1 2014 List decoding group homomorphisms between supersolvable groups. Zbl 1359.94851 Guo, Alan; Sudan, Madhu 1 2014 Extensions to the method of multiplicities, with applications to Kakeya sets and mergers. Zbl 1285.68116 Dvir, Zeev; Kopparty, Swastik; Saraf, Shubhangi; Sudan, Madhu 31 2013 New affine-invariant codes from lifting. Zbl 1364.94606 Guo, Alan; Kopparty, Swastik; Sudan, Madhu 18 2013 2-transitivity is insufficient for local testability. Zbl 1283.94130 Grigorescu, Elena; Kaufman, Tali; Sudan, Madhu 9 2013 Optimal testing of multivariate polynomials over small prime fields. Zbl 1275.68068 Haramaty, Elad; Shpilka, Amir; Sudan, Madhu 3 2013 A theory of goal-oriented communication. Zbl 1281.94004 Goldreich, Oded; Juba, Brendan; Sudan, Madhu 48 2012 Succinct representation of codes with applications to testing. Zbl 1264.94113 Grigorescu, Elena; Kaufman, Tali; Sudan, Madhu 2 2012 A new upper bound on the query complexity for testing generalized Reed-Muller codes. Zbl 1366.68362 Ron-Zewi, Noga; Sudan, Madhu 1 2012 Kakeya-type sets in finite vector spaces. Zbl 1230.42027 Kopparty, Swastik; Lev, Vsevolod F.; Saraf, Shubhangi; Sudan, Madhu 8 2011 On sums of locally testable affine invariant properties. Zbl 1343.68287 Ben-Sasson, Eli; Grigorescu, Elena; Maatouk, Ghid; Shpilka, Amir; Sudan, Madhu 7 2011 Limits on the rate of locally testable affine-invariant codes. Zbl 1343.68288 Ben-Sasson, Eli; Sudan, Madhu 7 2011 Testing linear-invariant non-linear properties. Zbl 1246.68259 Bhattacharyya, Arnab; Chen, Victor; Sudan, Madhu; Xie, Ning 6 2011 Derandomization of auctions. Zbl 1236.91072 Aggarwal, Gagan; Fiat, Amos; Goldberg, Andrew V.; Hartline, Jason D.; Immorlica, Nicole; Sudan, Madhu 3 2011 From logarithmic advice to single-bit advice. Zbl 1343.68080 Goldreich, Oded; Sudan, Madhu; Trevisan, Luca 1 2011 Optimal testing of multivariate polynomials over small prime fields. Zbl 1292.68157 Haramaty, Elad; Shpilka, Amir; Sudan, Madhu 1 2011 Optimal testing of Reed-Muller codes. Zbl 1310.68227 Bhattacharyya, Arnab; Kopparty, Swastik; Schoenebeck, Grant; Sudan, Madhu; Zuckerman, David 20 2010 Locally testable codes require redundant testers. Zbl 1209.68265 Ben-Sasson, Eli; Guruswami, Venkatesan; Kaufman, Tali; Sudan, Madhu; Viderman, Michael 8 2010 Invariance in property testing. Zbl 1309.68055 Sudan, Madhu 7 2010 Optimal error correction for computationally bounded noise. Zbl 1366.94397 Micali, Silvio; Peikert, Chris; Sudan, Madhu; Wilson, David A. 3 2010 Testing linear-invariant non-linear properties: a short report. Zbl 1259.68229 Bhattacharyya, Arnab; Chen, Victor; Sudan, Madhu; Xie, Ning 3 2010 Short PCPs with polylog query complexity. Zbl 1172.68025 Ben-Sasson, Eli; Sudan, Madhu 42 2009 Extensions to the method of multiplicities, with applications to Kakeya sets and mergers. Zbl 1292.68119 Dvir, Zeev; Kopparty, Swastik; Saraf, Shubhangi; Sudan, Madhu 26 2009 Succinct representation of codes with applications to testing. Zbl 1255.94082 Grigorescu, Elena; Kaufman, Tali; Sudan, Madhu 8 2009 Testing linear-invariant non-linear properties. Zbl 1236.68289 Bhattacharyya, Arnab; Chen, Victor; Sudan, Madhu; Xie, Ning 5 2009 Algebraic property testing: the role of invariance. Zbl 1231.68290 Kaufman, Tali; Sudan, Madhu 38 2008 An improved lower bound on the size of Kakeya sets over finite fields. Zbl 1335.42017 Saraf, Shubhangi; Sudan, Madhu 25 2008 Universal semantic communication. Zbl 1231.68244 Juba, Brendan; Sudan, Madhu 3 2008 Decodability of group homomorphisms beyond the Johnson bound. Zbl 1231.94061 Dinur, Irit; Grigorescu, Elena; Kopparty, Swastik; Sudan, Madhu 3 2008 Amplifying collision resistance: a complexity-theoretic treatment. Zbl 1215.94036 Canetti, Ran; Rivest, Ron; Sudan, Madhu; Trevisan, Luca; Vadhan, Salil; Wee, Hoeteck 10 2007 On Dinur’s proof of the PCP theorem. Zbl 1112.68117 Radhakrishnan, Jaikumar; Sudan, Madhu 5 2007 Guessing secrets efficiently via list decoding. Zbl 1446.94201 Alon, Noga; Guruswami, Venkatesan; Kaufman, Tali; Sudan, Madhu 1 2007 Robust PCPs of proximity, shorter PCPs, and applications to coding. Zbl 1118.68071 Ben-Sasson, Eli; Goldreich, Oded; Harsha, Prahladh; Sudan, Madhu; Vadhan, Salil 80 2006 Locally testable codes and PCPs of almost-linear length. Zbl 1315.94144 Goldreich, Oded; Sudan, Madhu 46 2006 A fuzzy vault scheme. Zbl 1172.94578 Juels, Ari; Sudan, Madhu 26 2006 Robust locally testable codes and products of codes. Zbl 1103.90080 Ben-Sasson, Eli; Sudan, Madhu 19 2006 Robust local testability of tensor products of LDPC codes. Zbl 1155.94402 Dinur, Irit; Sudan, Madhu; Wigderson, Avi 11 2006 Harmonic broadcasting is bandwidth-optimal assuming constant bit rate. Zbl 1093.94018 Engebretsen, Lars; Sudan, Madhu 5 2006 Local decoding and testing for homomorphisms. Zbl 1155.94408 Grigorescu, Elena; Kopparty, Swastik; Sudan, Madhu 2 2006 Derandomization of auctions. Zbl 1192.91095 Aggarwal, Gagan; Fiat, Amos; Goldberg, Andrew V.; Hartline, Jason D.; Immorlica, Nicole; Sudan, Madhu 12 2005 Simple PCPs with poly-log rate and query complexity. Zbl 1192.68287 Ben-Sasson, Eli; Sudan, Madhu 11 2005 Optimal error correction against computationally bounded noise. Zbl 1079.94565 Micali, Silvio; Peikert, Chris; Sudan, Madhu; Wilson, David A. 8 2005 Distributed computing with imperfect randomness. Zbl 1171.68860 Goldwasser, Shafi; Sudan, Madhu; Vaikuntanathan, Vinod 6 2005 Robust PSPs of proximity, shorter PSPs and applications to coding. Zbl 1192.68286 Ben-Sasson, Eli; Goldreich, Oded; Harsha, Prahladh; Sudan, Madhu; Vadhan, Salil 6 2004 Probabilistically checkable proofs. Zbl 1161.68021 Sudan, Madhu 4 2004 Robust locally testable codes and products of codes. Zbl 1105.68346 Ben-Sasson, Eli; Sudan, Madhu 3 2004 Improved low-degree testing and its applications. Zbl 1101.68572 Arora, Sanjeev; Sudan, Madhu 34 2003 Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. Zbl 1192.94089 Ben-Sasson, Eli; Sudan, Madhu; Vadhan, Salil; Wigderson, Avi 25 2003 Hardness of approximating the minimum distance of a linear code. Zbl 1063.68055 Dumer, Ilya; Micciancio, Daniele; Sudan, Madhu 22 2003 Bounds on \(2\)-query codeword testing. Zbl 1279.94142 Ben-Sasson, Eli; Goldreich, Oded; Sudan, Madhu 6 2003 Reconstructing curves in three (and higher) dimensional space from noisy data. Zbl 1192.94039 Coppersmith, Don; Sudan, Madhu 3 2003 Quick and dirty refereeing? Zbl 1226.68096 Sudan, Madhu 1 2003 Hardness of approximate hypergraph coloring. Zbl 1008.68052 Guruswami, Venkatesan; Hastad, Johan; Sudan, Madhu 16 2002 Combinatorial bounds for list decoding. Zbl 1061.94074 Guruswami, Venkatesan; Håstad, Johan; Sudan, Madhu; Zuckerman, David 9 2002 Guessing secrets efficiently via list decoding. Zbl 1058.94023 Alon, Noga; Guruswami, Venkatesan; Kaufman, Tali; Sudan, Madhu 7 2002 Complexity classifications of Boolean constraint satisfaction problems. Zbl 0981.68058 Creignou, Nadia; Khanna, Sanjeev; Sudan, Madhu 128 2001 The approximability of constraint satisfaction problems. Zbl 0992.68059 Khanna, Sanjeev; Sudan, Madhu; Trevisan, Luca; Williamson, David P. 54 2001 Pseudorandom generators without the XOR lemma. Zbl 1005.65006 Sudan, Madhu; Trevisan, Luca; Vadhan, Salil 54 2001 Adversarial queuing theory. Zbl 1320.68053 Borodin, Allan; Kleinberg, Jon; Raghavan, Prabhakar; Sudan, Madhu; Williamson, David P. 46 2001 Ideal error-correcting codes: Unifying algebraic and number-theoretic algorithms. Zbl 1057.94516 Sudan, Madhu 7 2001 On representations of algebraic-geometry codes. Zbl 1002.94041 Guruswami, Venkatesan; Sudan, Madhu 6 2001 Random walks with “back buttons”. Zbl 1021.60031 Fagin, Ronald; Karlin, Anna R.; Kleinberg, Jon; Raghavan, Prabhakar; Rajagopalan, Sridhar; Rubinfeld, Ronitt; Sudan, Madhu; Tomkins, Andrew 4 2001 Linear-consistency testing. Zbl 1052.68122 Aumann, Yonatan; Håstad, Johan; Rabin, Michael O.; Sudan, Madhu 3 2001 Gadgets, approximation, and linear programming. Zbl 0957.68048 Trevisan, Luca; Sorkin, Gregory B.; Sudan, Madhu; Williamson, David P. 46 2000 Chinese remaindering with errors. Zbl 1007.94026 Goldreich, Oded; Ron, Dana; Sudan, Madhu 17 2000 Learning polynomials with queries: The highly noisy case. Zbl 0968.68063 Goldreich, Oded; Rubinfeld, Ronitt; Sudan, Madhu 16 2000 List decoding algorithms for certain concatenated codes. Zbl 1296.94170 Guruswami, Venkatesan; Sudan, Madhu 10 2000 Small PCPs with low query complexity. Zbl 0986.68134 Harsha, Prahladh; Sudan, Madhu 8 2000 List decoding: Algorithms and applications. Zbl 1009.94572 Sudan, Madhu 7 2000 Random walks with “back buttons” (extended abstract). Zbl 1296.60191 Fagin, Ronald; Karlin, Anna R.; Kleinberg, Jon; Raghavan, Prabhakar; Rajagopalan, Sridhar; Rubinfeld, Ronitt; Sudan, Madhu; Tomkins, Andrew 3 2000 On representations of algebraic-geometric codes for list decoding. Zbl 0974.94030 Guruswami, Venkatesan; Sudan, Madhu 1 2000 Improved decoding of Reed-Solomon and algebraic-geometry codes. Zbl 0958.94036 Guruswami, Venkatesan; Sudan, Madhu 117 1999 Improved low degree testing and its applications. Zbl 0968.68145 Arora, Sanjeev; Sudan, Madhu 19 1999 A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction. Zbl 0962.68068 Khanna, Sanjeev; Sudan, Madhu; Williamson, David P. 13 1999 Pseudorandom generators without the XOR lemma (extended abstract). Zbl 1345.68138 Sudan, Madhu; Trevisan, Luca; Vadhan, Salil 13 1999 Chinese remaindering with errors. Zbl 1345.94105 Goldreich, Oded; Ron, Dana; Sudan, Madhu 6 1999 Computational indistinguishability: A sample hierarchy. Zbl 0947.68066 Goldreich, Oded; Sudan, Madhu 1 1999 Proof verification and the hardness of approximation problems. Zbl 1065.68570 Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario 279 1998 Approximate graph coloring by semidefinite programming. Zbl 0904.68116 Karger, David; Motwani, Rajeev; Sudan, Madhu 98 1998 Free bits, PCPs, and nonapproximability – towards tight results. Zbl 0912.68041 Bellare, Mihir; Goldreich, Oded; Sudan, Madhu 91 1998 ...and 29 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 2,988 Authors 38 Goldreich, Oded 26 Paschos, Vangelis Th. 25 Guruswami, Venkatesan 24 Sudan, Madhu 21 Chiesa, Alessandro 21 Ishai, Yuval 17 Gur, Tom 16 Alon, Noga 16 Ben-Sasson, Eli 16 Ron, Dana 15 Khot, Subhash Ajit 15 Krokhin, Andrei A. 15 Rothblum, Ron D. 14 Dinur, Irit 14 Živný, Stanislav 13 Kaufman, Tali 13 Rubinfeld, Ronitt 12 Creignou, Nadia 12 Grigorescu, Elena 12 Håstad, Johan Torkel 12 Raskhodnikova, Sofya 12 Wootters, Mary 11 Bazgan, Cristina 11 Chen, Hubie 11 Gamarnik, David 11 Halldórsson, Magnús Mar 11 Jonsson, Peter 11 Shapira, Asaf 10 Bhattacharyya, Arnab 10 Demange, Marc 10 Escoffier, Bruno 10 Jeavons, Peter G. 10 Kopparty, Swastik 10 Krivelevich, Michael 10 Marathe, Madhav V. 10 Shaltiel, Ronen 10 Trevisan, Luca 10 Yoshida, Yuichi 9 Applebaum, Benny 9 Boyle, Elette 9 Feige, Uriel 9 Fox, Jacob 9 Golovach, Petr A. 9 Kowalski, Dariusz R. 9 Manurangsi, Pasin 9 Ostrovsky, Rafail 9 Ravi, S. S. 9 Ron-Zewi, Noga 9 Vaikuntanathan, Vinod 8 Faria, Luerbio 8 Fischer, Eldar 8 Lê Văn Băng 8 Martin, Barnaby D. 8 Saurabh, Saket 8 Ta-Shma, Amnon 8 Yannakakis, Mihalis 7 Bhangale, Amey 7 Bulatov, Andrei A. 7 Cai, Jin-Yi 7 Chlebus, Bogdan Stanislaw 7 Cohen, David A. 7 Haviv, Ishay 7 Kann, Viggo 7 Kratsch, Dieter 7 Lu, Pinyan 7 Meir, Or 7 Newman, Ilan I. 7 Paulusma, Daniël 7 Shinkar, Igor 7 Tauman Kalai, Yael 7 Vadhan, Salil P. 7 Wigderson, Avi 6 Austrin, Per 6 Blais, Eric 6 Blesa, Maria J. 6 Bshouty, Nader H. 6 Chen, Jian-er 6 Cooper, Martin C. 6 Couteau, Geoffroy 6 Crescenzi, Pierluigi 6 Fujito, Toshihiro 6 Harsha, Prahladh 6 Hell, Pavol 6 Hemenway, Brett 6 Hermann, Miki 6 Jiang, Tao 6 Kabatiansky, Grigorii A. 6 Lu, Chijen 6 Makarychev, Yury S. 6 Marx, Dániel 6 Pass, Rafael 6 Ravi, Ramamoorthi 6 Roberson, David E. 6 Ruano, Diego 6 Safra, Muli 6 Saraf, Shubhangi 6 Viderman, Michael 6 Vollmer, Heribert 6 Yeo, Anders 6 Zhu, Daming ...and 2,888 more Authors all top 5 Cited in 232 Serials 163 Theoretical Computer Science 76 Journal of Computer and System Sciences 70 Algorithmica 68 Discrete Applied Mathematics 67 SIAM Journal on Computing 66 Information Processing Letters 47 Computational Complexity 39 Designs, Codes and Cryptography 30 Information and Computation 30 Theory of Computing Systems 29 Random Structures & Algorithms 24 European Journal of Operational Research 23 Mathematical Programming. Series A. Series B 23 Journal of Combinatorial Optimization 20 Journal of Cryptology 18 SIAM Journal on Discrete Mathematics 16 Discrete Mathematics 14 Information Sciences 14 Operations Research Letters 14 Combinatorica 14 Combinatorics, Probability and Computing 13 Quantum Information Processing 12 Discrete Optimization 11 Journal of Symbolic Computation 11 Distributed Computing 11 The Electronic Journal of Combinatorics 10 Finite Fields and their Applications 10 Journal of Discrete Algorithms 9 Artificial Intelligence 9 Problems of Information Transmission 9 International Journal of Foundations of Computer Science 8 European Journal of Combinatorics 8 Journal of the ACM 8 Cryptography and Communications 7 Israel Journal of Mathematics 7 Operations Research 7 Journal of Complexity 7 Computers & Operations Research 7 Linear Algebra and its Applications 7 Applicable Algebra in Engineering, Communication and Computing 7 Annals of Mathematics and Artificial Intelligence 7 RAIRO. Operations Research 7 Journal of Machine Learning Research (JMLR) 7 Advances in Mathematics of Communications 7 Computer Science Review 7 ACM Transactions on Computation Theory 6 Networks 6 Constraints 6 4OR 5 Communications in Mathematical Physics 5 Journal of Combinatorial Theory. Series A 5 Journal of Combinatorial Theory. Series B 5 Journal of Graph Theory 5 Discrete & Computational Geometry 5 Annals of Operations Research 5 Cybernetics and Systems Analysis 5 Journal of Statistical Mechanics: Theory and Experiment 5 Journal of Mathematical Cryptology 5 Theory of Computing 4 International Journal of Theoretical Physics 4 The Annals of Probability 4 The Annals of Statistics 4 Journal of Computer Science and Technology 4 The Annals of Applied Probability 4 Computational Geometry 4 Geometric and Functional Analysis. GAFA 4 Games and Economic Behavior 4 Bulletin of the American Mathematical Society. New Series 4 Journal of Scheduling 4 Annals of Mathematics. Second Series 4 Optimization Letters 4 Discrete Mathematics, Algorithms and Applications 4 Discrete Analysis 4 Prikladnaya Diskretnaya Matematika 3 Acta Informatica 3 Computers & Mathematics with Applications 3 Communications on Pure and Applied Mathematics 3 Algebra Universalis 3 Mathematics of Operations Research 3 Probability Theory and Related Fields 3 Journal of the American Mathematical Society 3 Journal of Global Optimization 3 Journal of Algebraic Combinatorics 3 Journal of Mathematical Sciences (New York) 3 International Transactions in Operational Research 3 INFORMS Journal on Computing 3 Data Mining and Knowledge Discovery 3 ACM Transactions on Computational Logic 3 ACM Journal of Experimental Algorithmics 3 Oberwolfach Reports 3 Journal of Zhejiang University. Science A 3 Algorithms 3 AIMS Mathematics 3 Matematicheskie Voprosy Kriptografii 2 Journal of Mathematical Biology 2 Journal of Statistical Physics 2 Mathematics of Computation 2 The Mathematical Intelligencer 2 Advances in Mathematics 2 American Journal of Mathematics ...and 132 more Serials all top 5 Cited in 41 Fields 1,325 Computer science (68-XX) 497 Information and communication theory, circuits (94-XX) 462 Combinatorics (05-XX) 380 Operations research, mathematical programming (90-XX) 87 Number theory (11-XX) 67 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 65 Quantum theory (81-XX) 43 Mathematical logic and foundations (03-XX) 41 Probability theory and stochastic processes (60-XX) 33 Algebraic geometry (14-XX) 31 Order, lattices, ordered algebraic structures (06-XX) 30 Statistics (62-XX) 30 Biology and other natural sciences (92-XX) 26 Statistical mechanics, structure of matter (82-XX) 24 Commutative algebra (13-XX) 22 General algebraic systems (08-XX) 22 Convex and discrete geometry (52-XX) 20 Numerical analysis (65-XX) 18 Linear and multilinear algebra; matrix theory (15-XX) 18 Geometry (51-XX) 14 Field theory and polynomials (12-XX) 10 Group theory and generalizations (20-XX) 9 Dynamical systems and ergodic theory (37-XX) 8 Systems theory; control (93-XX) 7 General and overarching topics; collections (00-XX) 7 Harmonic analysis on Euclidean spaces (42-XX) 6 Functional analysis (46-XX) 5 Approximations and expansions (41-XX) 4 Measure and integration (28-XX) 4 Operator theory (47-XX) 3 Associative rings and algebras (16-XX) 3 Abstract harmonic analysis (43-XX) 2 Topological groups, Lie groups (22-XX) 2 Real functions (26-XX) 1 History and biography (01-XX) 1 Category theory; homological algebra (18-XX) 1 Partial differential equations (35-XX) 1 Difference and functional equations (39-XX) 1 General topology (54-XX) 1 Global analysis, analysis on manifolds (58-XX) 1 Classical thermodynamics, heat transfer (80-XX) Citations by Year Wikidata Timeline The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.