×

zbMATH — the first resource for mathematics

Sudan, Madhu

Compute Distance To:
Author ID: sudan.madhu Recent zbMATH articles by "Sudan, Madhu"
Published as: Sudan, Madhu; Sudan, M.
Homepage: http://madhu.seas.harvard.edu/
External Links: IdRef · MGP · Wikidata · dblp · GND
Awards: Nevanlinna Prize (2002)
Documents Indexed: 148 Publications since 1992, including 2 Books
Biographic References: 3 Publications
all top 5

Co-Authors

9 single-authored
20 Goldreich, Oded
14 Guruswami, Venkatesan
12 Ben-Sasson, Eli
8 Haramaty, Elad
8 Khanna, Sanjeev
8 Rubinfeld, Ronitt
8 Vadhan, Salil P.
7 Ghazi, Badih
7 Kaufman, Tali
7 Kopparty, Swastik
6 Coppersmith, Don
6 Grigorescu, Elena
6 Håstad, Johan Torkel
6 Trevisan, Luca
5 Bellare, Mihir
5 Motwani, Rajeev
5 Raghavan, Prabhakar
5 Ron-Zewi, Noga
5 Schieber, Baruch
5 Williamson, David P.
4 Arora, Sanjeev
4 Bar-Noy, Amotz
4 Bhattacharyya, Arnab
4 Harsha, Prahladh
4 Kleinberg, Jon Michael
4 Saraf, Shubhangi
3 Chen, Victor C.
3 Chor, Benny
3 Gamarnik, David
3 Kamath, Pritish
3 Kapralov, Michael
3 Shpilka, Amir
3 Xie, Ning
2 Aggarwal, Alok
2 Aggarwal, Gagan
2 Alon, Noga M.
2 Ar, Sigal
2 Aumann, Yonatan
2 Bafna, Mitali
2 Błasiok, Jarosław
2 Borodin, Allan B.
2 Bürgisser, Peter
2 Canonne, Clement Louis
2 Dinur, Irit
2 Dvir, Zeev
2 Engebretsen, Lars
2 Fagin, Ronald
2 Fiat, Amos
2 Goldberg, Andrew V.
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 Kushilevitz, Eyal
2 Lipton, Richard J.
2 Lund, Carsten
2 Mayer, Alain J.
2 Meka, Raghu
2 Micali, Silvio
2 Peikert, Chris
2 Rabin, Michael O.
2 Rajagopalan, Sridhar
2 Ramaswami, Rajiv
2 Rivest, Ronald Linn
2 Ron, Dana
2 Srinivasan, Srikanth
2 Szegedy, Mario
2 Tomkins, Andrew
2 Velingker, Ameya
2 von zur Gathen, Joachim
2 Wigderson, Avi
2 Wilson, David A.
2 Zuckerman, David
1 Albanese, Andres
1 Bavarian, Mohammad
1 Bern, Marshall W.
1 Blömer, Johannes
1 Blum, Avrim L.
1 Canetti, Ran
1 Chalasani, Prasad
1 Creignou, Nadia
1 Dumer, Ilya I.
1 Edmonds, Jeff A.
1 Even, Guy
1 Gemmell, Peter S.
1 Ghaffari, Mohsen
1 Goldwasser, Shafi
1 Greene, Daniel H.
1 Juels, Ari
1 Karger, David R.
1 Lev, Vsevolod F.
1 Luby, Michael G.
1 Maatouk, Ghid
1 Micciancio, Daniele
...and 19 more Co-Authors

Publications by Year

Citations contained in zbMATH Open

