Venkatesan Guruswami

Venkatesan Guruswami, Carol Wang: Linear-Algebraic List Decoding for Variants of Reed-Solomon Codes. IEEE Transactions on Information Theory 59(6): 3257-3268 (2013)

Venkatesan Guruswami, Ali Kemal Sinop: Approximating Non-Uniform Sparsest Cut Via Generalized Spectra. SODA 2013: 295-305

Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker: Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. SODA 2013: 432-442

Venkatesan Guruswami, Chaoping Xing: Optimal rate algebraic list decoding using narrow ray class fields. CoRR abs/1302.6660 (2013)

Venkatesan Guruswami, Patrick Xia: Polar Codes: Speed of polarization and polynomial gap to capacity. CoRR abs/1304.4321 (2013)

Venkatesan Guruswami, Krzysztof Onak: Superlinear lower bounds for multipass graph processing. Electronic Colloquium on Computational Complexity (ECCC) 20: 2 (2013)

Venkatesan Guruswami, Chaoping Xing: Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets. Electronic Colloquium on Computational Complexity (ECCC) 20: 46 (2013)

Venkatesan Guruswami, Patrick Xia: Polar Codes: Speed of polarization and polynomial gap to capacity. Electronic Colloquium on Computational Complexity (ECCC) 20: 50 (2013)

Venkatesan Guruswami, Swastik Kopparty: Explicit Subspace Designs. Electronic Colloquium on Computational Complexity (ECCC) 20: 60 (2013)

Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu: Agnostic Learning of Monomials by Halfspaces Is Hard. SIAM J. Comput. 41(6): 1558-1590 (2012)

Venkatesan Guruswami, Yuan Zhou: Tight Bounds on the Approximability of Almost-Satisfiable Horn SAT and Exact Hitting Set. Theory of Computing 8(1): 239-267 (2012)

Venkatesan Guruswami, Yuan Zhou: Approximating Bounded Occurrence Ordering CSPs. APPROX-RANDOM 2012: 158-169

Venkatesan Guruswami, Ali Kemal Sinop: Faster SDP Hierarchy Solvers for Local Rounding Algorithms. FOCS 2012: 197-206

Venkatesan Guruswami, Srivatsan Narayanan, Carol Wang: List decoding subspace codes from insertions and deletions. ITCS 2012: 183-189

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

Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu: Bypassing UGC from some optimal geometric inapproximability results. SODA 2012: 699-717

Venkatesan Guruswami, Ali Kemal Sinop: Optimal column-based low-rank matrix reconstruction. SODA 2012: 1207-1214

Venkatesan Guruswami, Chaoping Xing: Folded codes from function field towers and improved optimal rate list decoding. STOC 2012: 339-350

Venkatesan Guruswami, Srivatsan Narayanan, Carol Wang: List decoding subspace codes from insertions and deletions. CoRR abs/1202.0535 (2012)

Venkatesan Guruswami, Ali Kemal Sinop, Yuan Zhou: Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems. CoRR abs/1202.6071 (2012)

Venkatesan Guruswami, Srivatsan Narayanan: Combinatorial limitations of a strong form of list decoding. CoRR abs/1202.6086 (2012)

Venkatesan Guruswami, Chaoping Xing: Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding. CoRR abs/1204.4209 (2012)

Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker: Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. CoRR abs/1207.1140 (2012)

Venkatesan Guruswami, Ali Kemal Sinop: Faster SDP hierarchy solvers for local rounding algorithms. CoRR abs/1207.4372 (2012)

Venkatesan Guruswami, Krzysztof Onak: Superlinear lower bounds for multipass graph processing. CoRR abs/1212.6925 (2012)

Venkatesan Guruswami, Srivatsan Narayanan: Combinatorial limitations of a strong form of list decoding. Electronic Colloquium on Computational Complexity (ECCC) 19: 17 (2012)

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)

Venkatesan Guruswami, Carol Wang: Linear-algebraic list decoding for variants of Reed-Solomon codes. Electronic Colloquium on Computational Complexity (ECCC) 19: 73 (2012)

