Venkatesan Guruswami

	2012
197		Venkatesan Guruswami, Srivatsan Narayanan, Carol Wang: List decoding subspace codes from insertions and deletions. ITCS 2012: 183-189
196		Venkatesan Guruswami, Ali Kemal Sinop: Optimal column-based low-rank matrix reconstruction. SODA 2012: 1207-1214
195		Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, Venkatesan Guruswami, Yuan Zhou: Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph. SODA 2012: 388-405
194		Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu: Bypassing UGC from some optimal geometric inapproximability results. SODA 2012: 699-717
193		Venkatesan Guruswami, Chaoping Xing: Folded codes from function field towers and improved optimal rate list decoding. STOC 2012: 339-350
192		Venkatesan Guruswami, Srivatsan Narayanan, Carol Wang: List decoding subspace codes from insertions and deletions CoRR abs/1202.0535: (2012)
191		Venkatesan Guruswami, Ali Kemal Sinop, Yuan Zhou: Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems CoRR abs/1202.6071: (2012)
190		Venkatesan Guruswami, Srivatsan Narayanan: Combinatorial limitations of a strong form of list decoding CoRR abs/1202.6086: (2012)
189		Venkatesan Guruswami, Chaoping Xing: Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding CoRR abs/1204.4209: (2012)
188		Venkatesan Guruswami, Srivatsan Narayanan: Combinatorial limitations of a strong form of list decoding. Electronic Colloquium on Computational Complexity (ECCC) 19: 17 (2012)
187		Venkatesan Guruswami, Chaoping Xing: Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding. Electronic Colloquium on Computational Complexity (ECCC) 19: 36 (2012)
	2011
186		Venkatesan Guruswami, Carol Wang: Optimal Rate List Decoding via Derivative Codes. APPROX-RANDOM 2011: 593-604
185		Venkatesan Guruswami, Ali Kemal Sinop: Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives. FOCS 2011: 482-491
184		Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou: Finding Almost-Perfect Graph Bisections. ICS 2011: 321-337
183		Venkatesan Guruswami: Linear-Algebraic List Decoding of Folded Reed-Solomon Codes. IEEE Conference on Computational Complexity 2011: 77-85
182		Venkatesan Guruswami, Yuan Zhou: Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set. SODA 2011: 1574-1589
181		Venkatesan Guruswami, Ali Kemal Sinop: The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number. SODA 2011: 1615-1626
180		Amit Chakrabarti, Venkatesan Guruswami, Andrew Wirth, Anthony Wirth: The query complexity of estimating weighted averages. Acta Inf. 48(7-8): 417-426 (2011)
179		Venkatesan Guruswami, Ali Kemal Sinop: Optimal Column-Based Low-Rank Matrix Reconstruction CoRR abs/1104.1732: (2011)
178		Venkatesan Guruswami, Ali Kemal Sinop: Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives CoRR abs/1104.4746: (2011)
177		Venkatesan Guruswami: Linear-algebraic list decoding of folded Reed-Solomon codes CoRR abs/1106.0436: (2011)
176		Venkatesan Guruswami, Carol Wang: Optimal rate list decoding via derivative codes CoRR abs/1106.3951: (2011)
175		Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, Yuan Zhou: Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph CoRR abs/1110.1360: (2011)
174		Venkatesan Guruswami, Ali Kemal Sinop: Certifying Graph Expansion and Non-Uniform Sparsity via Generalized Spectra CoRR abs/1112.4109: (2011)
173		Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar: Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant. Electronic Colloquium on Computational Complexity (ECCC) 18: 27 (2011)
172		Venkatesan Guruswami, Ali Kemal Sinop: Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives. Electronic Colloquium on Computational Complexity (ECCC) 18: 66 (2011)
171		Venkatesan Guruswami, Atri Rudra: Soft Decoding, Dual BCH Codes, and Better List-Decodable varepsilon-Biased Codes. IEEE Transactions on Information Theory 57(2): 705-717 (2011)
170		Venkatesan Guruswami, Johan Håstad, Swastik Kopparty: On the List-Decodability of Random Linear Codes. IEEE Transactions on Information Theory 57(2): 718-725 (2011)
169		Parikshit Gopalan, Venkatesan Guruswami: Hardness amplification within NP against deterministic algorithms. J. Comput. Syst. Sci. 77(1): 107-121 (2011)
168		Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar: Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant. SIAM J. Comput. 40(3): 878-914 (2011)
167		Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra: List Decoding Tensor Products and Interleaved Codes. SIAM J. Comput. 40(5): 1432-1462 (2011)
	2010