115 Publications have been cited 2,160 times in 1,478 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
203
1998
Robust characterizations of polynomials with applications to program testing. Zbl 0844.68062
Rubinfeld, Ronitt; Sudan, Madhu
151
1996
Proof verification and hardness of approximation problems. Zbl 0977.68539
Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario
149
1992
Improved decoding of Reed-Solomon and algebraic-geometry codes. Zbl 0958.94036
Guruswami, Venkatesan; Sudan, Madhu
95
1999
Complexity classifications of Boolean constraint satisfaction problems. Zbl 0981.68058
Creignou, Nadia; Khanna, Sanjeev; Sudan, Madhu
93
2001
Free bits, PCPs, and nonapproximability – towards tight results. Zbl 0912.68041
Bellare, Mihir; Goldreich, Oded; Sudan, Madhu
77
1998
Approximate graph coloring by semidefinite programming. Zbl 0904.68116
Karger, David; Motwani, Rajeev; Sudan, Madhu
77
1998
Decoding of Reed Solomon codes beyond the error-correction bound. Zbl 0872.68026
Sudan, Madhu
63
1997
On syntactic versus computational views of approximability. Zbl 0915.68068
Khanna, Sanjeev; Motwani, Rajeev; Sudan, Madhu; Vazirani, Umesh
54
1998
Private information retrieval. Zbl 1065.68524
Chor, Benny; Goldreich, Oded; Kushilevitz, Eyal; Sudan, Madhu
54
1998
The minimum latency problem. Zbl 1345.90073
Blum, Avrim; Chalasani, Prasad; Coppersmith, Don; Pulleyblank, Bill; Raghavan, Prabhakar; Sudan, Madhu
51
1994
Approximating minimum feedback sets and multicuts in directed graphs. Zbl 0897.68078
Even, G.; Naor, J.; Schieber, B.; Sudan, M.
50
1998
A theory of goal-oriented communication. Zbl 1281.94004
Goldreich, Oded; Juba, Brendan; Sudan, Madhu
48
2012
Robust PCPs of proximity, shorter PCPs, and applications to coding. Zbl 1118.68071
Ben-Sasson, Eli; Goldreich, Oded; Harsha, Prahladh; Sudan, Madhu; Vadhan, Salil
45
2006
Locally testable codes and PCPs of almost-linear length. Zbl 1315.94144
Goldreich, Oded; Sudan, Madhu
35
2006
The approximability of constraint satisfaction problems. Zbl 0992.68059
Khanna, Sanjeev; Sudan, Madhu; Trevisan, Luca; Williamson, David P.
34
2001
Adversarial queuing theory. Zbl 1320.68053
Borodin, Allan; Kleinberg, Jon; Raghavan, Prabhakar; Sudan, Madhu; Williamson, David P.
33
2001
Gadgets, approximation, and linear programming. Zbl 0957.68048
Trevisan, Luca; Sorkin, Gregory B.; Sudan, Madhu; Williamson, David P.
32
2000
Pseudorandom generators without the XOR lemma. Zbl 1005.65006
Sudan, Madhu; Trevisan, Luca; Vadhan, Salil
31
2001
Computing roots of graphs is hard. Zbl 0812.68103
Motwani, Rajeev; Sudan, Madhu
31
1994
Private information retrieval. Zbl 0938.68625
Chor, Benny; Goldreich, Oded; Kushilevitz, Eyal; Sudan, Madhu
30
1995
Algebraic property testing: the role of invariance. Zbl 1231.68290
Kaufman, Tali; Sudan, Madhu
30
2008
Linearity testing in characteristic two. Zbl 0867.68060
Bellare, Mihir; Coppersmith, Don; Håstad, Johan; Kiwi, Marcos; Sudan, Madhu
27
1996
Improved low-degree testing and its applications. Zbl 1101.68572
Arora, Sanjeev; Sudan, Madhu
26
2003
Short PCPs with polylog query complexity. Zbl 1172.68025
Ben-Sasson, Eli; Sudan, Madhu
23
2009
Improved non-approximability results. Zbl 1344.68094
Bellare, Mihir; Sudan, Madhu
22
1994
Highly resilient correctors for polynomials. Zbl 0767.68075
Gemmell, Peter; Sudan, Madhu
20
1992
Limits of local algorithms over sparse random graphs (extended abstract). Zbl 1365.05277
Gamarnik, David; Sudan, Madhu
20
2014
Extensions to the method of multiplicities, with applications to Kakeya sets and mergers. Zbl 1292.68119
Dvir, Zeev; Kopparty, Swastik; Saraf, Shubhangi; Sudan, Madhu
20
2009
Improved low degree testing and its applications. Zbl 0968.68145
Arora, Sanjeev; Sudan, Madhu
19
1999
A geometric approach to betweenness. Zbl 0912.68058
Chor, Benny; Sudan, Madhu
18
1998
Free bits, PCPs and non-approximability – towards tight results. Zbl 0938.68820
Bellare, Mihir; Goldreich, Oded; Sudan, Madhu
18
1995
An improved lower bound on the size of Kakeya sets over finite fields. Zbl 1335.42017
Saraf, Shubhangi; Sudan, Madhu
17
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
17
2003
Optimal testing of Reed-Muller codes. Zbl 1310.68227
Bhattacharyya, Arnab; Kopparty, Swastik; Schoenebeck, Grant; Sudan, Madhu; Zuckerman, David
17
2010
A fuzzy vault scheme. Zbl 1172.94578
Juels, Ari; Sudan, Madhu
15
2006
Learning polynomials with queries: The highly noisy case. Zbl 0968.68063
Goldreich, Oded; Rubinfeld, Ronitt; Sudan, Madhu
14
2000
Efficient routing and scheduling algorithms for optical networks. Zbl 0874.68018
Aggarwal, Alok; Bar-Noy, Amotz; Coppersmith, Don; Ramaswami, Rajiv; Schieber, Baruch; Sudan, Madhu
13
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
Robust locally testable codes and products of codes. Zbl 1103.90080
Ben-Sasson, Eli; Sudan, Madhu
13
2006
Hardness of approximating the minimum distance of a linear code. Zbl 1063.68055
Dumer, Ilya; Micciancio, Daniele; Sudan, Madhu
12
2003
Extensions to the method of multiplicities, with applications to Kakeya sets and mergers. Zbl 1285.68116
Dvir, Zeev; Kopparty, Swastik; Saraf, Shubhangi; Sudan, Madhu
12
2013
Hardness of approximate hypergraph coloring. Zbl 1008.68052
Guruswami, Venkatesan; Hastad, Johan; Sudan, Madhu
11
2002
Chinese remaindering with errors. Zbl 1007.94026
Goldreich, Oded; Ron, Dana; Sudan, Madhu
11
2000
Pseudorandom generators without the XOR lemma (extended abstract). Zbl 1345.68138
Sudan, Madhu; Trevisan, Luca; Vadhan, Salil
11
1999
Learning polynomials with queries: The highly noisy case. Zbl 0938.68642
Goldreich, Oded; Rubinfeld, Ronitt; Sudan, Madhu
10
1995
Efficient checking of polynomials and proofs and the hardness of approximation problems. Zbl 0861.68042
Sudan, Madhu
10
1995
New affine-invariant codes from lifting. Zbl 1364.94606
Guo, Alan; Kopparty, Swastik; Sudan, Madhu
10
2013
Priority encoding transmission. Zbl 0867.94038
Albanese, Andres; Blömer, Johannes; Edmonds, Jeff; Luby, Michael; Sudan, Madhu
9
1996
Optimal error rates for interactive coding. I: Adaptivity and other settings. Zbl 1315.94122
Ghaffari, Mohsen; Haeupler, Bernhard; Sudan, Madhu
9
2014
Derandomization of auctions. Zbl 1192.91095
Aggarwal, Gagan; Fiat, Amos; Goldberg, Andrew V.; Hartline, Jason D.; Immorlica, Nicole; Sudan, Madhu
9
2005
Simple PCPs with poly-log rate and query complexity. Zbl 1192.68287
Ben-Sasson, Eli; Sudan, Madhu
9
2005
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
List decoding algorithms for certain concatenated codes. Zbl 1296.94170
Guruswami, Venkatesan; Sudan, Madhu
8
2000
Robust local testability of tensor products of LDPC codes. Zbl 1155.94402
Dinur, Irit; Sudan, Madhu; Wigderson, Avi
8
2006
Reconstructing algebraic functions from mixed data. Zbl 0915.68088
Ar, Sigal; Lipton, Richard J.; Rubinfeld, Ronitt; Sudan, Madhu
7
1998
Linearity testing in characteristic two. Zbl 0938.68926
Bellare, M.; Coppersmith, D.; Håstad, J.; Kiwi, M.; Sudan, M.
7
1995
Efficient routing in optical networks. Zbl 0885.68083
Aggarwal, Alok; Bar-Noy, Amotz; Coppersmith, Don; Ramaswami, Rajiv; Schieber, Baruch; Sudan, Madhu
7
1996
Guessing secrets efficiently via list decoding. Zbl 1058.94023
Alon, Noga; Guruswami, Venkatesan; Kaufman, Tali; Sudan, Madhu
7
2002
Self-testing polynomial functions efficiently and over rational domains. Zbl 0834.68076
Rubinfeld, Ronitt; Sudan, Madhu
7
1992
Succinct representation of codes with applications to testing. Zbl 1255.94082
Grigorescu, Elena; Kaufman, Tali; Sudan, Madhu
7
2009
Limits of local algorithms over sparse random graphs. Zbl 1371.05265
Gamarnik, David; Sudan, Madhu
7
2017
Small PCPs with low query complexity. Zbl 0986.68134
Harsha, Prahladh; Sudan, Madhu
6
2000
Ideal error-correcting codes: Unifying algebraic and number-theoretic algorithms. Zbl 1057.94516
Sudan, Madhu
6
2001
Limits on the rate of locally testable affine-invariant codes. Zbl 1343.68288
Ben-Sasson, Eli; Sudan, Madhu
6
2011
Combinatorial bounds for list decoding. Zbl 1061.94074
Guruswami, Venkatesan; Håstad, Johan; Sudan, Madhu; Zuckerman, David
6
2002
Performance of sequential local algorithms for the random NAE-\(K\)-SAT problem. Zbl 1388.60037
Gamarnik, David; Sudan, Madhu
6
2017
Bounds on \(2\)-query codeword testing. Zbl 1279.94142
Ben-Sasson, Eli; Goldreich, Oded; Sudan, Madhu
6
2003
Invariance in property testing. Zbl 1309.68055
Sudan, Madhu
6
2010
Optimal error correction against computationally bounded noise. Zbl 1079.94565
Micali, Silvio; Peikert, Chris; Sudan, Madhu; Wilson, David A.
5
2005
Amplifying collision resistance: a complexity-theoretic treatment. Zbl 1215.94036
Canetti, Ran; Rivest, Ron; Sudan, Madhu; Trevisan, Luca; Vadhan, Salil; Wee, Hoeteck
5
2007
Harmonic broadcasting is bandwidth-optimal assuming constant bit rate. Zbl 1093.94018
Engebretsen, Lars; Sudan, Madhu
5
2006
Robust PSPs of proximity, shorter PSPs and applications to coding. Zbl 1192.68286
Ben-Sasson, Eli; Goldreich, Oded; Harsha, Prahladh; Sudan, Madhu; Vadhan, Salil
5
2004
Testing linear-invariant non-linear properties. Zbl 1246.68259
Bhattacharyya, Arnab; Chen, Victor; Sudan, Madhu; Xie, Ning
5
2011
Approximating matching size from random streams. Zbl 1423.68344
Kapralov, Michael; Khanna, Sanjeev; Sudan, Madhu
5
2014
List decoding: Algorithms and applications. Zbl 1009.94572
Sudan, Madhu
4
2000
On representations of algebraic-geometry codes. Zbl 1002.94041
Guruswami, Venkatesan; Sudan, Madhu
4
2001
On sums of locally testable affine invariant properties. Zbl 1343.68287
Ben-Sasson, Eli; Grigorescu, Elena; Maatouk, Ghid; Shpilka, Amir; Sudan, Madhu
4
2011
Kakeya-type sets in finite vector spaces. Zbl 1230.42027
Kopparty, Swastik; Lev, Vsevolod F.; Saraf, Shubhangi; Sudan, Madhu
4
2011
Queuing with future information. Zbl 1309.60090
Spencer, Joel; Sudan, Madhu; Xu, Kuang
4
2014
Testing linear-invariant non-linear properties. Zbl 1236.68289
Bhattacharyya, Arnab; Chen, Victor; Sudan, Madhu; Xie, Ning
4
2009
Guaranteeing fair service to persistent dependent tasks. Zbl 0910.90174
Bar-Noy, Amotz; Mayer, Alain; Schieber, Baruch; Sudan, Madhu
3
1998
Reconsructing algebraic functions from mixed data. Zbl 0925.68221
Ar, Sigal; Lipton, Richard J.; Rubinfeld, Ronitt; Sudan, Madhu
3
1992
Adversarial queueing theory. Zbl 0934.60079
Borodin, Allan; Kleinberg, Jon; Raghavan, Prabhakar; Sudan, Madhu; Williamson, David P.
3
1996
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
3
2001
Streaming lower bounds for approximating max-cut. Zbl 1371.68213
Kapralov, Michael; Khanna, Sanjeev; Sudan, Madhu
3
2015
Distributed computing with imperfect randomness. Zbl 1171.68860
Goldwasser, Shafi; Sudan, Madhu; Vaikuntanathan, Vinod
3
2005
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
Derandomization of auctions. Zbl 1236.91072
Aggarwal, Gagan; Fiat, Amos; Goldberg, Andrew V.; Hartline, Jason D.; Immorlica, Nicole; Sudan, Madhu
3
2011
Reconstructing curves in three (and higher) dimensional space from noisy data. Zbl 1192.94039
Coppersmith, Don; Sudan, Madhu
3
2003
Linear-consistency testing. Zbl 1052.68122
Aumann, Yonatan; Håstad, Johan; Rabin, Michael O.; Sudan, Madhu
2
2001
Robust locally testable codes and products of codes. Zbl 1105.68346
Ben-Sasson, Eli; Sudan, Madhu
2
2004
Optimal error correction for computationally bounded noise. Zbl 1366.94397
Micali, Silvio; Peikert, Chris; Sudan, Madhu; Wilson, David A.
2
2010
On-line algorithms for locating checkpoints. Zbl 0784.68031
Bern, Marshall; Greene, Daniel H.; Raghunathan, Arvind; Sudan, Madhu
2
1994
On Dinur’s proof of the PCP theorem. Zbl 1112.68117
Radhakrishnan, Jaikumar; Sudan, Madhu
2
2007
\((1 + \Omega(1))\)-approximation to MAX-CUT requires linear space. Zbl 1410.68169
Kapralov, Michael; Khanna, Sanjeev; Sudan, Madhu; Velingker, Ameya
2
2017
Universal semantic communication. Zbl 1231.68244
Juba, Brendan; Sudan, Madhu
2
2008
Decodability of group homomorphisms beyond the Johnson bound. Zbl 1231.94061
Dinur, Irit; Grigorescu, Elena; Kopparty, Swastik; Sudan, Madhu
2
2008
Testing linear-invariant non-linear properties: a short report. Zbl 1259.68229
Bhattacharyya, Arnab; Chen, Victor; Sudan, Madhu; Xie, Ning
2
2010
Limits of local algorithms over sparse random graphs. Zbl 1371.05265
Gamarnik, David; Sudan, Madhu
7
2017
Performance of sequential local algorithms for the random NAE-\(K\)-SAT problem. Zbl 1388.60037
Gamarnik, David; Sudan, Madhu
6
2017
\((1 + \Omega(1))\)-approximation to MAX-CUT requires linear space. Zbl 1410.68169
Kapralov, Michael; Khanna, Sanjeev; Sudan, Madhu; Velingker, Ameya
2
2017
Sparse affine-invariant linear codes are locally testable. Zbl 1381.94114
Ben-Sasson, Eli; Ron-Zewi, Noga; Sudan, Madhu
1
2017
Communication complexity of permutation-invariant functions. Zbl 1410.68129
Ghazi, Badih; Kamath, Pritish; Sudan, Madhu
1
2016
Deterministic compression with uncertain priors. Zbl 1353.68075
Haramaty, Elad; Sudan, Madhu
1
2016
Streaming lower bounds for approximating max-cut. Zbl 1371.68213
Kapralov, Michael; Khanna, Sanjeev; Sudan, Madhu
3
2015
Communication with imperfectly shared randomness. Zbl 1364.68192
Canonne, Clement Louis; Guruswami, Venkatesan; Meka, Raghu; Sudan, Madhu
1
2015
Limits of local algorithms over sparse random graphs (extended abstract). Zbl 1365.05277
Gamarnik, David; Sudan, Madhu
20
2014
Optimal error rates for interactive coding. I: Adaptivity and other settings. Zbl 1315.94122
Ghaffari, Mohsen; Haeupler, Bernhard; Sudan, Madhu
9
2014
Approximating matching size from random streams. Zbl 1423.68344
Kapralov, Michael; Khanna, Sanjeev; Sudan, Madhu
5
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
Extensions to the method of multiplicities, with applications to Kakeya sets and mergers. Zbl 1285.68116
Dvir, Zeev; Kopparty, Swastik; Saraf, Shubhangi; Sudan, Madhu
12
2013
New affine-invariant codes from lifting. Zbl 1364.94606
Guo, Alan; Kopparty, Swastik; Sudan, Madhu
10
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
1
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
Limits on the rate of locally testable affine-invariant codes. Zbl 1343.68288
Ben-Sasson, Eli; Sudan, Madhu
6
2011
Testing linear-invariant non-linear properties. Zbl 1246.68259
Bhattacharyya, Arnab; Chen, Victor; Sudan, Madhu; Xie, Ning
5
2011
On sums of locally testable affine invariant properties. Zbl 1343.68287
Ben-Sasson, Eli; Grigorescu, Elena; Maatouk, Ghid; Shpilka, Amir; Sudan, Madhu
4
2011
Kakeya-type sets in finite vector spaces. Zbl 1230.42027
Kopparty, Swastik; Lev, Vsevolod F.; Saraf, Shubhangi; Sudan, Madhu
4
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 Reed-Muller codes. Zbl 1310.68227
Bhattacharyya, Arnab; Kopparty, Swastik; Schoenebeck, Grant; Sudan, Madhu; Zuckerman, David
17
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
6
2010
Optimal error correction for computationally bounded noise. Zbl 1366.94397
Micali, Silvio; Peikert, Chris; Sudan, Madhu; Wilson, David A.
2
2010
Testing linear-invariant non-linear properties: a short report. Zbl 1259.68229
Bhattacharyya, Arnab; Chen, Victor; Sudan, Madhu; Xie, Ning
2
2010
Short PCPs with polylog query complexity. Zbl 1172.68025
Ben-Sasson, Eli; Sudan, Madhu
23
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
20
2009
Succinct representation of codes with applications to testing. Zbl 1255.94082
Grigorescu, Elena; Kaufman, Tali; Sudan, Madhu
7
2009
Testing linear-invariant non-linear properties. Zbl 1236.68289
Bhattacharyya, Arnab; Chen, Victor; Sudan, Madhu; Xie, Ning
4
2009
Algebraic property testing: the role of invariance. Zbl 1231.68290
Kaufman, Tali; Sudan, Madhu
30
2008
An improved lower bound on the size of Kakeya sets over finite fields. Zbl 1335.42017
Saraf, Shubhangi; Sudan, Madhu
17
2008
Universal semantic communication. Zbl 1231.68244
Juba, Brendan; Sudan, Madhu
2
2008
Decodability of group homomorphisms beyond the Johnson bound. Zbl 1231.94061
Dinur, Irit; Grigorescu, Elena; Kopparty, Swastik; Sudan, Madhu
2
2008
Amplifying collision resistance: a complexity-theoretic treatment. Zbl 1215.94036
Canetti, Ran; Rivest, Ron; Sudan, Madhu; Trevisan, Luca; Vadhan, Salil; Wee, Hoeteck
5
2007
On Dinur’s proof of the PCP theorem. Zbl 1112.68117
Radhakrishnan, Jaikumar; Sudan, Madhu
2
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
45
2006
Locally testable codes and PCPs of almost-linear length. Zbl 1315.94144
Goldreich, Oded; Sudan, Madhu
35
2006
A fuzzy vault scheme. Zbl 1172.94578
Juels, Ari; Sudan, Madhu
15
2006
Robust locally testable codes and products of codes. Zbl 1103.90080
Ben-Sasson, Eli; Sudan, Madhu
13
2006
Robust local testability of tensor products of LDPC codes. Zbl 1155.94402
Dinur, Irit; Sudan, Madhu; Wigderson, Avi
8
2006
Harmonic broadcasting is bandwidth-optimal assuming constant bit rate. Zbl 1093.94018
Engebretsen, Lars; Sudan, Madhu
5
2006
Derandomization of auctions. Zbl 1192.91095
Aggarwal, Gagan; Fiat, Amos; Goldberg, Andrew V.; Hartline, Jason D.; Immorlica, Nicole; Sudan, Madhu
9
2005
Simple PCPs with poly-log rate and query complexity. Zbl 1192.68287
Ben-Sasson, Eli; Sudan, Madhu
9
2005
Optimal error correction against computationally bounded noise. Zbl 1079.94565
Micali, Silvio; Peikert, Chris; Sudan, Madhu; Wilson, David A.
5
2005
Distributed computing with imperfect randomness. Zbl 1171.68860
Goldwasser, Shafi; Sudan, Madhu; Vaikuntanathan, Vinod
3
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
5
2004
Robust locally testable codes and products of codes. Zbl 1105.68346
Ben-Sasson, Eli; Sudan, Madhu
2
2004
Probabilistically checkable proofs. Zbl 1161.68021
Sudan, Madhu
1
2004
Improved low-degree testing and its applications. Zbl 1101.68572
Arora, Sanjeev; Sudan, Madhu
26
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
17
2003
Hardness of approximating the minimum distance of a linear code. Zbl 1063.68055
Dumer, Ilya; Micciancio, Daniele; Sudan, Madhu
12
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
Hardness of approximate hypergraph coloring. Zbl 1008.68052
Guruswami, Venkatesan; Hastad, Johan; Sudan, Madhu
11
2002
Guessing secrets efficiently via list decoding. Zbl 1058.94023
Alon, Noga; Guruswami, Venkatesan; Kaufman, Tali; Sudan, Madhu
7
2002
Combinatorial bounds for list decoding. Zbl 1061.94074
Guruswami, Venkatesan; Håstad, Johan; Sudan, Madhu; Zuckerman, David
6
2002
Complexity classifications of Boolean constraint satisfaction problems. Zbl 0981.68058
Creignou, Nadia; Khanna, Sanjeev; Sudan, Madhu
93
2001
The approximability of constraint satisfaction problems. Zbl 0992.68059
Khanna, Sanjeev; Sudan, Madhu; Trevisan, Luca; Williamson, David P.
34
2001
Adversarial queuing theory. Zbl 1320.68053
Borodin, Allan; Kleinberg, Jon; Raghavan, Prabhakar; Sudan, Madhu; Williamson, David P.
33
2001
Pseudorandom generators without the XOR lemma. Zbl 1005.65006
Sudan, Madhu; Trevisan, Luca; Vadhan, Salil
31
2001
Ideal error-correcting codes: Unifying algebraic and number-theoretic algorithms. Zbl 1057.94516
Sudan, Madhu
6
2001
On representations of algebraic-geometry codes. Zbl 1002.94041
Guruswami, Venkatesan; Sudan, Madhu
4
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
3
2001
Linear-consistency testing. Zbl 1052.68122
Aumann, Yonatan; Håstad, Johan; Rabin, Michael O.; Sudan, Madhu
2
2001
Gadgets, approximation, and linear programming. Zbl 0957.68048
Trevisan, Luca; Sorkin, Gregory B.; Sudan, Madhu; Williamson, David P.
32
2000
Learning polynomials with queries: The highly noisy case. Zbl 0968.68063
Goldreich, Oded; Rubinfeld, Ronitt; Sudan, Madhu
14
2000
Chinese remaindering with errors. Zbl 1007.94026
Goldreich, Oded; Ron, Dana; Sudan, Madhu
11
2000
List decoding algorithms for certain concatenated codes. Zbl 1296.94170
Guruswami, Venkatesan; Sudan, Madhu
8
2000
Small PCPs with low query complexity. Zbl 0986.68134
Harsha, Prahladh; Sudan, Madhu
6
2000
List decoding: Algorithms and applications. Zbl 1009.94572
Sudan, Madhu
4
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
95
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
11
1999
Computational indistinguishability: A sample hierarchy. Zbl 0947.68066
Goldreich, Oded; Sudan, Madhu
1
1999
Chinese remaindering with errors. Zbl 1345.94105
Goldreich, Oded; Ron, Dana; 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
203
1998
Free bits, PCPs, and nonapproximability – towards tight results. Zbl 0912.68041
Bellare, Mihir; Goldreich, Oded; Sudan, Madhu
77
1998
Approximate graph coloring by semidefinite programming. Zbl 0904.68116
Karger, David; Motwani, Rajeev; Sudan, Madhu
77
1998
On syntactic versus computational views of approximability. Zbl 0915.68068
Khanna, Sanjeev; Motwani, Rajeev; Sudan, Madhu; Vazirani, Umesh
54
1998
Private information retrieval. Zbl 1065.68524
Chor, Benny; Goldreich, Oded; Kushilevitz, Eyal; Sudan, Madhu
54
1998
Approximating minimum feedback sets and multicuts in directed graphs. Zbl 0897.68078
Even, G.; Naor, J.; Schieber, B.; Sudan, M.
50
1998
A geometric approach to betweenness. Zbl 0912.68058
Chor, Benny; Sudan, Madhu
18
1998
Reconstructing algebraic functions from mixed data. Zbl 0915.68088
Ar, Sigal; Lipton, Richard J.; Rubinfeld, Ronitt; Sudan, Madhu
7
1998
Guaranteeing fair service to persistent dependent tasks. Zbl 0910.90174
Bar-Noy, Amotz; Mayer, Alain; Schieber, Baruch; Sudan, Madhu
3
1998
Decoding of Reed Solomon codes beyond the error-correction bound. Zbl 0872.68026
Sudan, Madhu
63
1997
Robust characterizations of polynomials with applications to program testing. Zbl 0844.68062
Rubinfeld, Ronitt; Sudan, Madhu
151
1996
Linearity testing in characteristic two. Zbl 0867.68060
Bellare, Mihir; Coppersmith, Don; Håstad, Johan; Kiwi, Marcos; Sudan, Madhu
27
1996
Priority encoding transmission. Zbl 0867.94038
Albanese, Andres; Blömer, Johannes; Edmonds, Jeff; Luby, Michael; Sudan, Madhu
9
1996
Efficient routing in optical networks. Zbl 0885.68083
Aggarwal, Alok; Bar-Noy, Amotz; Coppersmith, Don; Ramaswami, Rajiv; Schieber, Baruch; Sudan, Madhu
7
1996
Adversarial queueing theory. Zbl 0934.60079
Borodin, Allan; Kleinberg, Jon; Raghavan, Prabhakar; Sudan, Madhu; Williamson, David P.
3
1996
...and 15 more Documents
all top 5