Venkatesan Guruswami, Yuan Zhou: Approximating Bounded Occurrence Ordering CSPs. Electronic Colloquium on Computational Complexity (ECCC) 19: 74 (2012)

Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker: Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. Electronic Colloquium on Computational Complexity (ECCC) 19: 82 (2012)

Venkatesan Guruswami, Ali Kemal Sinop: Faster SDP hierarchy solvers for local rounding algorithms. Electronic Colloquium on Computational Complexity (ECCC) 19: 111 (2012)

Venkatesan Guruswami, Chaoping Xing: List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound. Electronic Colloquium on Computational Complexity (ECCC) 19: 146 (2012)

Amit Chakrabarti, Venkatesan Guruswami, Andrew Wirth, Anthony Wirth: The query complexity of estimating weighted averages. Acta Inf. 48(7-8): 417-426 (2011)

Parikshit Gopalan, Venkatesan Guruswami: Hardness amplification within NP against deterministic algorithms. J. Comput. Syst. Sci. 77(1): 107-121 (2011)

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)

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra: List Decoding Tensor Products and Interleaved Codes. SIAM J. Comput. 40(5): 1432-1462 (2011)

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)

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)

Venkatesan Guruswami, Carol Wang: Optimal Rate List Decoding via Derivative Codes. APPROX-RANDOM 2011: 593-604

Venkatesan Guruswami: Linear-Algebraic List Decoding of Folded Reed-Solomon Codes. IEEE Conference on Computational Complexity 2011: 77-85

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

Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou: Finding Almost-Perfect Graph Bisections. ICS 2011: 321-337

Venkatesan Guruswami, Yuan Zhou: Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set. SODA 2011: 1574-1589

Venkatesan Guruswami, Ali Kemal Sinop: The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number. SODA 2011: 1615-1626

Venkatesan Guruswami, Ali Kemal Sinop: Optimal Column-Based Low-Rank Matrix Reconstruction. CoRR abs/1104.1732 (2011)

Venkatesan Guruswami, Ali Kemal Sinop: Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives. CoRR abs/1104.4746 (2011)

Venkatesan Guruswami: Linear-algebraic list decoding of folded Reed-Solomon codes. CoRR abs/1106.0436 (2011)

Venkatesan Guruswami, Carol Wang: Optimal rate list decoding via derivative codes. CoRR abs/1106.3951 (2011)

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)

Venkatesan Guruswami, Ali Kemal Sinop: Certifying Graph Expansion and Non-Uniform Sparsity via Generalized Spectra. CoRR abs/1112.4109 (2011)

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)

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)

Venkatesan Guruswami, James R. Lee, Alexander A. Razborov: Almost Euclidean subspaces of l ₁^N VIA expander codes. Combinatorica 30(1): 47-68 (2010)

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)

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)

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)

Venkatesan Guruswami, Salil P. Vadhan: A Lower Bound on List Size for List Decoding. IEEE Transactions on Information Theory 56(11): 5681-5688 (2010)

Venkatesan Guruswami, Adam Smith: Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate. FOCS 2010: 723-732

Venkatesan Guruswami, Rishi Saket: On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs. ICALP (1) 2010: 360-371

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

Venkatesan Guruswami, Johan Håstad, Swastik Kopparty: On the list-decodability of random linear codes. STOC 2010: 409-416

Venkatesan Guruswami, Johan Håstad, Swastik Kopparty: On the List-Decodability of Random Linear Codes. CoRR abs/1001.1386 (2010)

Venkatesan Guruswami, Adam Smith: Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate. CoRR abs/1004.4017 (2010)

Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu: Agnostic Learning of Monomials by Halfspaces is Hard. CoRR abs/1012.0729 (2010)

Venkatesan Guruswami, Johan Håstad, Swastik Kopparty: On the List-Decodability of Random Linear Codes. Electronic Colloquium on Computational Complexity (ECCC) 17: 3 (2010)

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)

Venkatesan Guruswami, Adam Smith: Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate. Electronic Colloquium on Computational Complexity (ECCC) 17: 77 (2010)

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)

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)

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)