166		Venkatesan Guruswami, Adam Smith: Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate. FOCS 2010: 723-732
165		Venkatesan Guruswami, Rishi Saket: On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs. ICALP (1) 2010: 360-371
164		Venkatesan Guruswami, Subhash Khot, Ryan O'Donnell, Preyas Popat, Madhur Tulsiani, Yi Wu: SDP Gaps for 2-to-1 and Other Label-Cover Variants. ICALP (1) 2010: 617-628
163		Venkatesan Guruswami, Johan Håstad, Swastik Kopparty: On the list-decodability of random linear codes. STOC 2010: 409-416
162		Venkatesan Guruswami, Johan Håstad, Swastik Kopparty: On the List-Decodability of Random Linear Codes CoRR abs/1001.1386: (2010)
161		Venkatesan Guruswami, Adam Smith: Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate CoRR abs/1004.4017: (2010)
160		Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu: Agnostic Learning of Monomials by Halfspaces is Hard CoRR abs/1012.0729: (2010)
159		Venkatesan Guruswami, James R. Lee, Alexander A. Razborov: Almost Euclidean subspaces of l 1N VIA expander codes. Combinatorica 30(1): 47-68 (2010)
158		Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang: Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs. Combinatorica 30(5): 485-520 (2010)
157		Venkatesan Guruswami, Ali Kemal Sinop: The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number. Electronic Colloquium on Computational Complexity (ECCC) 17: 111 (2010)
156		Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu: Bypassing UGC from some optimal geometric inapproximability results. Electronic Colloquium on Computational Complexity (ECCC) 17: 177 (2010)
155		Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu: Agnostic Learning of Monomials by Halfspaces is Hard. Electronic Colloquium on Computational Complexity (ECCC) 17: 185 (2010)
154		Venkatesan Guruswami, Johan Håstad, Swastik Kopparty: On the List-Decodability of Random Linear Codes. Electronic Colloquium on Computational Complexity (ECCC) 17: 3 (2010)
153		Venkatesan Guruswami, Yuan Zhou: Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set}. Electronic Colloquium on Computational Complexity (ECCC) 17: 63 (2010)
152		Venkatesan Guruswami, Adam Smith: Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate. Electronic Colloquium on Computational Complexity (ECCC) 17: 77 (2010)
151		Venkatesan Guruswami, Atri Rudra: The existence of concatenated codes list-decodable up to the hamming bound. IEEE Transactions on Information Theory 56(10): 5195-5206 (2010)
150		Venkatesan Guruswami, Salil P. Vadhan: A Lower Bound on List Size for List Decoding. IEEE Transactions on Information Theory 56(11): 5681-5688 (2010)
149		Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman: Locally Testable Codes Require Redundant Testers. SIAM J. Comput. 39(7): 3230-3247 (2010)
	2009
148		Venkatesan Guruswami, Ali Kemal Sinop: Improved Inapproximability Results for Maximum k-Colorable Subgraph. APPROX-RANDOM 2009: 163-176
147		Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu: Agnostic Learning of Monomials by Halfspaces Is Hard. FOCS 2009: 385-394
146		Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman: Locally Testable Codes Require Redundant Testers. IEEE Conference on Computational Complexity 2009: 52-61
145		Moses Charikar, Venkatesan Guruswami, Rajsekar Manokaran: Every Permutation CSP of arity 3 is Approximation Resistant. IEEE Conference on Computational Complexity 2009: 62-73
144		Venkatesan Guruswami: List Decoding of Binary Codes-A Brief Survey of Some Recent Results. IWCC 2009: 97-106
143		Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra: List decoding tensor products and interleaved codes. STOC 2009: 13-22
142		Venkatesan Guruswami: Artin automorphisms, cyclotomic function fields, and folded list-decodable codes. STOC 2009: 23-32
141		MohammadHossein Bateni, Moses Charikar, Venkatesan Guruswami: MaxMin allocation via degree lower-bounded arborescences. STOC 2009: 543-552
140		Venkatesan Guruswami, Ali Kemal Sinop: Improved Inapproximability Results for Maximum k-Colorable Subgraph CoRR abs/0910.2271: (2009)
139		Venkatesan Guruswami, Adam Smith: Explicit Capacity-achieving Codes for Worst-Case Additive Errors CoRR abs/0912.0965: (2009)
138		Venkatesan Guruswami, Atri Rudra: Error correction up to the information-theoretic limit. Commun. ACM 52(3): 87-95 (2009)
137		Venkatesan Guruswami: Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes. Electronic Colloquium on Computational Complexity (ECCC) 16: 1 (2009)
136		Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman: Locally Testable Codes Require Redundant Testers. Electronic Colloquium on Computational Complexity (ECCC) 16: 126 (2009)
135		Venkatesan Guruswami, Prasad Raghavendra: Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers. Electronic Colloquium on Computational Complexity (ECCC) 16: 20 (2009)
134		Venkatesan Guruswami, Ali Kemal Sinop: Improved Inapproximability Results for Maximum k-Colorable Subgraph. Electronic Colloquium on Computational Complexity (ECCC) 16: 99 (2009)
133		Venkatesan Guruswami, Atri Rudra: Better Binary List Decodable Codes Via Multilevel Concatenation. IEEE Transactions on Information Theory 55(1): 19-26 (2009)
132		Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan: Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes. J. ACM 56(4): (2009)
131		Venkatesan Guruswami, Prasad Raghavendra: Hardness of Learning Halfspaces with Noise. SIAM J. Comput. 39(2): 742-765 (2009)
130		Venkatesan Guruswami, Prasad Raghavendra: Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers. TOCT 1(2): (2009)
	2008