Cited by 2,224 Authors

30 Goldreich, Oded
25 Paschos, Vangelis Th.
20 Sudan, Madhu
17 Guruswami, Venkatesan
15 Alon, Noga M.
15 Ron, Dana
12 Ben-Sasson, Eli
12 Khot, Subhash Ajit
12 Krokhin, Andrei A.
12 Rubinfeld, Ronitt
11 Bazgan, Cristina
11 Gur, Tom
10 Chen, Hubie
10 Creignou, Nadia
10 Demange, Marc
10 Escoffier, Bruno
10 Grigorescu, Elena
10 Håstad, Johan Torkel
10 Ishai, Yuval
10 Rothblum, Ron D.
9 Chiesa, Alessandro
9 Dinur, Irit
9 Feige, Uriel
9 Halldórsson, Magnús Mar
9 Kaufman, Tali
9 Shapira, Asaf
9 Trevisan, Luca
8 Bhattacharyya, Arnab
8 Shaltiel, Ronen
8 Wootters, Mary
8 Yannakakis, Mihalis
8 Yoshida, Yuichi
8 Živný, Stanislav
7 Applebaum, Benny
7 Bulatov, Andrei A.
7 Cai, Jin-Yi
7 Faria, Luerbio
7 Fischer, Eldar
7 Fox, Jacob
7 Golovach, Petr A.
7 Jeavons, Peter G.
7 Jonsson, Peter A.
7 Kopparty, Swastik
7 Kratsch, Dieter
7 Krivelevich, Michael
7 Lê Văn Băng
7 Marathe, Madhav V.
7 Paulusma, Daniël
7 Raskhodnikova, Sofya
6 Chen, Jian-er
6 Chlebus, Bogdan Stanislaw
6 Hemenway, Brett
6 Kabatiansky, Grigorii A.
6 Kann, Viggo
6 Lu, Chijen
6 Lu, Pinyan
6 Meir, Or
6 Newman, Ilan I.
6 Ravi, S. S.
6 Roberson, David E.
6 Saurabh, Saket
6 Vollmer, Heribert
6 Wigderson, Avi
6 Zuckerman, David
5 Arora, Sanjeev
5 Ausiello, Giorgio
5 Austrin, Per
5 Bar-Noy, Amotz
5 Blesa, Maria J.
5 Cooper, Martin C.
5 Fujito, Toshihiro
5 Gamarnik, David
5 Goldberg, Leslie Ann
5 Goldwasser, Shafi
5 Haviv, Ishay
5 Hell, Pavol
5 Hermann, Miki
5 Jiang, Tao
5 Levin, Asaf
5 Makarychev, Yury S.
5 Manurangsi, Pasin
5 Ostrovsky, Rafail
5 Raz, Ran
5 Serna, Maria José
5 Seshadhri, Comandur
5 Shinkar, Igor
5 Sidorenko, Vladimir R.
5 Stewart, Anthony
5 Ta-Shma, Amnon
5 Tauman Kalai, Yael
5 Vadhan, Salil P.
5 Vaikuntanathan, Vinod
5 Viderman, Michael
5 Williams, Richard Ryan
5 Zhang, Kaizhong
4 Anantharamu, Lakshmi
4 Blais, Eric
4 Blum, Avrim L.
4 Bodirsky, Manuel
4 Boyle, Elette
...and 2,124 more Authors
all top 5