Venkatesan Guruswami, Atri Rudra: Error correction up to the information-theoretic limit. Commun. ACM 52(3): 87-95 (2009)

Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan: Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes. J. ACM 56(4) (2009)

Venkatesan Guruswami, Prasad Raghavendra: Hardness of Learning Halfspaces with Noise. SIAM J. Comput. 39(2): 742-765 (2009)

Venkatesan Guruswami, Atri Rudra: Better Binary List Decodable Codes Via Multilevel Concatenation. IEEE Transactions on Information Theory 55(1): 19-26 (2009)

Venkatesan Guruswami, Prasad Raghavendra: Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers. TOCT 1(2) (2009)

Venkatesan Guruswami, Ali Kemal Sinop: Improved Inapproximability Results for Maximum k-Colorable Subgraph. APPROX-RANDOM 2009: 163-176

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

Moses Charikar, Venkatesan Guruswami, Rajsekar Manokaran: Every Permutation CSP of arity 3 is Approximation Resistant. IEEE Conference on Computational Complexity 2009: 62-73

Venkatesan Guruswami: List Decoding of Binary Codes-A Brief Survey of Some Recent Results. IWCC 2009: 97-106

Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu: Agnostic Learning of Monomials by Halfspaces Is Hard. FOCS 2009: 385-394

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra: List decoding tensor products and interleaved codes. STOC 2009: 13-22

Venkatesan Guruswami: Artin automorphisms, cyclotomic function fields, and folded list-decodable codes. STOC 2009: 23-32

MohammadHossein Bateni, Moses Charikar, Venkatesan Guruswami: MaxMin allocation via degree lower-bounded arborescences. STOC 2009: 543-552

Venkatesan Guruswami, Ali Kemal Sinop: Improved Inapproximability Results for Maximum k-Colorable Subgraph. CoRR abs/0910.2271 (2009)

Venkatesan Guruswami, Adam Smith: Explicit Capacity-achieving Codes for Worst-Case Additive Errors. CoRR abs/0912.0965 (2009)

Venkatesan Guruswami: Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes. Electronic Colloquium on Computational Complexity (ECCC) 16: 1 (2009)

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)

Venkatesan Guruswami, Ali Kemal Sinop: Improved Inapproximability Results for Maximum k-Colorable Subgraph. Electronic Colloquium on Computational Complexity (ECCC) 16: 99 (2009)

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)

Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton: Algorithms for Modular Counting of Roots of Multivariate Polynomials. Algorithmica 50(4): 479-496 (2008)

Venkatesan Guruswami, Valentine Kabanets: Hardness Amplification via Space-Efficient Direct Products. Computational Complexity 17(4): 475-500 (2008)

Venkatesan Guruswami, Anindya C. Patthak: Correlated algebraic-geometric codes: Improved list decoding over bounded alphabets. Math. Comput. 77(261): 447-473 (2008)

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)

Venkatesan Guruswami, Prasad Raghavendra: Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness. APPROX-RANDOM 2008: 77-90

Venkatesan Guruswami, James R. Lee, Avi Wigderson: Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals. APPROX-RANDOM 2008: 444-454

Parikshit Gopalan, Venkatesan Guruswami: Hardness Amplification within NP against Deterministic Algorithms. IEEE Conference on Computational Complexity 2008: 19-30

Venkatesan Guruswami, Atri Rudra: Soft Decoding, Dual BCH Codes, and Better List-Decodable e-Biased Codes. IEEE Conference on Computational Complexity 2008: 163-174

Venkatesan Guruswami, Rajsekar Manokaran, Prasad Raghavendra: Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph. FOCS 2008: 573-582

Venkatesan Guruswami: List Error-Correction with Optimal Information Rate (Invited Talk). ICITS 2008: 118-119

Venkatesan Guruswami, Widad Machmouchi: Explicit interleavers for a Repeat Accumulate Accumulate (RAA) code construction. ISIT 2008: 1968-1972