129		Venkatesan Guruswami, James R. Lee, Avi Wigderson: Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals. APPROX-RANDOM 2008: 444-454
128		Venkatesan Guruswami, Prasad Raghavendra: Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness. APPROX-RANDOM 2008: 77-90
127		Venkatesan Guruswami, Rajsekar Manokaran, Prasad Raghavendra: Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph. FOCS 2008: 573-582
126		Venkatesan Guruswami: List Error-Correction with Optimal Information Rate (Invited Talk). ICITS 2008: 118-119
125		Venkatesan Guruswami, Atri Rudra: Soft Decoding, Dual BCH Codes, and Better List-Decodable e-Biased Codes. IEEE Conference on Computational Complexity 2008: 163-174
124		Parikshit Gopalan, Venkatesan Guruswami: Hardness Amplification within NP against Deterministic Algorithms. IEEE Conference on Computational Complexity 2008: 19-30
123		Venkatesan Guruswami, Widad Machmouchi: Explicit interleavers for a Repeat Accumulate Accumulate (RAA) code construction. ISIT 2008: 1968-1972
122		Venkatesan Guruswami, Atri Rudra: Concatenated codes can achieve list-decoding capacity. SODA 2008: 258-267
121		Venkatesan Guruswami, James R. Lee, Alexander A. Razborov: Almost Euclidean subspaces of lN1 via expander codes. SODA 2008: 353-362
120		Venkatesan Guruswami: Decoding Reed-Solomon Codes. Encyclopedia of Algorithms 2008
119		Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton: Algorithms for Modular Counting of Roots of Multivariate Polynomials. Algorithmica 50(4): 479-496 (2008)
118		Venkatesan Guruswami: Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes CoRR abs/0811.4139: (2008)
117		Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra: List Decoding Tensor Products and Interleaved Codes CoRR abs/0811.4395: (2008)
116		Venkatesan Guruswami, Valentine Kabanets: Hardness Amplification via Space-Efficient Direct Products. Computational Complexity 17(4): 475-500 (2008)
115		Venkatesan Guruswami, Prasad Raghavendra: Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness. Electronic Colloquium on Computational Complexity (ECCC) 15(008): (2008)
114		Venkatesan Guruswami, Atri Rudra: Soft decoding, dual BCH codes, and better list-decodable eps-biased codes. Electronic Colloquium on Computational Complexity (ECCC) 15(036): (2008)
113		Venkatesan Guruswami, Atri Rudra: Concatenated codes can achieve list-decoding capacity. Electronic Colloquium on Computational Complexity (ECCC) 15(054): (2008)
112		Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra: List Decoding Tensor Products and Interleaved Codes. Electronic Colloquium on Computational Complexity (ECCC) 15(105): (2008)
111		Venkatesan Guruswami, Atri Rudra: Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy. IEEE Transactions on Information Theory 54(1): 135-150 (2008)
110		Venkatesan Guruswami, Anindya C. Patthak: Correlated algebraic-geometric codes: Improved list decoding over bounded alphabets. Math. Comput. 77(261): 447-473 (2008)
	2007
