| 2008 |
|---|
| 104 | EE | Venkatesan Guruswami,
Atri Rudra:
Soft Decoding, Dual BCH Codes, and Better List-Decodable e-Biased Codes.
IEEE Conference on Computational Complexity 2008: 163-174 |
| 103 | EE | Parikshit Gopalan,
Venkatesan Guruswami:
Hardness Amplification within NP against Deterministic Algorithms.
IEEE Conference on Computational Complexity 2008: 19-30 |
| 102 | EE | Venkatesan Guruswami,
Atri Rudra:
Concatenated codes can achieve list-decoding capacity.
SODA 2008: 258-267 |
| 101 | EE | Venkatesan Guruswami,
James R. Lee,
Alexander A. Razborov:
Almost Euclidean subspaces of lN1 via expander codes.
SODA 2008: 353-362 |
| 100 | EE | Parikshit Gopalan,
Venkatesan Guruswami,
Richard J. Lipton:
Algorithms for Modular Counting of Roots of Multivariate Polynomials.
Algorithmica 50(4): 479-496 (2008) |
| 2007 |
|---|
| 99 | EE | Venkatesan Guruswami:
List Decoding and Pseudorandom Constructions.
AAECC 2007: 1-6 |
| 98 | EE | Venkatesan Guruswami,
Atri Rudra:
Better Binary List-Decodable Codes Via Multilevel Concatenation.
APPROX-RANDOM 2007: 554-568 |
| 97 | EE | Venkatesan Guruswami,
Christopher Umans,
Salil P. Vadhan:
Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes.
IEEE Conference on Computational Complexity 2007: 96-108 |
| 96 | EE | Julia Chuzhoy,
Venkatesan Guruswami,
Sanjeev Khanna,
Kunal Talwar:
Hardness of routing with congestion in directed graphs.
STOC 2007: 165-178 |
| 95 | EE | Venkatesan Guruswami,
Prasad Raghavendra:
A 3-query PCP over integers.
STOC 2007: 198-206 |
| 94 | EE | Noga Alon,
Venkatesan Guruswami,
Tali Kaufman,
Madhu Sudan:
Guessing secrets efficiently via list decoding.
ACM Transactions on Algorithms 3(4): (2007) |
| 93 | EE | Venkatesan Guruswami,
Valentine Kabanets:
Special Issue "Conference on Computational Complexity 2006" Guest Editors' Foreword.
Computational Complexity 16(2): 113-114 (2007) |
| 2006 |
|---|
| 92 | EE | Venkatesan Guruswami,
Anindya C. Patthak:
Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets.
FOCS 2006: 227-238 |
| 91 | EE | Venkatesan Guruswami,
Prasad Raghavendra:
Hardness of Learning Halfspaces with Noise.
FOCS 2006: 543-552 |
| 90 | EE | Venkatesan Guruswami:
On 2-Query Codeword Testing with Near-Perfect Completeness.
ISAAC 2006: 267-276 |
| 89 | EE | Parikshit Gopalan,
Venkatesan Guruswami,
Richard J. Lipton:
Algorithms for Modular Counting of Roots of Multivariate Polynomials.
LATIN 2006: 544-555 |
| 88 | EE | Venkatesan Guruswami,
Valentine Kabanets:
Hardness Amplification Via Space-Efficient Direct Products.
LATIN 2006: 556-568 |
| 87 | EE | Ioannis Giotis,
Venkatesan Guruswami:
Correlation clustering with a fixed number of clusters.
SODA 2006: 1167-1176 |
| 86 | EE | Venkatesan Guruswami,
Atri Rudra:
Explicit capacity-achieving list-decodable codes.
STOC 2006: 1-10 |
| 85 | EE | Venkatesan Guruswami:
Iterative Decoding of Low-Density Parity Check Codes (A Survey)
CoRR abs/cs/0610022: (2006) |
| 84 | EE | Venkatesan Guruswami:
Algorithmic Results in List Decoding.
Foundations and Trends in Theoretical Computer Science 2(2): (2006) |
| 83 | EE | Venkatesan Guruswami,
Atri Rudra:
Limits to List Decoding Reed-Solomon Codes.
IEEE Transactions on Information Theory 52(8): 3642-3649 (2006) |
| 82 | EE | Ioannis Giotis,
Venkatesan Guruswami:
Correlation Clustering with a Fixed Number of Clusters.
Theory of Computing 2(1): 249-266 (2006) |
| 2005 |
|---|
| 81 | EE | Venkatesan Guruswami,
Atri Rudra:
Tolerant Locally Testable Codes.
APPROX-RANDOM 2005: 306-317 |
| 80 | EE | Venkatesan Guruswami,
Salil P. Vadhan:
A Lower Bound on List Size for List Decoding.
APPROX-RANDOM 2005: 318-329 |
| 79 | EE | Venkatesan Guruswami,
Luca Trevisan:
The Complexity of Making Unique Choices: Approximating 1-in- k SAT.
APPROX-RANDOM 2005: 99-110 |
| 78 | EE | Venkatesan Guruswami,
Subhash Khot:
Hardness of Max 3SAT with No Mixed Clauses.
IEEE Conference on Computational Complexity 2005: 154-162 |
| 77 | EE | Venkatesan Guruswami,
Jason D. Hartline,
Anna R. Karlin,
David Kempe,
Claire Kenyon,
Frank McSherry:
On profit-maximizing envy-free pricing.
SODA 2005: 1164-1173 |
| 76 | EE | Venkatesan Guruswami,
Alexander Vardy:
Maximum-likelihood decoding of Reed-Solomon codes is NP-hard.
SODA 2005: 470-478 |
| 75 | EE | Venkatesan Guruswami,
Atri Rudra:
Limits to list decoding Reed-Solomon codes.
STOC 2005: 602-609 |
| 74 | EE | Ioannis Giotis,
Venkatesan Guruswami:
Correlation Clustering with a Fixed Number of Clusters
CoRR abs/cs/0504023: (2005) |
| 73 | EE | Venkatesan Guruswami,
Atri Rudra:
Explicit Codes Achieving List Decoding Capacity: Error-correction with Optimal Redundancy
CoRR abs/cs/0511072: (2005) |
| 72 | EE | Venkatesan Guruswami,
Daniele Micciancio,
Oded Regev:
The complexity of the covering radius problem.
Computational Complexity 14(2): 90-121 (2005) |
| 71 | EE | Venkatesan Guruswami,
Atri Rudra:
Tolerant Locally Testable Codes
Electronic Colloquium on Computational Complexity (ECCC)(019): (2005) |
| 70 | EE | Venkatesan Guruswami,
Valentine Kabanets:
Hardness amplification via space-efficient direct products
Electronic Colloquium on Computational Complexity (ECCC)(057): (2005) |
| 69 | EE | Venkatesan Guruswami:
Algebraic-geometric generalizations of the Parvaresh-Vardy codes
Electronic Colloquium on Computational Complexity (ECCC)(132): (2005) |
| 68 | EE | Venkatesan Guruswami,
Atri Rudra:
Explicit Capacity-Achieving List-Decodable Codes
Electronic Colloquium on Computational Complexity (ECCC)(133): (2005) |
| 67 | EE | Venkatesan Guruswami,
Piotr Indyk:
Linear-time encodable/decodable codes with near-optimal rate.
IEEE Transactions on Information Theory 51(10): 3393-3400 (2005) |
| 66 | EE | Venkatesan Guruswami,
Alexander Vardy:
Maximum-likelihood decoding of Reed-Solomon codes is NP-hard.
IEEE Transactions on Information Theory 51(7): 2249-2256 (2005) |
| 65 | EE | Moses Charikar,
Venkatesan Guruswami,
Anthony Wirth:
Clustering with qualitative information.
J. Comput. Syst. Sci. 71(3): 360-383 (2005) |
| 64 | EE | 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 |
|---|
| 63 | | Venkatesan Guruswami:
List Decoding of Error-Correcting Codes (Winning Thesis of the 2002 ACM Doctoral Dissertation Competition)
Springer 2004 |
| 62 | EE | Venkatesan Guruswami,
Piotr Indyk:
Linear-Time List Decoding in Error-Free Settings: (Extended Abstract).
ICALP 2004: 695-707 |
| 61 | EE | 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 |
| 60 | EE | Venkatesan Guruswami,
Piotr Indyk:
Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates.
SODA 2004: 756-757 |
| 59 | EE | Venkatesan Guruswami:
Better extractors for better codes?
STOC 2004: 436-444 |
| 58 | EE | Venkatesan Guruswami,
Alexander Vardy:
Maximum-likelihood decoding of Reed-Solomon Codes is NP-hard
CoRR cs.CC/0405005: (2004) |
| 57 | EE | Venkatesan Guruswami,
Alexander Vardy:
Maximum-likelihood decoding of Reed-Solomon codes is NP-hard
Electronic Colloquium on Computational Complexity (ECCC)(040): (2004) |
| 56 | EE | Edith Cohen,
Venkatesan Guruswami:
Guest Editors' foreword.
J. Comput. Syst. Sci. 68(4): 701 (2004) |
| 55 | EE | Lars Engebretsen,
Venkatesan Guruswami:
Is constraint satisfaction over two variables always easy?
Random Struct. Algorithms 25(2): 150-178 (2004) |
| 54 | EE | Venkatesan Guruswami,
Sanjeev Khanna:
On the Hardness of 4-Coloring a 3-Colorable Graph.
SIAM J. Discrete Math. 18(1): 30-40 (2004) |
| 53 | EE | Venkatesan Guruswami:
Guest column: error-correcting codes and expander graphs.
SIGACT News 35(3): 25-41 (2004) |
| 2003 |
|---|
| 52 | EE | Moses Charikar,
Venkatesan Guruswami,
Anthony Wirth:
Clustering with Qualitative Information.
FOCS 2003: 524-533 |
| 51 | EE | Venkatesan Guruswami:
List Decoding with Side Information.
IEEE Conference on Computational Complexity 2003: 300- |
| 50 | EE | Venkatesan Guruswami,
Piotr Indyk:
Embeddings and non-approximability of geometric problems.
SODA 2003: 537-538 |
| 49 | EE | Venkatesan Guruswami,
Igor Shparlinski:
Unconditional proof of tightness of Johnson bound.
SODA 2003: 754-755 |
| 48 | EE | Venkatesan Guruswami,
Piotr Indyk:
Linear time encodable and list decodable codes.
STOC 2003: 126-135 |
| 47 | EE | Irit Dinur,
Venkatesan Guruswami,
Subhash Khot,
Oded Regev:
A new multilayered PCP and the hardness of hypergraph vertex cover.
STOC 2003: 595-601 |
| 46 | EE | Venkatesan Guruswami:
Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses.
Algorithmica 38(3): 451-469 (2003) |
| 45 | EE | Irit Dinur,
Venkatesan Guruswami,
Subhash Khot,
Oded Regev:
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
CoRR cs.CC/0304026: (2003) |
| 44 | EE | Venkatesan Guruswami:
Better Extractors for Better Codes?
Electronic Colloquium on Computational Complexity (ECCC)(080): (2003) |
| 43 | | Venkatesan Guruswami:
List decoding from erasures: bounds and code constructions.
IEEE Transactions on Information Theory 49(11): 2826-2833 (2003) |
| 42 | | Venkatesan Guruswami:
Constructions of codes from number fields.
IEEE Transactions on Information Theory 49(3): 594-603 (2003) |
| 41 | EE | 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 |
|---|
| 40 | EE | Venkatesan Guruswami,
Madhu Sudan:
Decoding Concatenated Codes using Soft Information.
IEEE Conference on Computational Complexity 2002: 148-157 |
| 39 | EE | Lars Engebretsen,
Venkatesan Guruswami:
Is Constraint Satisfaction Over Two Variables Always Easy?
RANDOM 2002: 224-238 |
| 38 | EE | Noga Alon,
Venkatesan Guruswami,
Tali Kaufman,
Madhu Sudan:
Guessing secrets efficiently via list decoding.
SODA 2002: 254-262 |
| 37 | EE | Venkatesan Guruswami:
Limits to list decodability of linear codes.
STOC 2002: 802-811 |
| 36 | EE | Venkatesan Guruswami,
Piotr Indyk:
Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets.
STOC 2002: 812-821 |
| 35 | EE | 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) |
| 34 | EE | Lars Engebretsen,
Venkatesan Guruswami:
Is Constraint Satisfaction Over Two Variables Always Easy?
Electronic Colloquium on Computational Complexity (ECCC)(053): (2002) |
| 33 | | Venkatesan Guruswami,
Johan Håstad,
Madhu Sudan,
David Zuckerman:
Combinatorial bounds for list decoding.
IEEE Transactions on Information Theory 48(5): 1021-1034 (2002) |
| 32 | EE | 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) |
| 31 | EE | Venkatesan Guruswami,
Johan Håstad,
Madhu Sudan:
Hardness of Approximate Hypergraph Coloring.
SIAM J. Comput. 31(6): 1663-1686 (2002) |
| 2001 |
|---|
| 30 | EE | Venkatesan Guruswami:
Constructions of Codes from Number Fields.
AAECC 2001: 129-140 |
| 29 | | Venkatesan Guruswami,
Piotr Indyk:
Expander-Based Constructions of Efficiently Decodable Codes.
FOCS 2001: 658-667 |
| 28 | EE | Venkatesan Guruswami:
List Decoding from Erasures: Bounds and Code Constructions.
FSTTCS 2001: 195-206 |
| 27 | EE | Venkatesan Guruswami,
C. Pandu Rangan,
Maw-Shang Chang,
Gerard J. Chang,
C. K. Wong:
The Kr-Packing Problem.
Computing 66(1): 79-89 (2001) |
| 26 | EE | Venkatesan Guruswami:
Constructions of Codes from Number Fields
Electronic Colloquium on Computational Complexity (ECCC) 8(2): (2001) |
| 25 | | Venkatesan Guruswami,
Madhu Sudan:
On representations of algebraic-geometry codes.
IEEE Transactions on Information Theory 47(4): 1610-1613 (2001) |
| 2000 |
|---|
| 24 | EE | 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 | EE | Venkatesan Guruswami,
Sanjeev Khanna:
On the Hardness of 4-Coloring a 3-Colorable Graph.
IEEE Conference on Computational Complexity 2000: 188-197 |
| 18 | EE | Venkatesan Guruswami,
Madhu Sudan:
List decoding algorithms for certain concatenated codes.
STOC 2000: 181-190 |
| 17 | EE | 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 | EE | Venkatesan Guruswami,
Johan Håstad,
Madhu Sudan:
Hardness of approximate hypergraph coloring
Electronic Colloquium on Computational Complexity (ECCC) 7(62): (2000) |
| 14 | EE | 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 | EE | Venkatesan Guruswami,
Amit Sahai:
Multiclass Learning, Boosting, and Error-Correcting Codes.
COLT 1999: 145-155 |
| 12 | EE | Yevgeniy Dodis,
Venkatesan Guruswami,
Sanjeev Khanna:
The 2-Catalog Segmentation Problem.
SODA 1999: 897-898 |
| 11 | EE | 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 | EE | Venkatesan Guruswami:
Maximum Cut on Line and Total Graphs.
Discrete Applied Mathematics 92(2-3): 217-221 (1999) |
| 9 | EE | Venkatesan Guruswami:
Enumerative aspects of certain subclasses of perfect graphs.
Discrete Mathematics 205(1-3): 97-117 (1999) |
| 8 | EE | 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 | EE | Venkatesan Guruswami,
Madhu Sudan:
Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes.
FOCS 1998: 28-39 |
| 5 | EE | 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 | EE | 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 | EE | Venkatesan Guruswami,
Madhu Sudan:
Improved decoding of Reed-Solomon and algebraic-geometric codes.
Electronic Colloquium on Computational Complexity (ECCC) 5(43): (1998) |
| 1 | EE | Venkatesan Guruswami,
C. Pandu Rangan:
A Natural Family of Optimization Problems with Arbitrarily Small Approximation Thresholds.
Inf. Process. Lett. 68(5): 241-248 (1998) |