Venkatesan Guruswami, Atri Rudra: Concatenated codes can achieve list-decoding capacity. SODA 2008: 258-267

Venkatesan Guruswami, James R. Lee, Alexander A. Razborov: Almost Euclidean subspaces of l^N₁ via expander codes. SODA 2008: 353-362

Venkatesan Guruswami: Decoding Reed-Solomon Codes. Encyclopedia of Algorithms 2008

Venkatesan Guruswami: Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes. CoRR abs/0811.4139 (2008)

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra: List Decoding Tensor Products and Interleaved Codes. CoRR abs/0811.4395 (2008)

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)

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)

Venkatesan Guruswami, Atri Rudra: Concatenated codes can achieve list-decoding capacity. Electronic Colloquium on Computational Complexity (ECCC) 15(054) (2008)

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra: List Decoding Tensor Products and Interleaved Codes. Electronic Colloquium on Computational Complexity (ECCC) 15(105) (2008)

Venkatesan Guruswami, Valentine Kabanets: Special Issue "Conference on Computational Complexity 2006" Guest Editors' Foreword. Computational Complexity 16(2): 113-114 (2007)

Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan: Guessing secrets efficiently via list decoding. ACM Transactions on Algorithms 3(4) (2007)

Venkatesan Guruswami: List Decoding and Pseudorandom Constructions. AAECC 2007: 1-6

Venkatesan Guruswami, Atri Rudra: Better Binary List-Decodable Codes Via Multilevel Concatenation. APPROX-RANDOM 2007: 554-568

Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan: Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes. IEEE Conference on Computational Complexity 2007: 96-108

Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar: Hardness of routing with congestion in directed graphs. STOC 2007: 165-178

Venkatesan Guruswami, Prasad Raghavendra: A 3-query PCP over integers. STOC 2007: 198-206

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)

Parikshit Gopalan, Venkatesan Guruswami: Deterministic Hardness Amplification via Local GMD Decoding. Electronic Colloquium on Computational Complexity (ECCC) 14(089) (2007)

Venkatesan Guruswami, Atri Rudra: Better Binary List-Decodable Codes via Multilevel Concatenation. Electronic Colloquium on Computational Complexity (ECCC) 14(109) (2007)

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)

Venkatesan Guruswami: Iterative Decoding of Low-Density Parity Check Codes. Bulletin of the EATCS 90: 53-88 (2006)

Venkatesan Guruswami: Algorithmic Results in List Decoding. Foundations and Trends in Theoretical Computer Science 2(2) (2006)

Venkatesan Guruswami, Atri Rudra: Limits to List Decoding Reed-Solomon Codes. IEEE Transactions on Information Theory 52(8): 3642-3649 (2006)

Ioannis Giotis, Venkatesan Guruswami: Correlation Clustering with a Fixed Number of Clusters. Theory of Computing 2(1): 249-266 (2006)

Venkatesan Guruswami, Anindya C. Patthak: Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets. FOCS 2006: 227-238

Venkatesan Guruswami, Prasad Raghavendra: Hardness of Learning Halfspaces with Noise. FOCS 2006: 543-552

Venkatesan Guruswami: On 2-Query Codeword Testing with Near-Perfect Completeness. ISAAC 2006: 267-276

Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton: Algorithms for Modular Counting of Roots of Multivariate Polynomials. LATIN 2006: 544-555

Venkatesan Guruswami, Valentine Kabanets: Hardness Amplification Via Space-Efficient Direct Products. LATIN 2006: 556-568

Ioannis Giotis, Venkatesan Guruswami: Correlation clustering with a fixed number of clusters. SODA 2006: 1167-1176

Venkatesan Guruswami, Atri Rudra: Explicit capacity-achieving list-decodable codes. STOC 2006: 1-10

Venkatesan Guruswami: Iterative Decoding of Low-Density Parity Check Codes (A Survey). CoRR abs/cs/0610022 (2006)

Venkatesan Guruswami, Prasad Raghavendra: Hardness of Learning Halfspaces with Noise. Electronic Colloquium on Computational Complexity (ECCC) 13(061) (2006)

