×

zbMATH — the first resource for mathematics

Guruswami, Venkatesan

Compute Distance To:
Author ID: guruswami.venkatesan Recent zbMATH articles by "Guruswami, Venkatesan"
Published as: Guruswami, Venkatesan; Guruswami, V.
Homepage: https://www.cs.cmu.edu/~venkatg/
External Links: MGP · ORCID · Wikidata · Google Scholar · ResearchGate · dblp · IdRef
Documents Indexed: 198 Publications since 1998, including 2 Books
all top 5

Co-Authors

20 single-authored
14 Lee, Euiwoong
14 Sudan, Madhu
12 Xing, Chaoping
11 Raghavendra, Prasad
11 Rudra, Atri
10 Brakensiek, Joshua
9 Håstad, Johan Torkel
8 Wang, Carol J.
7 Sinop, Ali Kemal
6 Charikar, Moses S.
6 Cheraghchi, Mahdi
6 Indyk, Piotr
6 Khanna, Sanjeev
5 Gopalan, Parikshit
5 Saket, Rishi
5 Velingker, Ameya
5 Wu, Yi
5 Zhou, Yuan
4 Li, Ray
4 Rangan, Chandrasekharan Pandu
4 Yuan, Chen
3 Bhattiprolu, Vijay V. S. P.
3 Dinur, Irit
3 Gopi, Sivakanth
3 Kaufman, Tali
3 Khot, Subhash Ajit
3 Kopparty, Swastik
3 Narayanan, Srivatsan
3 Regev, Oded
3 Vadhan, Salil P.
3 Wootters, Mary
2 Alon, Noga M.
2 Błasiok, Jarosław
2 Bukh, Boris
2 Canonne, Clement Louis
2 Chang, Gerard Jennhwa
2 Chang, Maw-Shang
2 Chuzhoy, Julia
2 Engebretsen, Lars
2 Fagin, Ronald
2 Feldman, Vitaly
2 Giotis, Ioannis
2 Harsha, Prahladh
2 Jin, Lingfei
2 Kabanets, Valentine
2 Kleinberg, Jon Michael
2 Lee, James R.
2 Lipton, Richard J.
2 Meka, Raghu
2 Radhakrishnan, Jaikumar
2 Raghavan, Prabhakar
2 Rajaraman, Rajmohan
2 Rawat, Ankit Singh
2 Shepherd, Bruce
2 Srinivasan, Srikanth
2 Talwar, Kunal
2 Tulsiani, Madhur
2 Vardy, Alexander
2 Varma, Girish
2 Wirth, Anthony
2 Wong, Chak-Kuen
2 Yannakakis, Mihalis
2 Yekhanin, Sergey
2 Zbarsky, Samuel
1 Alrabiah, Omar
1 Andrews, Matthew T.
1 Austrin, Per
1 Bateni, MohammadHossein
1 Ben-Sasson, Eli
1 Bhaskara, Aditya
1 Chakrabarti, Amit
1 Cohen, Edith
1 Dalai, Marco
1 Dodis, Yevgeniy
1 Efremenko, Klim
1 Forbes, Michael A.
1 Frank-Fischer, S. Luna
1 Ghosh, Mrinalkanti
1 Haeupler, Bernhard
1 Hartline, Jason D.
1 Karlin, Anna R.
1 Kempe, David
1 Kenyon, Claire M.
1 Lokam, Satyanarayana V.
1 Mani Jayaraman, Sai Vikneshwar
1 Manokaran, Rajsekar
1 McSherry, Frank
1 Micciancio, Daniele
1 Nakkiran, Preetum
1 O’Donnell, Ryan
1 Onak, Krzysztof
1 Patthak, Anindya C.
1 Popat, Preyas
1 Razborov, Aleksandr Aleksandrovich
1 Resch, Nicolas
1 Riazanov, Andrii
1 Sachdeva, Sushant
1 Sahai, Amit
1 Sandeep, Sai
1 Shahrasbi, Amirbehshad
...and 15 more Co-Authors

Publications by Year

Citations contained in zbMATH Open

