 | 2010 |
|---|
| 140 |       | Venkatesan Guruswami,
Johan Håstad,
Swastik Kopparty:
On the List-Decodability of Random Linear Codes
CoRR abs/1001.1386: (2010) |
| 2009 |
|---|
| 139 | | Venkatesan Guruswami,
Ali Kemal Sinop:
Improved Inapproximability Results for Maximum k-Colorable Subgraph.
APPROX-RANDOM 2009: 163-176 |
| 138 | | 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 |
| 137 | | Moses Charikar,
Venkatesan Guruswami,
Rajsekar Manokaran:
Every Permutation CSP of arity 3 is Approximation Resistant.
IEEE Conference on Computational Complexity 2009: 62-73 |
| 136 | | Venkatesan Guruswami:
List Decoding of Binary Codes-A Brief Survey of Some Recent Results.
IWCC 2009: 97-106 |
| 135 | | Parikshit Gopalan,
Venkatesan Guruswami,
Prasad Raghavendra:
List decoding tensor products and interleaved codes.
STOC 2009: 13-22 |
| 134 | | Venkatesan Guruswami:
Artin automorphisms, cyclotomic function fields, and folded list-decodable codes.
STOC 2009: 23-32 |
| 133 | | MohammadHossein Bateni,
Moses Charikar,
Venkatesan Guruswami:
MaxMin allocation via degree lower-bounded arborescences.
STOC 2009: 543-552 |
| 132 | | Venkatesan Guruswami,
Ali Kemal Sinop:
Improved Inapproximability Results for Maximum k-Colorable Subgraph
CoRR abs/0910.2271: (2009) |
| 131 | | Venkatesan Guruswami,
Adam Smith:
Explicit Capacity-achieving Codes for Worst-Case Additive Errors
CoRR abs/0912.0965: (2009) |
| 130 | | Venkatesan Guruswami,
Atri Rudra:
Error correction up to the information-theoretic limit.
Commun. ACM 52(3): 87-95 (2009) |
| 129 | | Venkatesan Guruswami,
Atri Rudra:
Better Binary List Decodable Codes Via Multilevel Concatenation.
IEEE Transactions on Information Theory 55(1): 19-26 (2009) |
| 128 | | Venkatesan Guruswami,
Christopher Umans,
Salil P. Vadhan:
Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes.
J. ACM 56(4): (2009) |
| 127 | | Venkatesan Guruswami,
Prasad Raghavendra:
Hardness of Learning Halfspaces with Noise.
SIAM J. Comput. 39(2): 742-765 (2009) |
| 126 | | Venkatesan Guruswami,
Prasad Raghavendra:
Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers.
TOCT 1(2): (2009) |
| 2008 |
|---|
| 125 | | Venkatesan Guruswami,
James R. Lee,
Avi Wigderson:
Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals.
APPROX-RANDOM 2008: 444-454 |
| 124 | | Venkatesan Guruswami,
Prasad Raghavendra:
Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness.
APPROX-RANDOM 2008: 77-90 |
| 123 | | Venkatesan Guruswami,
Rajsekar Manokaran,
Prasad Raghavendra:
Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph.
FOCS 2008: 573-582 |
| 122 | | Venkatesan Guruswami:
List Error-Correction with Optimal Information Rate (Invited Talk).
ICITS 2008: 118-119 |
| 121 | | Venkatesan Guruswami,
Atri Rudra:
Soft Decoding, Dual BCH Codes, and Better List-Decodable e-Biased Codes.
IEEE Conference on Computational Complexity 2008: 163-174 |
| 120 | | Parikshit Gopalan,
Venkatesan Guruswami:
Hardness Amplification within NP against Deterministic Algorithms.
IEEE Conference on Computational Complexity 2008: 19-30 |
| 119 | | Venkatesan Guruswami,
Atri Rudra:
Concatenated codes can achieve list-decoding capacity.
SODA 2008: 258-267 |
| 118 | | Venkatesan Guruswami,
James R. Lee,
Alexander A. Razborov:
Almost Euclidean subspaces of lN1 via expander codes.
SODA 2008: 353-362 |
| 117 | | Venkatesan Guruswami:
Decoding Reed-Solomon Codes.
Encyclopedia of Algorithms 2008 |
| 116 | | Parikshit Gopalan,
Venkatesan Guruswami,
Richard J. Lipton:
Algorithms for Modular Counting of Roots of Multivariate Polynomials.
Algorithmica 50(4): 479-496 (2008) |
| 115 | | Venkatesan Guruswami:
Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes
CoRR abs/0811.4139: (2008) |
| 114 | | Parikshit Gopalan,
Venkatesan Guruswami,
Prasad Raghavendra:
List Decoding Tensor Products and Interleaved Codes
CoRR abs/0811.4395: (2008) |
| 113 | | Venkatesan Guruswami,
Valentine Kabanets:
Hardness Amplification via Space-Efficient Direct Products.
Computational Complexity 17(4): 475-500 (2008) |
| 112 | | 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 | | 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 | | Venkatesan Guruswami,
Atri Rudra:
Concatenated codes can achieve list-decoding capacity.
Electronic Colloquium on Computational Complexity (ECCC) 15(054): (2008) |
| 109 | | Parikshit Gopalan,
Venkatesan Guruswami,
Prasad Raghavendra:
List Decoding Tensor Products and Interleaved Codes.
Electronic Colloquium on Computational Complexity (ECCC) 15(105): (2008) |
| 108 | | 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 | | Venkatesan Guruswami:
List Decoding and Pseudorandom Constructions.
AAECC 2007: 1-6 |
| 106 | | Venkatesan Guruswami,
Atri Rudra:
Better Binary List-Decodable Codes Via Multilevel Concatenation.
APPROX-RANDOM 2007: 554-568 |
| 105 | | 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 | | Julia Chuzhoy,
Venkatesan Guruswami,
Sanjeev Khanna,
Kunal Talwar:
Hardness of routing with congestion in directed graphs.
STOC 2007: 165-178 |
| 103 | | Venkatesan Guruswami,
Prasad Raghavendra:
A 3-query PCP over integers.
STOC 2007: 198-206 |
| 102 | | Noga Alon,
Venkatesan Guruswami,
Tali Kaufman,
Madhu Sudan:
Guessing secrets efficiently via list decoding.
ACM Transactions on Algorithms 3(4): (2007) |
| 101 | | Venkatesan Guruswami,
Valentine Kabanets:
Special Issue "Conference on Computational Complexity 2006" Guest Editors' Foreword.
Computational Complexity 16(2): 113-114 (2007) |
| 100 | | 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 | | Parikshit Gopalan,
Venkatesan Guruswami:
Deterministic Hardness Amplification via Local GMD Decoding.
Electronic Colloquium on Computational Complexity (ECCC) 14(089): (2007) |
| 98 | | Venkatesan Guruswami,
Atri Rudra:
Better Binary List-Decodable Codes via Multilevel Concatenation.
Electronic Colloquium on Computational Complexity (ECCC) 14(109): (2007) |
| 97 | | 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 | | Venkatesan Guruswami,
Anindya C. Patthak:
Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets.
FOCS 2006: 227-238 |
| 95 | | Venkatesan Guruswami,
Prasad Raghavendra:
Hardness of Learning Halfspaces with Noise.
FOCS 2006: 543-552 |
| 94 | | Venkatesan Guruswami:
On 2-Query Codeword Testing with Near-Perfect Completeness.
ISAAC 2006: 267-276 |
| 93 | | Parikshit Gopalan,
Venkatesan Guruswami,
Richard J. Lipton:
Algorithms for Modular Counting of Roots of Multivariate Polynomials.
LATIN 2006: 544-555 |
| 92 | | Venkatesan Guruswami,
Valentine Kabanets:
Hardness Amplification Via Space-Efficient Direct Products.
LATIN 2006: 556-568 |
| 91 | | Ioannis Giotis,
Venkatesan Guruswami:
Correlation clustering with a fixed number of clusters.
SODA 2006: 1167-1176 |
| 90 | | Venkatesan Guruswami,
Atri Rudra:
Explicit capacity-achieving list-decodable codes.
STOC 2006: 1-10 |
| 89 | | Venkatesan Guruswami:
Iterative Decoding of Low-Density Parity Check Codes (A Survey)
CoRR abs/cs/0610022: (2006) |
| 88 | | Venkatesan Guruswami,
Prasad Raghavendra:
Hardness of Learning Halfspaces with Noise.
Electronic Colloquium on Computational Complexity (ECCC) 13(061): (2006) |
| 87 | | Venkatesan Guruswami:
Iterative Decoding of Low-Density Parity Check Codes (A Survey).
Electronic Colloquium on Computational Complexity (ECCC) 13(123): (2006) |
| 86 | | Venkatesan Guruswami,
Christopher Umans,
Salil P. Vadhan:
Extractors and condensers from univariate polynomials.
Electronic Colloquium on Computational Complexity (ECCC) 13(134): (2006) |
| 85 | | Venkatesan Guruswami,
Kunal Talwar:
Hardness of Low Congestion Routing in Directed Graphs.
Electronic Colloquium on Computational Complexity (ECCC) 13(141): (2006) |
| 84 | | Venkatesan Guruswami:
Algorithmic Results in List Decoding.
Foundations and Trends in Theoretical Computer Science 2(2): (2006) |
| 83 | | Venkatesan Guruswami,
Atri Rudra:
Limits to List Decoding Reed-Solomon Codes.
IEEE Transactions on Information Theory 52(8): 3642-3649 (2006) |
| 82 | | Ioannis Giotis,
Venkatesan Guruswami:
Correlation Clustering with a Fixed Number of Clusters.
Theory of Computing 2(1): 249-266 (2006) |
| 2005 |
|---|
| 81 | | Venkatesan Guruswami,
Atri Rudra:
Tolerant Locally Testable Codes.
APPROX-RANDOM 2005: 306-317 |
| 80 | | Venkatesan Guruswami,
Salil P. Vadhan:
A Lower Bound on List Size for List Decoding.
APPROX-RANDOM 2005: 318-329 |
| 79 | | Venkatesan Guruswami,
Luca Trevisan:
The Complexity of Making Unique Choices: Approximating 1-in- k SAT.
APPROX-RANDOM 2005: 99-110 |
| 78 | | Venkatesan Guruswami,
Subhash Khot:
Hardness of Max 3SAT with No Mixed Clauses.
IEEE Conference on Computational Complexity 2005: 154-162 |
| 77 | | 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 | | Venkatesan Guruswami,
Alexander Vardy:
Maximum-likelihood decoding of Reed-Solomon codes is NP-hard.
SODA 2005: 470-478 |
| 75 | | Venkatesan Guruswami,
Atri Rudra:
Limits to list decoding Reed-Solomon codes.
STOC 2005: 602-609 |
| 74 | | Ioannis Giotis,
Venkatesan Guruswami:
Correlation Clustering with a Fixed Number of Clusters
CoRR abs/cs/0504023: (2005) |
| 73 | | Venkatesan Guruswami,
Atri Rudra:
Explicit Codes Achieving List Decoding Capacity: Error-correction with Optimal Redundancy
CoRR abs/cs/0511072: (2005) |
| 72 | | Venkatesan Guruswami,
Daniele Micciancio,
Oded Regev:
The complexity of the covering radius problem.
Computational Complexity 14(2): 90-121 (2005) |
| 71 | | Venkatesan Guruswami,
Atri Rudra:
Tolerant Locally Testable Codes
Electronic Colloquium on Computational Complexity (ECCC)(019): (2005) |
| 70 | | Venkatesan Guruswami,
Valentine Kabanets:
Hardness amplification via space-efficient direct products
Electronic Colloquium on Computational Complexity (ECCC)(057): (2005) |
| 69 | | Venkatesan Guruswami:
Algebraic-geometric generalizations of the Parvaresh-Vardy codes
Electronic Colloquium on Computational Complexity (ECCC)(132): (2005) |
| 68 | | Venkatesan Guruswami,
Atri Rudra:
Explicit Capacity-Achieving List-Decodable Codes
Electronic Colloquium on Computational Complexity (ECCC)(133): (2005) |
| 67 | | Venkatesan Guruswami,
Piotr Indyk:
Linear-time encodable/decodable codes with near-optimal rate.
IEEE Transactions on Information Theory 51(10): 3393-3400 (2005) |
| 66 | | 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 | | Moses Charikar,
Venkatesan Guruswami,
Anthony Wirth:
Clustering with qualitative information.
J. Comput. Syst. Sci. 71(3): 360-383 (2005) |
| 64 | | 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 | | Venkatesan Guruswami,
Piotr Indyk:
Linear-Time List Decoding in Error-Free Settings: (Extended Abstract).
ICALP 2004: 695-707 |
| 61 | | 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 | | Venkatesan Guruswami,
Piotr Indyk:
Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates.
SODA 2004: 756-757 |
| 59 | | Venkatesan Guruswami:
Better extractors for better codes?
STOC 2004: 436-444 |
| 58 | | Venkatesan Guruswami,
Alexander Vardy:
Maximum-likelihood decoding of Reed-Solomon Codes is NP-hard
CoRR cs.CC/0405005: (2004) |
| 57 | | Venkatesan Guruswami,
Alexander Vardy:
Maximum-likelihood decoding of Reed-Solomon codes is NP-hard
Electronic Colloquium on Computational Complexity (ECCC)(040): (2004) |
| 56 | | Edith Cohen,
Venkatesan Guruswami:
Guest Editors' foreword.
J. Comput. Syst. Sci. 68(4): 701 (2004) |
| 55 | | Lars Engebretsen,
Venkatesan Guruswami:
Is constraint satisfaction over two variables always easy?
Random Struct. Algorithms 25(2): 150-178 (2004) |
| 54 | | Venkatesan Guruswami,
Sanjeev Khanna:
On the Hardness of 4-Coloring a 3-Colorable Graph.
SIAM J. Discrete Math. 18(1): 30-40 (2004) |
| 53 | | Venkatesan Guruswami:
Guest column: error-correcting codes and expander graphs.
SIGACT News 35(3): 25-41 (2004) |
| 2003 |
|---|
| 52 | | Moses Charikar,
Venkatesan Guruswami,
Anthony Wirth:
Clustering with Qualitative Information.
FOCS 2003: 524-533 |
| 51 | | Venkatesan Guruswami:
List Decoding with Side Information.
IEEE Conference on Computational Complexity 2003: 300- |
| 50 | | Venkatesan Guruswami,
Piotr Indyk:
Embeddings and non-approximability of geometric problems.
SODA 2003: 537-538 |
| 49 | | Venkatesan Guruswami,
Igor Shparlinski:
Unconditional proof of tightness of Johnson bound.
SODA 2003: 754-755 |
| 48 | | Venkatesan Guruswami,
Piotr Indyk:
Linear time encodable and list decodable codes.
STOC 2003: 126-135 |
| 47 | | Irit Dinur,
Venkatesan Guruswami,
Subhash Khot,
Oded Regev:
A new multilayered PCP and the hardness of hypergraph vertex cover.
STOC 2003: 595-601 |
| 46 | | Venkatesan Guruswami:
Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses.
Algorithmica 38(3): 451-469 (2003) |
| 45 | | 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 | | 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 | | 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 | | Venkatesan Guruswami,
Madhu Sudan:
Decoding Concatenated Codes using Soft Information.
IEEE Conference on Computational Complexity 2002: 148-157 |
| 39 | | Lars Engebretsen,
Venkatesan Guruswami:
Is Constraint Satisfaction Over Two Variables Always Easy?
RANDOM 2002: 224-238 |
| 38 | | Noga Alon,
Venkatesan Guruswami,
Tali Kaufman,
Madhu Sudan:
Guessing secrets efficiently via list decoding.
SODA 2002: 254-262 |
| 37 | | Venkatesan Guruswami:
Limits to list decodability of linear codes.
STOC 2002: 802-811 |
| 36 | | 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 | | 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 | | 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 | | 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 | | Venkatesan Guruswami,
Johan Håstad,
Madhu Sudan:
Hardness of Approximate Hypergraph Coloring.
SIAM J. Comput. 31(6): 1663-1686 (2002) |
| 2001 |
|---|
| 30 | | 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 | | Venkatesan Guruswami:
List Decoding from Erasures: Bounds and Code Constructions.
FSTTCS 2001: 195-206 |
| 27 | | 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 | | 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 | | 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) |