109		Venkatesan Guruswami: List Decoding and Pseudorandom Constructions. AAECC 2007: 1-6
108		Venkatesan Guruswami, Atri Rudra: Better Binary List-Decodable Codes Via Multilevel Concatenation. APPROX-RANDOM 2007: 554-568
107		Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan: Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes. IEEE Conference on Computational Complexity 2007: 96-108
106		Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar: Hardness of routing with congestion in directed graphs. STOC 2007: 165-178
105		Venkatesan Guruswami, Prasad Raghavendra: A 3-query PCP over integers. STOC 2007: 198-206
104		Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan: Guessing secrets efficiently via list decoding. ACM Transactions on Algorithms 3(4): (2007)
103		Venkatesan Guruswami, Valentine Kabanets: Special Issue "Conference on Computational Complexity 2006" Guest Editors' Foreword. Computational Complexity 16(2): 113-114 (2007)
102		Venkatesan Guruswami, James R. Lee, Alexander A. Razborov: Almost Euclidean subspaces of $\ell_1^N$ via expander codes. Electronic Colloquium on Computational Complexity (ECCC) 14(086): (2007)
101		Parikshit Gopalan, Venkatesan Guruswami: Deterministic Hardness Amplification via Local GMD Decoding. Electronic Colloquium on Computational Complexity (ECCC) 14(089): (2007)
100		Venkatesan Guruswami, Atri Rudra: Better Binary List-Decodable Codes via Multilevel Concatenation. Electronic Colloquium on Computational Complexity (ECCC) 14(109): (2007)
99		Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang: Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Electronic Colloquium on Computational Complexity (ECCC) 14(113): (2007)
	2006
98		Venkatesan Guruswami, Anindya C. Patthak: Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets. FOCS 2006: 227-238
97		Venkatesan Guruswami, Prasad Raghavendra: Hardness of Learning Halfspaces with Noise. FOCS 2006: 543-552
96		Venkatesan Guruswami: On 2-Query Codeword Testing with Near-Perfect Completeness. ISAAC 2006: 267-276
95		Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton: Algorithms for Modular Counting of Roots of Multivariate Polynomials. LATIN 2006: 544-555
94		Venkatesan Guruswami, Valentine Kabanets: Hardness Amplification Via Space-Efficient Direct Products. LATIN 2006: 556-568
93		Ioannis Giotis, Venkatesan Guruswami: Correlation clustering with a fixed number of clusters. SODA 2006: 1167-1176
92		Venkatesan Guruswami, Atri Rudra: Explicit capacity-achieving list-decodable codes. STOC 2006: 1-10
91		Venkatesan Guruswami: Iterative Decoding of Low-Density Parity Check Codes. Bulletin of the EATCS 90: 53-88 (2006)
90		Venkatesan Guruswami: Iterative Decoding of Low-Density Parity Check Codes (A Survey) CoRR abs/cs/0610022: (2006)
89		Venkatesan Guruswami, Prasad Raghavendra: Hardness of Learning Halfspaces with Noise. Electronic Colloquium on Computational Complexity (ECCC) 13(061): (2006)
88		Venkatesan Guruswami: Iterative Decoding of Low-Density Parity Check Codes (A Survey). Electronic Colloquium on Computational Complexity (ECCC) 13(123): (2006)
87		Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan: Extractors and condensers from univariate polynomials. Electronic Colloquium on Computational Complexity (ECCC) 13(134): (2006)
86		Venkatesan Guruswami, Kunal Talwar: Hardness of Low Congestion Routing in Directed Graphs. Electronic Colloquium on Computational Complexity (ECCC) 13(141): (2006)
85		Venkatesan Guruswami: Algorithmic Results in List Decoding. Foundations and Trends in Theoretical Computer Science 2(2): (2006)
84		Venkatesan Guruswami, Atri Rudra: Limits to List Decoding Reed-Solomon Codes. IEEE Transactions on Information Theory 52(8): 3642-3649 (2006)
83		Ioannis Giotis, Venkatesan Guruswami: Correlation Clustering with a Fixed Number of Clusters. Theory of Computing 2(1): 249-266 (2006)
	2005