150 Publications have been cited 983 times in 711 Documents Cited by Year
Improved decoding of Reed-Solomon and algebraic-geometry codes. Zbl 0958.94036
Guruswami, Venkatesan; Sudan, Madhu
95
1999
On profit-maximizing envy-free pricing. Zbl 1297.91072
Guruswami, Venkatesan; Hartline, Jason D.; Karlin, Anna R.; Kempe, David; Kenyon, Claire; McSherry, Frank
65
2005
Clustering with qualitative information. Zbl 1094.68075
Charikar, Moses; Guruswami, Venkatesan; Wirth, Anthony
49
2005
Algorithmic aspects of clique-transversal and clique-independent sets. Zbl 0948.68135
Guruswami, Venkatesan; Rangan, C. Pandu
41
2000
Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. Zbl 1325.68169
Guruswami, Venkatesan; Umans, Christopher; Vadhan, Salil
37
2009
A new multilayered PCP and the hardness of hypergraph vertex cover. Zbl 1079.68039
Dinur, Irit; Guruswami, Venkatesan; Khot, Subhash; Regev, Oded
36
2005
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Zbl 1114.68430
Guruswami, Venkatesan; Khanna, Sanjeev; Rajaraman, Rajmohan; Shepherd, Bruce; Yannakakis, Mihalis
28
2003
List decoding of error-correcting codes. Winning thesis of the 2002 ACM Doctoral Dissertation Competition. Zbl 1075.94001
Guruswami, Venkatesan
19
2004
Explicit codes achieving list decoding capacity: error-correction with optimal redundancy. Zbl 1205.94125
Guruswami, Venkatesan; Rudra, Atri
19
2008
Non-malleable coding against bit-wise and split-state tampering. Zbl 1326.94080
Cheraghchi, Mahdi; Guruswami, Venkatesan
18
2014
Lasserre hierarchy, higher eigenvalues, and approximation schemes for graphs partitioning and quadratic integer programming with PSD objectives (extended abstract). Zbl 1292.90222
Guruswami, Venkatesan; Sinop, Ali Kemal
17
2011
MaxMin Allocation via degree lower-bounded arborescences. Zbl 1304.91143
Bateni, MohammadHossein; Charikar, Moses; Guruswami, Venkatesan
17
2009
List decoding Reed-Solomon, algebraic-geometric, and Gabidulin subcodes up to the singleton bound. Zbl 1293.94110
Guruswami, Venkatesan; Xing, Chaoping
15
2013
Beating the random ordering is hard: every ordering CSP is approximation resistant. Zbl 1235.68075
Guruswami, Venkatesan; Håstad, Johan; Manokaran, Rajsekar; Raghavendra, Prasad; Charikar, Moses
15
2011
Correlation clustering with a fixed number of clusters. Zbl 1213.68704
Giotis, Ioannis; Guruswami, Venkatesan
14
2006
Maximum-likelihood decoding of Reed-Solomon codes is NP-hard. Zbl 1310.94210
Guruswami, Venkatesan; Vardy, Alexander
13
2005
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Zbl 1346.68102
Guruswami, Venkatesan; Khanna, Sanjeev; Rajaraman, Rajmohan; Shepherd, Bruce; Yannakakis, Mihalis
13
1999
Capacity of non-malleable codes. Zbl 1366.68042
Cheraghchi, Mahdi; Guruswami, Venkatesan
12
2014
Restricted isometry of Fourier matrices and list decodability of random linear codes. Zbl 1321.94122
Cheraghchi, Mahdi; Guruswami, Venkatesan; Velingker, Ameya
11
2013
Query strategies for priced information. Zbl 1015.68244
Charikar, Moses; Fagin, Ronald; Guruswami, Venkatesan; Kleinberg, Jon; Raghavan, Prabhakar
11
2002
Hardness of approximate hypergraph coloring. Zbl 1008.68052
Guruswami, Venkatesan; Hastad, Johan; Sudan, Madhu
11
2002
A new multilayered {PCP} and the hardness of hypergraph vertex cover. Zbl 1192.68290
Dinur, Irit; Guruswami, Venkatesan; Khot, Subhash; Regev, Oded
11
2003
Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Zbl 1240.68113
Andrews, Matthew; Chuzhoy, Julia; Guruswami, Venkatesan; Khanna, Sanjeev; Talwar, Kunal; Zhang, Lisa
11
2010
The complexity of the covering radius problem. Zbl 1085.68063
Guruswami, Venkatesan; Micciancio, Daniele; Regev, Oded
10
2005
On the hardness of 4-coloring a 3-colorable graph. Zbl 1087.68071
Guruswami, Venkatesan; Khanna, Sanjeev
10
2004
Maximum cut on line and total graphs. Zbl 0935.68082
Guruswami, Venkatesan
10
1999
Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph. Zbl 1423.68202
Bhaskara, Aditya; Charikar, Moses; Vijayaraghavan, Aravindan; Guruswami, Venkatesan; Zhou, Yuan
10
2012
List decoding from erasures: bounds and code constructions. Zbl 1301.94156
Guruswami, Venkatesan
9
2003
Linear-time encodable/decodable codes with near-optimal rate. Zbl 1310.94209
Guruswami, Venkatesan; Indyk, Piotr
9
2005
List decoding algorithms for certain concatenated codes. Zbl 1296.94170
Guruswami, Venkatesan; Sudan, Madhu
8
2000
The vertex-disjoint triangles problem. Zbl 0918.68081
Guruswami, Venkatesan; Rangan, C. Pandu; Chang, M. S.; Chang, G. J.; Wong, C. K.
8
1998
Locally testable codes require redundant testers. Zbl 1209.68265
Ben-Sasson, Eli; Guruswami, Venkatesan; Kaufman, Tali; Sudan, Madhu; Viderman, Michael
8
2010
Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy. Zbl 1403.68074
Brakensiek, Joshua; Guruswami, Venkatesan
8
2018
Embeddings and non-approximability of geometric problems. Zbl 1092.68690
Guruswami, Venkatesan; Indyk, Piotr
7
2003
Folded codes from function field towers and improved optimal rate list decoding. Zbl 1286.94111
Guruswami, Venkatesan; Xing, Chaoping
7
2012
Linear-algebraic list decoding for variants of Reed-Solomon codes. Zbl 1364.94607
Guruswami, Venkatesan; Wang, Carol
7
2013
Guessing secrets efficiently via list decoding. Zbl 1058.94023
Alon, Noga; Guruswami, Venkatesan; Kaufman, Tali; Sudan, Madhu
7
2002
Agnostic learning of monomials by halfspaces is hard. Zbl 1261.68063
Feldman, Vitaly; Guruswami, Venkatesan; Raghavendra, Prasad; Wu, Yi
7
2012
Correlation clustering with a fixed number of clusters. Zbl 1194.62087
Giotis, Ioannis; Guruswami, Venkatesan
7
2006
Optimal column-based low-rank matrix reconstruction. Zbl 1421.68227
Guruswami, Venkatesan; Sinop, Ali Kemal
7
2012
Hardness of routing with congestion in directed graphs. Zbl 1232.68062
Chuzhoy, Julia; Guruswami, Venkatesan; Khanna, Sanjeev; Talwar, Kunal
6
2007
Explicit subspace designs. Zbl 1389.51003
Guruswami, Venkatesan; Kopparty, Swastik
6
2016
Inapproximability of \(H\)-transversal/packing. Zbl 1375.68059
Guruswami, Venkatesan; Lee, Euiwoong
6
2015
The \(K_r\)-packing problem. Zbl 0978.05060
Guruswami, V.; Pandu Rangan, C.; Chang, M. S.; Chang, G. J.; Wong, C. K.
6
2001
Combinatorial bounds for list decoding. Zbl 1061.94074
Guruswami, Venkatesan; Håstad, Johan; Sudan, Madhu; Zuckerman, David
6
2002
Superlinear lower bounds for multipass graph processing. Zbl 1353.68084
Guruswami, Venkatesan; Onak, Krzysztof
6
2016
Hardness of learning halfspaces with noise. Zbl 1198.68157
Guruswami, Venkatesan; Raghavendra, Prasad
6
2009
\((2+\varepsilon)\)-Sat is NP-hard. Zbl 06786785
Austrin, Per; Guruswami, Venkatesan; Håstad, Johan
6
2017
New hardness results for graph and hypergraph colorings. Zbl 1380.68190
Brakensiek, Joshua; Guruswami, Venkatesan
6
2016
Cyclotomic function fields, Artin-Frobenius automorphisms, and list error correction with optimal rate. Zbl 1206.94113
Guruswami, Venkatesan
6
2010
PCPs via the low-degree long code and hardness for constrained hypergraph coloring. Zbl 1330.68091
Dinur, Irit; Guruswami, Venkatesan
5
2015
Constructions of codes from number fields. Zbl 1063.94110
Guruswami, Venkatesan
5
2003
Inapproximability results for set splitting and satisfiability problems with no mixed clauses. Zbl 1095.68036
Guruswami, Venkatesan
5
2004
Linear time encodable and list decodable codes. Zbl 1192.94097
Guruswami, Venkatesan; Indyk, Piotr
5
2003
Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set. Zbl 1255.68303
Guruswami, Venkatesan; Zhou, Yuan
5
2012
The complexity of making unique choices: approximating 1-in-\(k\) SAT. Zbl 1142.68611
Guruswami, Venkatesan; Trevisan, Luca
4
2005
Agnostic learning of monomials by halfspaces is hard. Zbl 1292.68097
Feldman, Vitaly; Guruswami, Venkatesan; Raghavendra, Prasad; Wu, Yi
4
2009
Enumerative aspects of certain subclasses of perfect graphs. Zbl 0936.05058
Guruswami, Venkatesan
4
1999
On representations of algebraic-geometry codes. Zbl 1002.94041
Guruswami, Venkatesan; Sudan, Madhu
4
2001
How long can optimal locally repairable codes be? Zbl 1432.94213
Guruswami, Venkatesan; Xing, Chaoping; Yuan, Chen
4
2019
Explicit capacity-achieving list-decodable codes. Zbl 1301.94157
Guruswami, Venkatesan; Rudra, Atri
4
2006
Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. Zbl 1192.94132
Guruswami, Venkatesan; Indyk, Piotr
4
2002
On the inapproximability of Vertex Cover on \(k\)-partite \(k\)-uniform hypergraphs. Zbl 1288.68093
Guruswami, Venkatesan; Saket, Rishi
4
2010
List decoding tensor products and interleaved codes. Zbl 1235.94073
Gopalan, Parikshit; Guruswami, Venkatesan; Raghavendra, Prasad
4
2011
Strong inapproximability results on balanced rainbow-colorable hypergraphs. Zbl 1371.68208
Guruswami, Venkatesan; Lee, Euiwoong
4
2015
Tolerant locally testable codes. Zbl 1105.68347
Guruswami, Venkatesan; Rudra, Atri
3
2005
Algorithmic results in list decoding. Zbl 1203.94139
Guruswami, Venkatesan
3
2006
On 2-query codeword testing with near-perfect completeness. Zbl 1135.68441
Guruswami, Venkatesan
3
2006
Euclidean sections of \(\ell_1^N\) with sublinear randomness and error-correction over the reals. Zbl 1159.68038
Guruswami, Venkatesan; Lee, James R.; Wigderson, Avi
3
2008
Maximum-likelihood decoding of Reed-Solomon codes is NP-hard. Zbl 1297.94128
Guruswami, Venkatesan; Vardy, Alexander
3
2005
The 2-catalog segmentation problem. Zbl 0937.68157
Dodis, Yevgeniy; Guruswami, Venkatesan; Khanna, Sanjeev
3
1999
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. Zbl 1315.05052
Guruswami, Venkatesan; Harsha, Prahladh; Håstad, Johan; Srinivasan, Srikanth; Varma, Girish
3
2014
Inapproximability results for set splitting and satisfiability problems with no mixed clauses. Zbl 0976.68075
Guruswami, Venkatesan
3
2000
Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets (extended abstract). Zbl 1423.94174
Guruswami, Venkatesan; Xing, Chaoping
3
2014
Optimal rate list decoding via derivative codes. Zbl 1343.94101
Guruswami, Venkatesan; Wang, Carol
3
2011
Better extractors for better codes? Zbl 1192.68363
Guruswami, Venkatesan
3
2004
Bridging Shannon and Hamming: list error-correction with optimal rate. Zbl 1230.94013
Guruswami, Venkatesan
3
2011
Hardness amplification within NP against deterministic algorithms. Zbl 1214.68171
Gopalan, Parikshit; Guruswami, Venkatesan
3
2011
The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number. Zbl 1376.68054
Guruswami, Venkatesan; Sinop, Ali Kemal
3
2011
A lower bound on list size for list decoding. Zbl 1142.94395
Guruswami, Venkatesan; Vadhan, Salil
2
2005
Constraint satisfaction over a non-Boolean domain: Approximation algorithms and unique-games hardness. Zbl 1159.68665
Guruswami, Venkatesan; Raghavendra, Prasad
2
2008
Limits to list decoding Reed-Solomon codes. Zbl 1283.94139
Guruswami, Venkatesan; Rudra, Atri
2
2006
A 3-query PCP over integers. Zbl 1232.68065
Guruswami, Venkatesan; Raghavendra, Prasad
2
2007
Improved inapproximability results for maximum \(k\)-colorable subgraph. Zbl 1448.68246
Guruswami, Venkatesan; Sinop, Ali Kemal
2
2013
Optimal rate algebraic list decoding using narrow ray class fields. Zbl 1361.94066
Guruswami, Venkatesan; Xing, Chaoping
2
2015
A lower bound on list size for list decoding. Zbl 1366.94701
Guruswami, Venkatesan; Vadhan, Salil
2
2010
Inapproximability of \(H\)-transversal/packing. Zbl 1371.68099
Guruswami, Venkatesan; Lee, Euiwoong
2
2017
Approximate hypergraph coloring under low-discrepancy and related promises. Zbl 1375.05085
Bhattiprolu, Vijay V. S. P.; Guruswami, Venkatesan; Lee, Euiwoong
2
2015
Dimension expanders via rank condensers. Zbl 1375.68086
Forbes, Michael A.; Guruswami, Venkatesan
2
2015
Linear-time list decoding in error-free settings (extended abstract). Zbl 1099.94522
Guruswami, Venkatesan; Indyk, Piotr
2
2004
List decoding from erasures: Bounds and code constructions. Zbl 1052.94505
Guruswami, Venkatesan
2
2001
Is constraint satisfaction over two variables always easy? Zbl 1077.68094
Engebretsen, Lars; Guruswami, Venkatesan
2
2004
Subspace designs based on algebraic function fields. Zbl 1397.05031
Guruswami, Venkatesan; Xing, Chaoping; Yuan, Chen
2
2018
Bypassing UGC from some optimal geometric inapproximability results. Zbl 1398.68194
Guruswami, Venkatesan; Raghavendra, Prasad; Saket, Rishi; Wu, Yi
2
2016
An algorithmic blend of LPs and ring equations for promise CSPs. Zbl 1431.68043
Brakensiek, Joshua; Guruswami, Venkatesan
2
2019
Restricted isometry of Fourier matrices and list decodability of random linear codes. Zbl 1440.94105
Cheraghchi, Mahdi; Guruswami, Venkatesan; Velingker, Ameya
2
2013
List decoding subspace codes from insertions and deletions. Zbl 1348.94103
Guruswami, Venkatesan; Narayanan, Srivatsan; Wang, Carol
2
2012
Hardness amplification via space-efficient direct products. Zbl 1188.68152
Guruswami, Venkatesan; Kabanets, Valentine
2
2008
Almost Euclidean subspaces of \(l^N_1\) via expander codes. Zbl 1192.68745
Guruswami, Venkatesan; Lee, James R.; Razborov Alexander
2
2008
Limits to list decoding Reed-Solomon codes. Zbl 1192.94134
Guruswami, Venkatesan; Rudra, Atri
2
2005
An improved bound on the zero-error list-decoding capacity of the 4/3 channel. Zbl 1434.94048
Dalai, Marco; Guruswami, Venkatesan; Radhakrishnan, Jaikumar
1
2020
The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems. Zbl 07282219
Brakensiek, Joshua; Guruswami, Venkatesan; Wrochna, Marcin; Živný, Stanislav
1
2020
Maximally recoverable LRCs: a field size lower bound and constructions for few heavy parities. Zbl 1452.94113
Gopi, Sivakanth; Guruswami, Venkatesan; Yekhanin, Sergey
1
2020
How long can optimal locally repairable codes be? Zbl 1432.94213
Guruswami, Venkatesan; Xing, Chaoping; Yuan, Chen
4
2019
An algorithmic blend of LPs and ring equations for promise CSPs. Zbl 1431.68043
Brakensiek, Joshua; Guruswami, Venkatesan
2
2019
Approximability of \(p\rightarrow q\) matrix norms: generalized Krivine rounding and hypercontractive hardness. Zbl 1431.68041
Bhattiprolu, Vijay; Ghosh, Mrinalkanti; Guruswami, Venkatesan; Lee, Euiwoong; Tulsiani, Madhur
1
2019
Bridging between 0/1 and linear programming via random walks. Zbl 1433.68156
Brakensiek, Joshua; Guruswami, Venkatesan
1
2019
Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy. Zbl 1403.68074
Brakensiek, Joshua; Guruswami, Venkatesan
8
2018
Subspace designs based on algebraic function fields. Zbl 1397.05031
Guruswami, Venkatesan; Xing, Chaoping; Yuan, Chen
2
2018
Lossless dimension expanders via linearized polynomials and subspace designs. Zbl 1441.68037
Guruswami, Venkatesan; Resch, Nicolas; Xing, Chaoping
1
2018
Strong inapproximability results on balanced rainbow-colorable hypergraphs. Zbl 1424.05087
Guruswami, Venkatesan; Lee, Euiwoong
1
2018
\((2+\varepsilon)\)-Sat is NP-hard. Zbl 06786785
Austrin, Per; Guruswami, Venkatesan; Håstad, Johan
6
2017
Inapproximability of \(H\)-transversal/packing. Zbl 1371.68099
Guruswami, Venkatesan; Lee, Euiwoong
2
2017
Non-malleable coding against bit-wise and split-state tampering. Zbl 1370.94497
Cheraghchi, Mahdi; Guruswami, Venkatesan
2
2017
Repairing Reed-Solomon codes. Zbl 1374.94829
Guruswami, Venkatesan; Wootters, Mary
2
2017
An improved bound on the fraction of correctable deletions. Zbl 1359.94907
Bukh, Boris; Guruswami, Venkatesan; Håstad, Johan
1
2017
Nearly optimal NP-hardness of unique coverage. Zbl 1371.68098
Guruswami, Venkatesan; Lee, Euiwoong
1
2017
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. Zbl 1359.68104
Guruswami, Venkatesan; Harsha, Prahladh; Håstad, Johan; Srinivasan, Srikanth; Varma, Girish
1
2017
Explicit subspace designs. Zbl 1389.51003
Guruswami, Venkatesan; Kopparty, Swastik
6
2016
Superlinear lower bounds for multipass graph processing. Zbl 1353.68084
Guruswami, Venkatesan; Onak, Krzysztof
6
2016
New hardness results for graph and hypergraph colorings. Zbl 1380.68190
Brakensiek, Joshua; Guruswami, Venkatesan
6
2016
Bypassing UGC from some optimal geometric inapproximability results. Zbl 1398.68194
Guruswami, Venkatesan; Raghavendra, Prasad; Saket, Rishi; Wu, Yi
2
2016
Explicit list-decodable rank-metric and subspace codes via subspace designs. Zbl 1359.94797
Guruswami, Venkatesan; Wang, Carol; Xing, Chaoping
2
2016
Capacity of non-malleable codes. Zbl 1359.94884
Cheraghchi, Mahdi; Guruswami, Venkatesan
2
2016
Repairing Reed-Solomon codes. Zbl 1377.94074
Guruswami, Venkatesan; Wootters, Mary
1
2016
Nearly optimal NP-hardness of unique coverage. Zbl 1411.68189
Guruswami, Venkatesan; Lee, Euiwoong
1
2016
Efficient low-redundancy codes for correcting multiple deletions. Zbl 1415.94477
Brakensiek, Joshua; Guruswami, Venkatesan; Zbarsky, Samuel
1
2016
Optimal rate code constructions for computationally simple channels. Zbl 1407.94009
Guruswami, Venkatesan; Smith, Adam
1
2016
Simple proof of hardness of feedback vertex set. Zbl 1343.68095
Guruswami, Venkatesan; Lee, Euiwoong
1
2016
Complexity of approximating CSP with balance/hard constraints. Zbl 1350.68142
Guruswami, Venkatesan; Lee, Euiwoong
1
2016
Inapproximability of \(H\)-transversal/packing. Zbl 1375.68059
Guruswami, Venkatesan; Lee, Euiwoong
6
2015
PCPs via the low-degree long code and hardness for constrained hypergraph coloring. Zbl 1330.68091
Dinur, Irit; Guruswami, Venkatesan
5
2015
Strong inapproximability results on balanced rainbow-colorable hypergraphs. Zbl 1371.68208
Guruswami, Venkatesan; Lee, Euiwoong
4
2015
Optimal rate algebraic list decoding using narrow ray class fields. Zbl 1361.94066
Guruswami, Venkatesan; Xing, Chaoping
2
2015
Approximate hypergraph coloring under low-discrepancy and related promises. Zbl 1375.05085
Bhattiprolu, Vijay V. S. P.; Guruswami, Venkatesan; Lee, Euiwoong
2
2015
Dimension expanders via rank condensers. Zbl 1375.68086
Forbes, Michael A.; Guruswami, Venkatesan
2
2015
Inapproximability of minimum vertex cover on \(k\)-uniform \(k\)-partite hypergraphs. Zbl 1331.68089
Guruswami, Venkatesan; Sachdeva, Sushant; Saket, Rishi
1
2015
Communication with imperfectly shared randomness. Zbl 1364.68192
Canonne, Clement Louis; Guruswami, Venkatesan; Meka, Raghu; Sudan, Madhu
1
2015
Towards a characterization of approximation resistance for symmetric CSPs. Zbl 1375.68103
Guruswami, Venkatesan; Lee, Euiwoong
1
2015
Non-malleable coding against bit-wise and split-state tampering. Zbl 1326.94080
Cheraghchi, Mahdi; Guruswami, Venkatesan
18
2014
Capacity of non-malleable codes. Zbl 1366.68042
Cheraghchi, Mahdi; Guruswami, Venkatesan
12
2014
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. Zbl 1315.05052
Guruswami, Venkatesan; Harsha, Prahladh; Håstad, Johan; Srinivasan, Srikanth; Varma, Girish
3
2014
Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets (extended abstract). Zbl 1423.94174
Guruswami, Venkatesan; Xing, Chaoping
3
2014
Evading subspaces over large fields and explicit list-decodable rank-metric codes. Zbl 1359.94852
Guruswami, Venkatesan; Wang, Carol
2
2014
Combinatorial limitations of average-radius list-decoding. Zbl 1360.94436
Guruswami, Venkatesan; Narayanan, Srivatsan
1
2014
Complexity of approximating CSP with balance/hard constraints. Zbl 1364.68229
Guruswami, Venkatesan; Lee, Euiwoong
1
2014
Constant factor Lasserre integrality gaps for graph partitioning problems. Zbl 1327.90258
Guruswami, Venkatesan; Sinop, Ali Kemal; Zhou, Yuan
1
2014
List decoding Reed-Solomon, algebraic-geometric, and Gabidulin subcodes up to the singleton bound. Zbl 1293.94110
Guruswami, Venkatesan; Xing, Chaoping
15
2013
Restricted isometry of Fourier matrices and list decodability of random linear codes. Zbl 1321.94122
Cheraghchi, Mahdi; Guruswami, Venkatesan; Velingker, Ameya
11
2013
Linear-algebraic list decoding for variants of Reed-Solomon codes. Zbl 1364.94607
Guruswami, Venkatesan; Wang, Carol
7
2013
Improved inapproximability results for maximum \(k\)-colorable subgraph. Zbl 1448.68246
Guruswami, Venkatesan; Sinop, Ali Kemal
2
2013
Restricted isometry of Fourier matrices and list decodability of random linear codes. Zbl 1440.94105
Cheraghchi, Mahdi; Guruswami, Venkatesan; Velingker, Ameya
2
2013
Approximating non-uniform sparsest cut via generalized spectra. Zbl 1423.90223
Guruswami, Venkatesan; Sinop, Ali Kemal
1
2013
Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph. Zbl 1423.68202
Bhaskara, Aditya; Charikar, Moses; Vijayaraghavan, Aravindan; Guruswami, Venkatesan; Zhou, Yuan
10
2012
Folded codes from function field towers and improved optimal rate list decoding. Zbl 1286.94111
Guruswami, Venkatesan; Xing, Chaoping
7
2012
Agnostic learning of monomials by halfspaces is hard. Zbl 1261.68063
Feldman, Vitaly; Guruswami, Venkatesan; Raghavendra, Prasad; Wu, Yi
7
2012
Optimal column-based low-rank matrix reconstruction. Zbl 1421.68227
Guruswami, Venkatesan; Sinop, Ali Kemal
7
2012
Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set. Zbl 1255.68303
Guruswami, Venkatesan; Zhou, Yuan
5
2012
List decoding subspace codes from insertions and deletions. Zbl 1348.94103
Guruswami, Venkatesan; Narayanan, Srivatsan; Wang, Carol
2
2012
Bypassing UGC from some optimal geometric inapproximability results. Zbl 1421.68062
Guruswami, Venkatesan; Raghavendra, Prasad; Saket, Rishi; Wu, Yi
2
2012
Approximating bounded occurrence ordering CSPs. Zbl 1372.68298
Guruswami, Venkatesan; Zhou, Yuan
1
2012
Lasserre hierarchy, higher eigenvalues, and approximation schemes for graphs partitioning and quadratic integer programming with PSD objectives (extended abstract). Zbl 1292.90222
Guruswami, Venkatesan; Sinop, Ali Kemal
17
2011
Beating the random ordering is hard: every ordering CSP is approximation resistant. Zbl 1235.68075
Guruswami, Venkatesan; Håstad, Johan; Manokaran, Rajsekar; Raghavendra, Prasad; Charikar, Moses
15
2011
List decoding tensor products and interleaved codes. Zbl 1235.94073
Gopalan, Parikshit; Guruswami, Venkatesan; Raghavendra, Prasad
4
2011
Optimal rate list decoding via derivative codes. Zbl 1343.94101
Guruswami, Venkatesan; Wang, Carol
3
2011
Bridging Shannon and Hamming: list error-correction with optimal rate. Zbl 1230.94013
Guruswami, Venkatesan
3
2011
Hardness amplification within NP against deterministic algorithms. Zbl 1214.68171
Gopalan, Parikshit; Guruswami, Venkatesan
3
2011
The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number. Zbl 1376.68054
Guruswami, Venkatesan; Sinop, Ali Kemal
3
2011
Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set. Zbl 1377.68094
Guruswami, Venkatesan; Zhou, Yuan
2
2011
Soft decoding, dual BCH codes, and better list-decodable \(\epsilon\)-biased codes. Zbl 1366.94700
Guruswami, Venkatesan; Rudra, Atri
1
2011
On the list-decodability of random linear codes. Zbl 1366.94699
Guruswami, Venkatesan; Håstad, Johan; Kopparty, Swastik
1
2011
Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Zbl 1240.68113
Andrews, Matthew; Chuzhoy, Julia; Guruswami, Venkatesan; Khanna, Sanjeev; Talwar, Kunal; Zhang, Lisa
11
2010
Locally testable codes require redundant testers. Zbl 1209.68265
Ben-Sasson, Eli; Guruswami, Venkatesan; Kaufman, Tali; Sudan, Madhu; Viderman, Michael
8
2010
Cyclotomic function fields, Artin-Frobenius automorphisms, and list error correction with optimal rate. Zbl 1206.94113
Guruswami, Venkatesan
6
2010
On the inapproximability of Vertex Cover on \(k\)-partite \(k\)-uniform hypergraphs. Zbl 1288.68093
Guruswami, Venkatesan; Saket, Rishi
4
2010
A lower bound on list size for list decoding. Zbl 1366.94701
Guruswami, Venkatesan; Vadhan, Salil
2
2010
SDP gaps for 2-to-1 and other Label-Cover variants. Zbl 1288.68092
Guruswami, Venkatesan; Khot, Subhash; O’Donnell, Ryan; Popat, Preyas; Tulsiani, Madhur; Wu, Yi
1
2010
Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. Zbl 1325.68169
Guruswami, Venkatesan; Umans, Christopher; Vadhan, Salil
37
2009
MaxMin Allocation via degree lower-bounded arborescences. Zbl 1304.91143
Bateni, MohammadHossein; Charikar, Moses; Guruswami, Venkatesan
17
2009
Hardness of learning halfspaces with noise. Zbl 1198.68157
Guruswami, Venkatesan; Raghavendra, Prasad
6
2009
Agnostic learning of monomials by halfspaces is hard. Zbl 1292.68097
Feldman, Vitaly; Guruswami, Venkatesan; Raghavendra, Prasad; Wu, Yi
4
2009
Better binary list decodable codes via multilevel concatenation. Zbl 1367.94424
Guruswami, Venkatesan; Rudra, Atri
1
2009
List decoding tensor products and interleaved codes. Zbl 1304.94119
Gopalan, Parikshit; Guruswami, Venkatesan; Raghavendra, Prasad
1
2009
Artin automorphisms, cyclotomic function fields, and folded list-decodable codes. Zbl 1304.94116
Guruswami, Venkatesan
1
2009
List decoding of binary codes – a brief survey of some recent results. Zbl 1248.94123
Guruswami, Venkatesan
1
2009
Improved inapproximability results for maximum \(k\)-colorable subgraph. Zbl 1255.68072
Guruswami, Venkatesan; Sinop, Ali Kemal
1
2009
Explicit codes achieving list decoding capacity: error-correction with optimal redundancy. Zbl 1205.94125
Guruswami, Venkatesan; Rudra, Atri
19
2008
Euclidean sections of \(\ell_1^N\) with sublinear randomness and error-correction over the reals. Zbl 1159.68038
Guruswami, Venkatesan; Lee, James R.; Wigderson, Avi
3
2008
Constraint satisfaction over a non-Boolean domain: Approximation algorithms and unique-games hardness. Zbl 1159.68665
Guruswami, Venkatesan; Raghavendra, Prasad
2
2008
Hardness amplification via space-efficient direct products. Zbl 1188.68152
Guruswami, Venkatesan; Kabanets, Valentine
2
2008
Almost Euclidean subspaces of \(l^N_1\) via expander codes. Zbl 1192.68745
Guruswami, Venkatesan; Lee, James R.; Razborov Alexander
2
2008
Correlated algebraic-geometric codes: improved list decoding over bounded alphabets. Zbl 1150.94013
Guruswami, Venkatesan; Patthak, Anindya C.
1
2008
Algorithms for modular counting of roots of multivariate polynomials. Zbl 1143.11046
Gopalan, Parikshit; Guruswami, Venkatesan; Lipton, Richard J.
1
2008
Concatenated codes can achieve list-decoding capacity. Zbl 1192.94133
Guruswami, Venkatesan; Rudra, Atri
1
2008
Hardness of routing with congestion in directed graphs. Zbl 1232.68062
Chuzhoy, Julia; Guruswami, Venkatesan; Khanna, Sanjeev; Talwar, Kunal
6
2007
A 3-query PCP over integers. Zbl 1232.68065
Guruswami, Venkatesan; Raghavendra, Prasad
2
2007
Guessing secrets efficiently via list decoding. Zbl 1446.94201
Alon, Noga; Guruswami, Venkatesan; Kaufman, Tali; Sudan, Madhu
1
2007
Correlation clustering with a fixed number of clusters. Zbl 1213.68704
Giotis, Ioannis; Guruswami, Venkatesan
14
2006
Correlation clustering with a fixed number of clusters. Zbl 1194.62087
Giotis, Ioannis; Guruswami, Venkatesan
7
2006
Explicit capacity-achieving list-decodable codes. Zbl 1301.94157
Guruswami, Venkatesan; Rudra, Atri
4
2006
...and 50 more Documents
all top 5