Venkatesan Guruswami: Iterative Decoding of Low-Density Parity Check Codes (A Survey). Electronic Colloquium on Computational Complexity (ECCC) 13(123) (2006)

Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan: Extractors and condensers from univariate polynomials. Electronic Colloquium on Computational Complexity (ECCC) 13(134) (2006)

Venkatesan Guruswami, Kunal Talwar: Hardness of Low Congestion Routing in Directed Graphs. Electronic Colloquium on Computational Complexity (ECCC) 13(141) (2006)

Venkatesan Guruswami, Daniele Micciancio, Oded Regev: The complexity of the covering radius problem. Computational Complexity 14(2): 90-121 (2005)

Moses Charikar, Venkatesan Guruswami, Anthony Wirth: Clustering with qualitative information. J. Comput. Syst. Sci. 71(3): 360-383 (2005)

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)

Venkatesan Guruswami, Alexander Vardy: Maximum-likelihood decoding of Reed-Solomon codes is NP-hard. IEEE Transactions on Information Theory 51(7): 2249-2256 (2005)

Venkatesan Guruswami, Piotr Indyk: Linear-time encodable/decodable codes with near-optimal rate. IEEE Transactions on Information Theory 51(10): 3393-3400 (2005)

Venkatesan Guruswami, Luca Trevisan: The Complexity of Making Unique Choices: Approximating 1-in- k SAT. APPROX-RANDOM 2005: 99-110

Venkatesan Guruswami, Atri Rudra: Tolerant Locally Testable Codes. APPROX-RANDOM 2005: 306-317

Venkatesan Guruswami, Salil P. Vadhan: A Lower Bound on List Size for List Decoding. APPROX-RANDOM 2005: 318-329

Venkatesan Guruswami, Subhash Khot: Hardness of Max 3SAT with No Mixed Clauses. IEEE Conference on Computational Complexity 2005: 154-162

Venkatesan Guruswami, Alexander Vardy: Maximum-likelihood decoding of Reed-Solomon codes is NP-hard. SODA 2005: 470-478

Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, Frank McSherry: On profit-maximizing envy-free pricing. SODA 2005: 1164-1173

Venkatesan Guruswami, Atri Rudra: Limits to list decoding Reed-Solomon codes. STOC 2005: 602-609

Ioannis Giotis, Venkatesan Guruswami: Correlation Clustering with a Fixed Number of Clusters. CoRR abs/cs/0504023 (2005)

Venkatesan Guruswami, Atri Rudra: Explicit Codes Achieving List Decoding Capacity: Error-correction with Optimal Redundancy. CoRR abs/cs/0511072 (2005)

Venkatesan Guruswami, Atri Rudra: Tolerant Locally Testable Codes. Electronic Colloquium on Computational Complexity (ECCC)(019) (2005)

Venkatesan Guruswami, Valentine Kabanets: Hardness amplification via space-efficient direct products. Electronic Colloquium on Computational Complexity (ECCC)(057) (2005)

Venkatesan Guruswami: Algebraic-geometric generalizations of the Parvaresh-Vardy codes. Electronic Colloquium on Computational Complexity (ECCC)(132) (2005)

Venkatesan Guruswami, Atri Rudra: Explicit Capacity-Achieving List-Decodable Codes. Electronic Colloquium on Computational Complexity (ECCC)(133) (2005)

Venkatesan Guruswami: List Decoding of Error-Correcting Codes (Winning Thesis of the 2002 ACM Doctoral Dissertation Competition). Lecture Notes in Computer Science 3282, Springer 2004, isbn 3-540-24051-9

Edith Cohen, Venkatesan Guruswami: Guest Editors' foreword. J. Comput. Syst. Sci. 68(4): 701 (2004)

Lars Engebretsen, Venkatesan Guruswami: Is constraint satisfaction over two variables always easy? Random Struct. Algorithms 25(2): 150-178 (2004)

Venkatesan Guruswami, Sanjeev Khanna: On the Hardness of 4-Coloring a 3-Colorable Graph. SIAM J. Discrete Math. 18(1): 30-40 (2004)

