×
Author ID: sudan.madhu Recent zbMATH articles by "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)
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

Publications by Year

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 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

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.