Cited by 1,218 Authors

28 Guruswami, Venkatesan
15 Durán, Guillermo Alfredo
11 Bonomo-Braberman, Flavia
10 Shan, Erfang
9 Shaltiel, Ronen
7 Grigoriev, Alexander
7 Kang, Liying
7 Liang, Zuosong
7 Saurabh, Saket
7 Sidorenko, Vladimir R.
6 Haviv, Ishay
6 Kabatiansky, Grigorii A.
6 Laber, Eduardo Sany
6 Lee, Chuan-Min
6 Lin, Min Chih
6 Safe, Martín Darío
6 Venturi, Daniele
5 Alon, Noga M.
5 Ben-Sasson, Eli
5 Cicalese, Ferdinando
5 Flammini, Michele
5 Joret, Gwenaël
5 Khot, Subhash Ajit
5 Lee, Euiwoong
5 Mastrolilli, Monaldo
5 Saket, Rishi
5 Sitters, Rene A.
5 Sudan, Madhu
5 Ta-Shma, Amnon
4 Bartz, Hannes
4 Bourgain, Jean
4 Cao, Yixin
4 Chekuri, Chandra S.
4 Cheraghchi, Mahdi
4 Chlamtac, Eden
4 Dachman-Soled, Dana
4 Deng, Xiao-Tie
4 Dodis, Yevgeniy
4 Fiorini, Samuel
4 Geil, Olav
4 Goldreich, Oded
4 Grigorescu, Elena
4 Karpinski, Marek
4 Kopparty, Swastik
4 Kurpisz, Adam
4 Labbé, Martine V.
4 Lovett, Shachar
4 Manurangsi, Pasin
4 Rawitz, Dror
4 Regev, Oded
4 Ruano, Diego
4 Rudra, Atri
4 Soulignac, Francisco Juan
4 Sueiro, Gabriel
4 Szwarcfiter, Jayme Luiz
4 Uetz, Marc
4 Umans, Christopher
4 van Loon, Joyce
4 Wachter-Zeh, Antonia
4 Wagler, Annegret Katrin
4 Wootters, Mary
4 Xu, Dachuan
4 Zuckerman, David
3 Aggarwal, Divesh
3 Avidor, Adi
3 Bansal, Nikhil
3 Berger, André
3 Bernstein, Daniel Julius
3 Bhangale, Amey
3 Bilò, Vittorio
3 Brakensiek, Joshua
3 Briest, Patrick
3 Chandrasekaran, Karthekeyan
3 Chang, Maw-Shang
3 Chen, Jian-er
3 Chen, Ning
3 Chudnovsky, Maria
3 Chuzhoy, Julia
3 Cohen, Gil
3 Dalmau, Víctor
3 Dinur, Irit
3 Dirksen, Sjoerd
3 Doerr, Benjamin
3 Du, Donglei
3 Erlebach, Thomas
3 Friggstad, Zachary
3 Gopalan, Parikshit
3 Hanaka, Tesshu
3 Harsha, Prahladh
3 Håstad, Johan Torkel
3 Hemenway, Brett
3 Hoefer, Martin
3 Il’ev, Victor Petrovich
3 Jansen, Klaus
3 Kanukurthi, Bhavana
3 Kiayias, Aggelos
3 Kobayashi, Yusuke
3 Kozik, Marcin
3 Krokhin, Andrei A.
3 Leppänen, Samuli
...and 1,118 more Authors
all top 5