82		Venkatesan Guruswami, Atri Rudra: Tolerant Locally Testable Codes. APPROX-RANDOM 2005: 306-317
81		Venkatesan Guruswami, Salil P. Vadhan: A Lower Bound on List Size for List Decoding. APPROX-RANDOM 2005: 318-329
80		Venkatesan Guruswami, Luca Trevisan: The Complexity of Making Unique Choices: Approximating 1-in- k SAT. APPROX-RANDOM 2005: 99-110
79		Venkatesan Guruswami, Subhash Khot: Hardness of Max 3SAT with No Mixed Clauses. IEEE Conference on Computational Complexity 2005: 154-162
78		Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, Frank McSherry: On profit-maximizing envy-free pricing. SODA 2005: 1164-1173
77		Venkatesan Guruswami, Alexander Vardy: Maximum-likelihood decoding of Reed-Solomon codes is NP-hard. SODA 2005: 470-478
76		Venkatesan Guruswami, Atri Rudra: Limits to list decoding Reed-Solomon codes. STOC 2005: 602-609
75		Ioannis Giotis, Venkatesan Guruswami: Correlation Clustering with a Fixed Number of Clusters CoRR abs/cs/0504023: (2005)
74		Venkatesan Guruswami, Atri Rudra: Explicit Codes Achieving List Decoding Capacity: Error-correction with Optimal Redundancy CoRR abs/cs/0511072: (2005)
73		Venkatesan Guruswami, Daniele Micciancio, Oded Regev: The complexity of the covering radius problem. Computational Complexity 14(2): 90-121 (2005)
72		Venkatesan Guruswami, Atri Rudra: Tolerant Locally Testable Codes Electronic Colloquium on Computational Complexity (ECCC)(019): (2005)
71		Venkatesan Guruswami, Valentine Kabanets: Hardness amplification via space-efficient direct products Electronic Colloquium on Computational Complexity (ECCC)(057): (2005)
70		Venkatesan Guruswami: Algebraic-geometric generalizations of the Parvaresh-Vardy codes Electronic Colloquium on Computational Complexity (ECCC)(132): (2005)
69		Venkatesan Guruswami, Atri Rudra: Explicit Capacity-Achieving List-Decodable Codes Electronic Colloquium on Computational Complexity (ECCC)(133): (2005)
68		Venkatesan Guruswami, Piotr Indyk: Linear-time encodable/decodable codes with near-optimal rate. IEEE Transactions on Information Theory 51(10): 3393-3400 (2005)
67		Venkatesan Guruswami, Alexander Vardy: Maximum-likelihood decoding of Reed-Solomon codes is NP-hard. IEEE Transactions on Information Theory 51(7): 2249-2256 (2005)
66		Moses Charikar, Venkatesan Guruswami, Anthony Wirth: Clustering with qualitative information. J. Comput. Syst. Sci. 71(3): 360-383 (2005)
65		Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev: A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover. SIAM J. Comput. 34(5): 1129-1146 (2005)
	2004
64		Venkatesan Guruswami: List Decoding of Error-Correcting Codes (Winning Thesis of the 2002 ACM Doctoral Dissertation Competition) Springer 2004
63		Venkatesan Guruswami, Piotr Indyk: Linear-Time List Decoding in Error-Free Settings: (Extended Abstract). ICALP 2004: 695-707
62		Venkatesan Guruswami, Daniele Micciancio, Oded Regev: The Complexity of the Covering Radius Problem on Lattices and Codes. IEEE Conference on Computational Complexity 2004: 161-173
61		Venkatesan Guruswami, Piotr Indyk: Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates. SODA 2004: 756-757
60		Venkatesan Guruswami: Better extractors for better codes? STOC 2004: 436-444
59		Venkatesan Guruswami, Alexander Vardy: Maximum-likelihood decoding of Reed-Solomon Codes is NP-hard CoRR cs.CC/0405005: (2004)
58		Venkatesan Guruswami, Alexander Vardy: Maximum-likelihood decoding of Reed-Solomon codes is NP-hard Electronic Colloquium on Computational Complexity (ECCC)(040): (2004)
57		Edith Cohen, Venkatesan Guruswami: Guest Editors' foreword. J. Comput. Syst. Sci. 68(4): 701 (2004)
56		Lars Engebretsen, Venkatesan Guruswami: Is constraint satisfaction over two variables always easy? Random Struct. Algorithms 25(2): 150-178 (2004)
55		Venkatesan Guruswami, Sanjeev Khanna: On the Hardness of 4-Coloring a 3-Colorable Graph. SIAM J. Discrete Math. 18(1): 30-40 (2004)
54		Venkatesan Guruswami: Guest column: error-correcting codes and expander graphs. SIGACT News 35(3): 25-41 (2004)
	2003
