2009 |
126 | EE | Venkatesan Guruswami,
Atri Rudra:
Error correction up to the information-theoretic limit.
Commun. ACM 52(3): 87-95 (2009) |
125 | EE | Venkatesan Guruswami,
Atri Rudra:
Better Binary List Decodable Codes Via Multilevel Concatenation.
IEEE Transactions on Information Theory 55(1): 19-26 (2009) |
2008 |
124 | EE | Venkatesan Guruswami,
James R. Lee,
Avi Wigderson:
Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals.
APPROX-RANDOM 2008: 444-454 |
123 | EE | Venkatesan Guruswami,
Prasad Raghavendra:
Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness.
APPROX-RANDOM 2008: 77-90 |
122 | EE | Venkatesan Guruswami,
Rajsekar Manokaran,
Prasad Raghavendra:
Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph.
FOCS 2008: 573-582 |
121 | EE | Venkatesan Guruswami:
List Error-Correction with Optimal Information Rate (Invited Talk).
ICITS 2008: 118-119 |
120 | 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 |
119 | EE | Parikshit Gopalan,
Venkatesan Guruswami:
Hardness Amplification within NP against Deterministic Algorithms.
IEEE Conference on Computational Complexity 2008: 19-30 |
118 | EE | Venkatesan Guruswami,
Atri Rudra:
Concatenated codes can achieve list-decoding capacity.
SODA 2008: 258-267 |
117 | EE | Venkatesan Guruswami,
James R. Lee,
Alexander A. Razborov:
Almost Euclidean subspaces of lN1 via expander codes.
SODA 2008: 353-362 |
116 | EE | Venkatesan Guruswami:
Decoding Reed-Solomon Codes.
Encyclopedia of Algorithms 2008 |
115 | EE | Parikshit Gopalan,
Venkatesan Guruswami,
Richard J. Lipton:
Algorithms for Modular Counting of Roots of Multivariate Polynomials.
Algorithmica 50(4): 479-496 (2008) |
114 | EE | Venkatesan Guruswami:
Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes
CoRR abs/0811.4139: (2008) |
113 | EE | Parikshit Gopalan,
Venkatesan Guruswami,
Prasad Raghavendra:
List Decoding Tensor Products and Interleaved Codes
CoRR abs/0811.4395: (2008) |
112 | EE | 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) |
111 | EE | 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) |
110 | EE | Venkatesan Guruswami,
Atri Rudra:
Concatenated codes can achieve list-decoding capacity.
Electronic Colloquium on Computational Complexity (ECCC) 15(054): (2008) |
109 | EE | Parikshit Gopalan,
Venkatesan Guruswami,
Prasad Raghavendra,
Prasad Raghavendra:
List Decoding Tensor Products and Interleaved Codes.
Electronic Colloquium on Computational Complexity (ECCC) 15(105): (2008) |
108 | EE | 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) |
2007 |
107 | EE | Venkatesan Guruswami:
List Decoding and Pseudorandom Constructions.
AAECC 2007: 1-6 |
106 | EE | Venkatesan Guruswami,
Atri Rudra:
Better Binary List-Decodable Codes Via Multilevel Concatenation.
APPROX-RANDOM 2007: 554-568 |
105 | 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 |
104 | EE | Julia Chuzhoy,
Venkatesan Guruswami,
Sanjeev Khanna,
Kunal Talwar:
Hardness of routing with congestion in directed graphs.
STOC 2007: 165-178 |
103 | EE | Venkatesan Guruswami,
Prasad Raghavendra:
A 3-query PCP over integers.
STOC 2007: 198-206 |
102 | EE | Noga Alon,
Venkatesan Guruswami,
Tali Kaufman,
Madhu Sudan:
Guessing secrets efficiently via list decoding.
ACM Transactions on Algorithms 3(4): (2007) |
101 | EE | Venkatesan Guruswami,
Valentine Kabanets:
Special Issue "Conference on Computational Complexity 2006" Guest Editors' Foreword.
Computational Complexity 16(2): 113-114 (2007) |
100 | EE | 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) |
99 | EE | Parikshit Gopalan,
Venkatesan Guruswami:
Deterministic Hardness Amplification via Local GMD Decoding.
Electronic Colloquium on Computational Complexity (ECCC) 14(089): (2007) |
98 | EE | Venkatesan Guruswami,
Atri Rudra:
Better Binary List-Decodable Codes via Multilevel Concatenation.
Electronic Colloquium on Computational Complexity (ECCC) 14(109): (2007) |
97 | EE | 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 |
96 | EE | Venkatesan Guruswami,
Anindya C. Patthak:
Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets.
FOCS 2006: 227-238 |
95 | EE | Venkatesan Guruswami,
Prasad Raghavendra:
Hardness of Learning Halfspaces with Noise.
FOCS 2006: 543-552 |
94 | EE | Venkatesan Guruswami:
On 2-Query Codeword Testing with Near-Perfect Completeness.
ISAAC 2006: 267-276 |
93 | EE | Parikshit Gopalan,
Venkatesan Guruswami,
Richard J. Lipton:
Algorithms for Modular Counting of Roots of Multivariate Polynomials.
LATIN 2006: 544-555 |
92 | EE | Venkatesan Guruswami,
Valentine Kabanets:
Hardness Amplification Via Space-Efficient Direct Products.
LATIN 2006: 556-568 |
91 | EE | Ioannis Giotis,
Venkatesan Guruswami:
Correlation clustering with a fixed number of clusters.
SODA 2006: 1167-1176 |
90 | EE | Venkatesan Guruswami,
Atri Rudra:
Explicit capacity-achieving list-decodable codes.
STOC 2006: 1-10 |
89 | EE | Venkatesan Guruswami:
Iterative Decoding of Low-Density Parity Check Codes (A Survey)
CoRR abs/cs/0610022: (2006) |
88 | EE | Venkatesan Guruswami,
Prasad Raghavendra:
Hardness of Learning Halfspaces with Noise.
Electronic Colloquium on Computational Complexity (ECCC) 13(061): (2006) |
87 | EE | Venkatesan Guruswami:
Iterative Decoding of Low-Density Parity Check Codes (A Survey).
Electronic Colloquium on Computational Complexity (ECCC) 13(123): (2006) |
86 | EE | Venkatesan Guruswami,
Christopher Umans,
Salil P. Vadhan:
Extractors and condensers from univariate polynomials.
Electronic Colloquium on Computational Complexity (ECCC) 13(134): (2006) |
85 | EE | Venkatesan Guruswami,
Kunal Talwar:
Hardness of Low Congestion Routing in Directed Graphs.
Electronic Colloquium on Computational Complexity (ECCC) 13(141): (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) |