Venkatesan Guruswami: Guest column: error-correcting codes and expander graphs. SIGACT News 35(3): 25-41 (2004)

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

Venkatesan Guruswami, Piotr Indyk: Linear-Time List Decoding in Error-Free Settings: (Extended Abstract). ICALP 2004: 695-707

Venkatesan Guruswami, Piotr Indyk: Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates. SODA 2004: 756-757

Venkatesan Guruswami: Better extractors for better codes? STOC 2004: 436-444

Venkatesan Guruswami, Alexander Vardy: Maximum-likelihood decoding of Reed-Solomon Codes is NP-hard. CoRR cs.CC/0405005 (2004)

Venkatesan Guruswami, Alexander Vardy: Maximum-likelihood decoding of Reed-Solomon codes is NP-hard. Electronic Colloquium on Computational Complexity (ECCC)(040) (2004)

Venkatesan Guruswami: Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses. Algorithmica 38(3): 451-469 (2003)

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)

Venkatesan Guruswami: Constructions of codes from number fields. IEEE Transactions on Information Theory 49(3): 594-603 (2003)

Venkatesan Guruswami: List decoding from erasures: bounds and code constructions. IEEE Transactions on Information Theory 49(11): 2826-2833 (2003)

Venkatesan Guruswami: List Decoding with Side Information. IEEE Conference on Computational Complexity 2003: 300-

Moses Charikar, Venkatesan Guruswami, Anthony Wirth: Clustering with Qualitative Information. FOCS 2003: 524-533

Venkatesan Guruswami, Piotr Indyk: Embeddings and non-approximability of geometric problems. SODA 2003: 537-538

Venkatesan Guruswami, Igor Shparlinski: Unconditional proof of tightness of Johnson bound. SODA 2003: 754-755

Venkatesan Guruswami, Piotr Indyk: Linear time encodable and list decodable codes. STOC 2003: 126-135

Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev: A new multilayered PCP and the hardness of hypergraph vertex cover. STOC 2003: 595-601

Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev: A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover. CoRR cs.CC/0304026 (2003)

Venkatesan Guruswami: Better Extractors for Better Codes? Electronic Colloquium on Computational Complexity (ECCC)(080) (2003)

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)

Venkatesan Guruswami, Johan Håstad, Madhu Sudan: Hardness of Approximate Hypergraph Coloring. SIAM J. Comput. 31(6): 1663-1686 (2002)

Venkatesan Guruswami, Johan Håstad, Madhu Sudan, David Zuckerman: Combinatorial bounds for list decoding. IEEE Transactions on Information Theory 48(5): 1021-1034 (2002)

Venkatesan Guruswami, Madhu Sudan: Decoding Concatenated Codes using Soft Information. IEEE Conference on Computational Complexity 2002: 148-157

Lars Engebretsen, Venkatesan Guruswami: Is Constraint Satisfaction Over Two Variables Always Easy? RANDOM 2002: 224-238

Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan: Guessing secrets efficiently via list decoding. SODA 2002: 254-262

Venkatesan Guruswami: Limits to list decodability of linear codes. STOC 2002: 802-811

Venkatesan Guruswami, Piotr Indyk: Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. STOC 2002: 812-821

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)

Lars Engebretsen, Venkatesan Guruswami: Is Constraint Satisfaction Over Two Variables Always Easy? Electronic Colloquium on Computational Complexity (ECCC)(053) (2002)

Venkatesan Guruswami: List decoding of error correcting codes. Massachusetts Institute of Technology 2001, pp. 1-315

Venkatesan Guruswami, C. Pandu Rangan, Maw-Shang Chang, Gerard J. Chang, C. K. Wong: The K_r-Packing Problem. Computing 66(1): 79-89 (2001)

Venkatesan Guruswami, Madhu Sudan: On representations of algebraic-geometry codes. IEEE Transactions on Information Theory 47(4): 1610-1613 (2001)

Venkatesan Guruswami: Constructions of Codes from Number Fields. AAECC 2001: 129-140