Cited in 195 Serials

150 Theoretical Computer Science
73 Journal of Computer and System Sciences
65 Information Processing Letters
64 Discrete Applied Mathematics
64 Algorithmica
49 SIAM Journal on Computing
44 Computational Complexity
35 Designs, Codes and Cryptography
29 Information and Computation
27 Theory of Computing Systems
23 European Journal of Operational Research
22 Mathematical Programming. Series A. Series B
21 Random Structures & Algorithms
21 Journal of Combinatorial Optimization
15 SIAM Journal on Discrete Mathematics
15 Journal of Cryptology
14 Discrete Mathematics
14 Combinatorics, Probability and Computing
12 Information Sciences
12 Operations Research Letters
12 Combinatorica
11 Journal of Symbolic Computation
10 Distributed Computing
10 Journal of Discrete Algorithms
9 Discrete Optimization
8 Problems of Information Transmission
8 Finite Fields and their Applications
8 Quantum Information Processing
7 International Journal of Foundations of Computer Science
7 Linear Algebra and its Applications
7 Annals of Mathematics and Artificial Intelligence
7 RAIRO. Operations Research
7 ACM Transactions on Computation Theory
6 Operations Research
6 European Journal of Combinatorics
6 Journal of Complexity
6 Applicable Algebra in Engineering, Communication and Computing
6 Advances in Mathematics of Communications
5 Artificial Intelligence
5 Journal of Combinatorial Theory. Series B
5 Networks
5 Computers & Operations Research
5 Annals of Operations Research
5 Cybernetics and Systems Analysis
5 The Electronic Journal of Combinatorics
5 Journal of Machine Learning Research (JMLR)
5 4OR
5 Cryptography and Communications
4 International Journal of Theoretical Physics
4 Israel Journal of Mathematics
4 Journal of Combinatorial Theory. Series A
4 Journal of Graph Theory
4 Journal of Computer Science and Technology
4 Games and Economic Behavior
4 Bulletin of the American Mathematical Society. New Series
4 Constraints
4 Journal of Scheduling
4 Journal of the ACM
4 Journal of Statistical Mechanics: Theory and Experiment
4 Journal of Mathematical Cryptology
4 Computer Science Review
4 Prikladnaya Diskretnaya Matematika
3 Computers & Mathematics with Applications
3 Communications in Mathematical Physics
3 Algebra Universalis
3 The Annals of Probability
3 Mathematics of Operations Research
3 Discrete & Computational Geometry
3 Journal of Global Optimization
3 Geometric and Functional Analysis. GAFA
3 Journal of Mathematical Sciences (New York)
3 Journal of Zhejiang University. Science A
3 Discrete Mathematics, Algorithms and Applications
3 Algorithms
3 Theory of Computing
2 Acta Informatica
2 Mathematics of Computation
2 Advances in Mathematics
2 Automatica
2 Annals of Pure and Applied Logic
2 Probability Theory and Related Fields
2 Applied Mathematics Letters
2 Science in China. Series A
2 The Annals of Applied Probability
2 Computational Geometry
2 International Journal of Algebra and Computation
2 International Journal of Computer Mathematics
2 Annales de l’Institut Henri Poincaré. Probabilités et Statistiques
2 INFORMS Journal on Computing
2 Data Mining and Knowledge Discovery
2 Annals of Mathematics. Second Series
2 Optimization Letters
1 American Mathematical Monthly
1 Communications on Pure and Applied Mathematics
1 Jahresbericht der Deutschen Mathematiker-Vereinigung (DMV)
1 Journal of the Franklin Institute
1 Journal of Mathematical Biology
1 Journal of Mathematical Physics
1 Journal of Statistical Physics
1 Chaos, Solitons and Fractals
...and 95 more Serials
all top 5