Cited in 131 Serials

47 Algorithmica
45 Theoretical Computer Science
35 SIAM Journal on Computing
28 Discrete Applied Mathematics
28 Designs, Codes and Cryptography
27 Information Processing Letters
25 Journal of Computer and System Sciences
18 Journal of Combinatorial Optimization
16 Computational Complexity
16 Finite Fields and their Applications
13 Theory of Computing Systems
12 Mathematical Programming. Series A. Series B
9 Discrete Mathematics
9 SIAM Journal on Discrete Mathematics
9 Journal of Cryptology
9 Random Structures & Algorithms
8 Problems of Information Transmission
8 Journal of Symbolic Computation
7 Artificial Intelligence
7 Machine Learning
7 Applicable Algebra in Engineering, Communication and Computing
7 Advances in Mathematics of Communications
6 Networks
6 Operations Research Letters
5 Mathematics of Operations Research
5 Information and Computation
5 Annals of Operations Research
5 Games and Economic Behavior
5 Journal of Discrete Algorithms
5 Discrete Optimization
5 Prikladnaya Diskretnaya Matematika
4 Israel Journal of Mathematics
4 Mathematics of Computation
4 Algebra Universalis
4 Computers & Operations Research
4 European Journal of Operational Research
4 International Journal of Computer Mathematics
4 Linear Algebra and its Applications
4 Journal of the ACM
3 Information Sciences
3 Combinatorica
3 Discrete & Computational Geometry
3 Distributed Computing
3 Applied and Computational Harmonic Analysis
3 Annals of Mathematics. Second Series
3 4OR
3 Optimization Letters
3 Diskretnyĭ Analiz i Issledovanie Operatsiĭ
2 Journal of Combinatorial Theory. Series A
2 Mathematische Zeitschrift
2 Transactions of the American Mathematical Society
2 Journal of Complexity
2 Journal of Computer Science and Technology
2 Science in China. Series A
2 Geometric and Functional Analysis. GAFA
2 SIAM Journal on Optimization
2 Computational Optimization and Applications
2 Combinatorics, Probability and Computing
2 Journal of Scheduling
2 Journal of Machine Learning Research (JMLR)
2 Algorithms
2 Science China. Mathematics
2 ACM Transactions on Algorithms
2 Theory of Computing
2 EURO Journal on Computational Optimization
2 ACM Transactions on Computation Theory
1 American Mathematical Monthly
1 Communications on Pure and Applied Mathematics
1 Journal of Mathematical Physics
1 Linear and Multilinear Algebra
1 Mathematical Notes
1 Advances in Mathematics
1 The Annals of Statistics
1 Applied Mathematics and Computation
1 Duke Mathematical Journal
1 Inventiones Mathematicae
1 Journal of Economic Theory
1 Journal of Pure and Applied Algebra
1 The Journal of Symbolic Logic
1 Naval Research Logistics
1 Operations Research
1 Quaestiones Mathematicae
1 European Journal of Combinatorics
1 Mathematical Social Sciences
1 Chinese Annals of Mathematics. Series B
1 Graphs and Combinatorics
1 Constructive Approximation
1 Journal of Automated Reasoning
1 Computational Geometry
1 Journal of Global Optimization
1 Computational Mathematics and Mathematical Physics
1 YUJOR. Yugoslav Journal of Operations Research
1 SIAM Journal on Mathematical Analysis
1 Annales de la Faculté des Sciences de Toulouse. Mathématiques. Série VI
1 Computational and Applied Mathematics
1 Top
1 Advances in Computational Mathematics
1 The Journal of Artificial Intelligence Research (JAIR)
1 The Journal of Fourier Analysis and Applications
1 Abstract and Applied Analysis
...and 31 more Serials

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.