Venkatesan Guruswami, Piotr Indyk: Expander-Based Constructions of Efficiently Decodable Codes. FOCS 2001: 658-667

Venkatesan Guruswami: List Decoding from Erasures: Bounds and Code Constructions. FSTTCS 2001: 195-206

Venkatesan Guruswami: Constructions of Codes from Number Fields. Electronic Colloquium on Computational Complexity (ECCC) 8(2) (2001)

Venkatesan Guruswami, C. Pandu Rangan: Algorithmic aspects of clique-transversal and clique-independent sets. Discrete Applied Mathematics 100(3): 183-202 (2000)

Venkatesan Guruswami: Inapproximability results for set splitting and satisfiability problems with no mixed clauses. APPROX 2000: 155-166

Venkatesan Guruswami, Sanjeev Khanna: On the Hardness of 4-Coloring a 3-Colorable Graph. IEEE Conference on Computational Complexity 2000: 188-197

Venkatesan Guruswami, Madhu Sudan: On Representations of Algebraic-Geometric Codes for List Decoding. ESA 2000: 244-255

Venkatesan Guruswami, Johan Håstad, Madhu Sudan: Hardness of Approximate Hypergraph Coloring. FOCS 2000: 149-158

Venkatesan Guruswami, Amit Sahai, Madhu Sudan: "Soft-decision" Decoding of Chinese Remainder Codes. FOCS 2000: 159-168

Moses Charikar, Venkatesan Guruswami, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai: Combinatorial feature selection problems. FOCS 2000: 631-640

Venkatesan Guruswami, Madhu Sudan: List decoding algorithms for certain concatenated codes. STOC 2000: 181-190

Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M. Kleinberg, Prabhakar Raghavan, Amit Sahai: Query strategies for priced information (extended abstract). STOC 2000: 582-591

Venkatesan Guruswami, Johan Håstad, Madhu Sudan: Hardness of approximate hypergraph coloring. Electronic Colloquium on Computational Complexity (ECCC) 7(62) (2000)

Venkatesan Guruswami, Sanjeev Khanna: On the Hardness of 4-coloring a 3-colorable Graph. Electronic Colloquium on Computational Complexity (ECCC) 7(73) (2000)

Venkatesan Guruswami: Maximum Cut on Line and Total Graphs. Discrete Applied Mathematics 92(2-3): 217-221 (1999)

Venkatesan Guruswami: Enumerative aspects of certain subclasses of perfect graphs. Discrete Mathematics 205(1-3): 97-117 (1999)

Venkatesan Guruswami, Madhu Sudan: Improved decoding of Reed-Solomon and algebraic-geometry codes. IEEE Transactions on Information Theory 45(6): 1757-1767 (1999)

Venkatesan Guruswami, Amit Sahai: Multiclass Learning, Boosting, and Error-Correcting Codes. COLT 1999: 145-155

Yevgeniy Dodis, Venkatesan Guruswami, Sanjeev Khanna: The 2-Catalog Segmentation Problem. SODA 1999: 897-898

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

Venkatesan Guruswami: The Approximability of Set Splitting Problems and Satisfiability Problems with no Mixed Clauses. Electronic Colloquium on Computational Complexity (ECCC)(43) (1999)

Venkatesan Guruswami, C. Pandu Rangan: A Natural Family of Optimization Problems with Arbitrarily Small Approximation Thresholds. Inf. Process. Lett. 68(5): 241-248 (1998)

Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan: A Tight Characterization of NP with 3 Query PCPs. FOCS 1998: 8-17

Venkatesan Guruswami, Madhu Sudan: Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes. FOCS 1998: 28-39

Venkatesan Guruswami, C. Pandu Rangan, Maw-Shang Chang, Gerard J. Chang, C. K. Wong: The Vertex-Disjoint Triangles Problem. WG 1998: 26-37

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)

Venkatesan Guruswami, Madhu Sudan: Improved decoding of Reed-Solomon and algebraic-geometric codes. Electronic Colloquium on Computational Complexity (ECCC) 5(43) (1998)