Cited in 40 Fields

981 Computer science (68-XX)
372 Combinatorics (05-XX)
315 Information and communication theory, circuits (94-XX)
295 Operations research, mathematical programming (90-XX)
65 Number theory (11-XX)
58 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
48 Quantum theory (81-XX)
32 Mathematical logic and foundations (03-XX)
32 Probability theory and stochastic processes (60-XX)
24 Order, lattices, ordered algebraic structures (06-XX)
22 Algebraic geometry (14-XX)
21 Biology and other natural sciences (92-XX)
19 Commutative algebra (13-XX)
19 Numerical analysis (65-XX)
16 General algebraic systems (08-XX)
16 Statistics (62-XX)
15 Geometry (51-XX)
14 Linear and multilinear algebra; matrix theory (15-XX)
12 Field theory and polynomials (12-XX)
11 Convex and discrete geometry (52-XX)
9 Statistical mechanics, structure of matter (82-XX)
8 Group theory and generalizations (20-XX)
8 Systems theory; control (93-XX)
7 Dynamical systems and ergodic theory (37-XX)
5 Approximations and expansions (41-XX)
5 Functional analysis (46-XX)
4 General and overarching topics; collections (00-XX)
4 Harmonic analysis on Euclidean spaces (42-XX)
3 Abstract harmonic analysis (43-XX)
3 Operator theory (47-XX)
2 Topological groups, Lie groups (22-XX)
2 Measure and integration (28-XX)
1 History and biography (01-XX)
1 Associative rings and algebras (16-XX)
1 Real functions (26-XX)
1 Partial differential equations (35-XX)
1 Difference and functional equations (39-XX)
1 Integral transforms, operational calculus (44-XX)
1 General topology (54-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.