53		Moses Charikar, Venkatesan Guruswami, Anthony Wirth: Clustering with Qualitative Information. FOCS 2003: 524-533
52		Venkatesan Guruswami: List Decoding with Side Information. IEEE Conference on Computational Complexity 2003: 300-
51		Venkatesan Guruswami, Piotr Indyk: Embeddings and non-approximability of geometric problems. SODA 2003: 537-538
50		Venkatesan Guruswami, Igor Shparlinski: Unconditional proof of tightness of Johnson bound. SODA 2003: 754-755
49		Venkatesan Guruswami, Piotr Indyk: Linear time encodable and list decodable codes. STOC 2003: 126-135
48		Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev: A new multilayered PCP and the hardness of hypergraph vertex cover. STOC 2003: 595-601
47		Venkatesan Guruswami: Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses. Algorithmica 38(3): 451-469 (2003)
46		Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev: A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover CoRR cs.CC/0304026: (2003)
45		Venkatesan Guruswami: Better Extractors for Better Codes? Electronic Colloquium on Computational Complexity (ECCC)(080): (2003)
44		Venkatesan Guruswami: List decoding from erasures: bounds and code constructions. IEEE Transactions on Information Theory 49(11): 2826-2833 (2003)
43		Venkatesan Guruswami: Constructions of codes from number fields. IEEE Transactions on Information Theory 49(3): 594-603 (2003)
42		Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. Syst. Sci. 67(3): 473-496 (2003)
	2002
41		Venkatesan Guruswami, Madhu Sudan: Decoding Concatenated Codes using Soft Information. IEEE Conference on Computational Complexity 2002: 148-157
40		Lars Engebretsen, Venkatesan Guruswami: Is Constraint Satisfaction Over Two Variables Always Easy? RANDOM 2002: 224-238
39		Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan: Guessing secrets efficiently via list decoding. SODA 2002: 254-262
38		Venkatesan Guruswami: Limits to list decodability of linear codes. STOC 2002: 802-811
37		Venkatesan Guruswami, Piotr Indyk: Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. STOC 2002: 812-821
36		Irit Dinur, Venkatesan Guruswami, Subhash Khot: Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-epsilon) Electronic Colloquium on Computational Complexity (ECCC)(027): (2002)
35		Lars Engebretsen, Venkatesan Guruswami: Is Constraint Satisfaction Over Two Variables Always Easy? Electronic Colloquium on Computational Complexity (ECCC)(053): (2002)
34		Venkatesan Guruswami, Johan Håstad, Madhu Sudan, David Zuckerman: Combinatorial bounds for list decoding. IEEE Transactions on Information Theory 48(5): 1021-1034 (2002)
33		Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M. Kleinberg, Prabhakar Raghavan, Amit Sahai: Query Strategies for Priced Information. J. Comput. Syst. Sci. 64(4): 785-819 (2002)
32		Venkatesan Guruswami, Johan Håstad, Madhu Sudan: Hardness of Approximate Hypergraph Coloring. SIAM J. Comput. 31(6): 1663-1686 (2002)
	2001
31		Venkatesan Guruswami: Constructions of Codes from Number Fields. AAECC 2001: 129-140
30		Venkatesan Guruswami, Piotr Indyk: Expander-Based Constructions of Efficiently Decodable Codes. FOCS 2001: 658-667
29		Venkatesan Guruswami: List Decoding from Erasures: Bounds and Code Constructions. FSTTCS 2001: 195-206
28		Venkatesan Guruswami, C. Pandu Rangan, Maw-Shang Chang, Gerard J. Chang, C. K. Wong: The Kr-Packing Problem. Computing 66(1): 79-89 (2001)
27		Venkatesan Guruswami: Constructions of Codes from Number Fields Electronic Colloquium on Computational Complexity (ECCC) 8(2): (2001)
26		Venkatesan Guruswami, Madhu Sudan: On representations of algebraic-geometry codes. IEEE Transactions on Information Theory 47(4): 1610-1613 (2001)
25		Venkatesan Guruswami: List decoding of error correcting codes. Massachusetts Institute of Technology 2001: 1-315
	2000
24		Venkatesan Guruswami: Inapproximability results for set splitting and satisfiability problems with no mixed clauses. APPROX 2000: 155-166
23		Venkatesan Guruswami, Madhu Sudan: On Representations of Algebraic-Geometric Codes for List Decoding. ESA 2000: 244-255
22		Venkatesan Guruswami, Johan Håstad, Madhu Sudan: Hardness of Approximate Hypergraph Coloring. FOCS 2000: 149-158
21		Venkatesan Guruswami, Amit Sahai, Madhu Sudan: "Soft-decision" Decoding of Chinese Remainder Codes. FOCS 2000: 159-168
20		Moses Charikar, Venkatesan Guruswami, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai: Combinatorial feature selection problems. FOCS 2000: 631-640
19		Venkatesan Guruswami, Sanjeev Khanna: On the Hardness of 4-Coloring a 3-Colorable Graph. IEEE Conference on Computational Complexity 2000: 188-197
18		Venkatesan Guruswami, Madhu Sudan: List decoding algorithms for certain concatenated codes. STOC 2000: 181-190
17		Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M. Kleinberg, Prabhakar Raghavan, Amit Sahai: Query strategies for priced information (extended abstract). STOC 2000: 582-591
16		Venkatesan Guruswami, C. Pandu Rangan: Algorithmic aspects of clique-transversal and clique-independent sets. Discrete Applied Mathematics 100(3): 183-202 (2000)
15		Venkatesan Guruswami, Johan Håstad, Madhu Sudan: Hardness of approximate hypergraph coloring Electronic Colloquium on Computational Complexity (ECCC) 7(62): (2000)
14		Venkatesan Guruswami, Sanjeev Khanna: On the Hardness of 4-coloring a 3-colorable Graph Electronic Colloquium on Computational Complexity (ECCC) 7(73): (2000)
	1999
13		Venkatesan Guruswami, Amit Sahai: Multiclass Learning, Boosting, and Error-Correcting Codes. COLT 1999: 145-155
12		Yevgeniy Dodis, Venkatesan Guruswami, Sanjeev Khanna: The 2-Catalog Segmentation Problem. SODA 1999: 897-898
11		Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis: Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. STOC 1999: 19-28
10		Venkatesan Guruswami: Maximum Cut on Line and Total Graphs. Discrete Applied Mathematics 92(2-3): 217-221 (1999)
9		Venkatesan Guruswami: Enumerative aspects of certain subclasses of perfect graphs. Discrete Mathematics 205(1-3): 97-117 (1999)
8		Venkatesan Guruswami: The Approximability of Set Splitting Problems and Satisfiability Problems with no Mixed Clauses Electronic Colloquium on Computational Complexity (ECCC)(43): (1999)
7		Venkatesan Guruswami, Madhu Sudan: Improved decoding of Reed-Solomon and algebraic-geometry codes. IEEE Transactions on Information Theory 45(6): 1757-1767 (1999)
	1998
6		Venkatesan Guruswami, Madhu Sudan: Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes. FOCS 1998: 28-39
5		Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan: A Tight Characterization of NP with 3 Query PCPs. FOCS 1998: 8-17
4		Venkatesan Guruswami, C. Pandu Rangan, Maw-Shang Chang, Gerard J. Chang, C. K. Wong: The Vertex-Disjoint Triangles Problem. WG 1998: 26-37
3		Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan: A tight characterization of NP with 3 query PCPs Electronic Colloquium on Computational Complexity (ECCC) 5(34): (1998)
2		Venkatesan Guruswami, Madhu Sudan: Improved decoding of Reed-Solomon and algebraic-geometric codes. Electronic Colloquium on Computational Complexity (ECCC) 5(43): (1998)
1		Venkatesan Guruswami, C. Pandu Rangan: A Natural Family of Optimization Problems with Arbitrarily Small Approximation Thresholds. Inf. Process. Lett. 68(5): 241-248 (1998)

Coauthor Index

1	Noga Alon	[39] [104]
2	Matthew Andrews	[99] [158]
3	MohammadHossein Bateni	[141]
4	Eli Ben-Sasson	[136] [146] [149]
5	Aditya Bhaskara	[175] [195]
6	Amit Chakrabarti	[180]
7	Gerard J. Chang (Gerard Jennhwa Chang)	[4] [28]
8	Maw-Shang Chang	[4] [28]
9	Moses Charikar	[17] [20] [33] [53] [66] [141] [145] [168] [173] [175] [195]
10	Julia Chuzhoy	[99] [106] [158]
11	Edith Cohen	[57]
12	Irit Dinur	[36] [46] [48] [65]
13	Yevgeniy Dodis	[12]
14	Lars Engebretsen	[35] [40] [56]
15	Ronald Fagin	[17] [33]
16	Vitaly Feldman	[147] [155] [160]
17	Ioannis Giotis	[75] [83] [93]
18	Parikshit Gopalan	[95] [101] [112] [117] [119] [124] [143] [167] [169]
19	Jason D. Hartline	[78]
20	Johan Håstad	[15] [22] [32] [34] [154] [162] [163] [168] [170] [173]
21	Piotr Indyk	[30] [37] [49] [51] [61] [63] [68]
22	Valentine Kabanets	[71] [94] [103] [116]
23	Anna R. Karlin	[78]
24	Tali Kaufman	[39] [104] [136] [146] [149]
25	David Kempe	[78]
26	Sanjeev Khanna	[11] [12] [14] [19] [42] [55] [99] [106] [158]
27	Subhash Khot	[36] [46] [48] [65] [79] [164]
28	Jon M. Kleinberg	[17] [33]
29	Swastik Kopparty	[154] [162] [163] [170]
30	Ravi Kumar (S. Ravi Kumar)	[20]
31	James R. Lee	[102] [121] [129] [159]
32	Daniel Lewin	[3] [5]
33	Richard J. Lipton	[95] [119]
34	Widad Machmouchi	[123]
35	Yury Makarychev	[184]
36	Rajsekar Manokaran	[127] [145] [168] [173]
37	Claire Mathieu (Claire Kenyon, Claire Kenyon-Mathieu)	[78]
38	Frank McSherry	[78]
39	Daniele Micciancio	[62] [73]
40	Srivatsan Narayanan	[188] [190] [192] [197]
41	Ryan O'Donnell	[164]
42	Anindya C. Patthak	[98] [110]
43	Preyas Popat	[164]
44	Prabhakar Raghavan	[17] [33]
45	Prasad Raghavendra	[89] [97] [105] [112] [115] [117] [127] [128] [130] [131] [135] [143] [147] [155] [156] [160] [167] [168] [173] [184] [194]
46	Sridhar Rajagopalan	[20]
47	Rajmohan Rajaraman	[11] [42]
48	C. Pandu Rangan (Chandrasekaran Pandu Rangan)	[1] [4] [16] [28]
49	Alexander A. Razborov	[102] [121] [159]
50	Oded Regev	[46] [48] [62] [65] [73]
51	Atri Rudra	[69] [72] [74] [76] [82] [84] [92] [100] [108] [111] [113] [114] [122] [125] [133] [138] [151] [171]
52	Amit Sahai	[13] [17] [20] [21] [33]
53	Rishi Saket	[156] [165] [194]
54	F. Bruce Shepherd	[11] [42]
55	Igor Shparlinski	[50]
56	Ali Kemal Sinop	[134] [140] [148] [157] [172] [174] [178] [179] [181] [185] [191] [196]
57	Adam Smith (Adam D. Smith)	[139] [152] [161] [166]
58	David Steurer	[184]
59	Madhu Sudan	[2] [3] [5] [6] [7] [15] [18] [21] [22] [23] [26] [32] [34] [39] [41] [104] [136] [146] [149]
60	Kunal Talwar	[86] [99] [106] [158]
61	Luca Trevisan	[3] [5] [80]
62	Madhur Tulsiani	[164]
63	Christopher Umans	[87] [107] [132]
64	Salil P. Vadhan	[81] [87] [107] [132] [150]
65	Alexander Vardy	[58] [59] [67] [77]
66	Michael Viderman	[136] [146] [149]
67	Aravindan Vijayaraghavan	[175] [195]
68	Carol Wang	[176] [186] [192] [197]
69	Avi Wigderson	[129]
70	Andrew Wirth	[180]
71	Anthony Wirth (Anthony Ian Wirth)	[53] [66] [180]
72	Chak-Kuen Wong (C. K. Wong)	[4] [28]
73	Yi Wu	[147] [155] [156] [160] [164] [194]
74	Chaoping Xing	[187] [189] [193]
75	Mihalis Yannakakis	[11] [42]
76	Lisa Zhang	[99] [158]
77	Yuan Zhou	[153] [175] [182] [184] [191] [195]
78	David Zuckerman	[34]

Colors in the list of coauthors

Last update Fri May 25 01:42:58 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page