Journal Article Explicit Capacity-achieving Codes for Worst-Case Additive Errors 2009 Guruswami V, Smith A
Journal Article HARDNESS OF LEARNING HALFSPACES WITH NOISE 2009 • SIAM journal on computing (Print) • 39(2):742-765 Guruswami V, Raghavendra P
Journal Article Hardness of Solving Sparse Overdetermined Linear Systems 2009 • ACM Transactions on Computation Theory • 1(2):1-20 Guruswami V, Raghavendra P
Journal Article Improved Inapproximability Results for Maximum k-Colorable Subgraph 2009 • Lecture Notes in Computer Science • 5687:163-176 Guruswami V, Sinop AK
Journal Article Improved Inapproximability Results for Maximum k-Colorable Subgraph 2009 • Lecture Notes in Computer Science Guruswami V, Sinop AK
Conference List Decoding of Binary Codes-A Brief Survey of Some Recent Results 2009 • Lecture Notes in Computer Science • 5557:97-106 Guruswami V
Conference List Decoding Tensor Products and Interleaved Codes 2009 • Annual ACM Symposium on Theory of Computing • 13-22 Gopalan P, Guruswami V, Raghavendra P
Conference Locally Testable Codes Require Redundant Testers 2009 • Proceedings of the Annual IEEE Conference on Computational Complexity • 52-+ Ben-Sasson E, Guruswami V, Kaufman T, Sudan M, Viderman M
Conference MaxMin Allocation via Degree Lower-bounded Arborescences 2009 • Annual ACM Symposium on Theory of Computing • 543-552 Bateni M, Charikar M, Guruswami V
Journal Article Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes 2009 • Journal of the ACM • 56(4): Guruswami V, Umans C, Vadhan S
Journal Article Algorithms for modular counting of roots of multivariate polynomials 2008 • Algorithmica • 50(4):479-496 Gopalan P, Guruswami V, Lipton RJ
Conference Almost euclidean subspaces of Ell; N 1 via expander codes 2008 • Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms • 353-362 Guruswami V, Lee JR, Razborov A
Journal Article Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes 2008 Guruswami V
Conference Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph 2008 • Annual Symposium on Foundations of Computer Science • 573-582 GURUSWAMI V, MANOKARAN R, RAGHAVENDRA P
Conference Concatenated codes can achieve list-decoding capacity 2008 • Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms • 258-267 Guruswami V, Rudra A
Conference Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness 2008 • Lecture Notes in Computer Science • 5171:77-90 Guruswami V, Raghavendra P
Journal Article Correlated algebraic-geometric codes: Improved list decoding over bounded alphabets 2008 • Mathematics of Computation • 77(261):447-473 Guruswami V, Patthak AC
Conference Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals 2008 • Lecture Notes in Computer Science • 5171:444-454 Guruswami V, Lee JR, Wigderson A
Journal Article Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy 2008 • IEEE Transactions on Information Theory • 54(1):135-150 Guruswami V, Rudra A
Conference Explicit Interleavers for a Repeat Accumulate Accumulate (RAA) code construction 2008 1968-1972 Guruswami V, Machmouchi W
Journal Article HARDNESS AMPLIFICATION VIA SPACE-EFFICIENT DIRECT PRODUCTS 2008 • Computational Complexity • 17(4):475-500 Guruswami V, Kabanets V
Conference Hardness Amplification within NP Against Deterministic Algorithms 2008 • Proceedings of the Annual IEEE Conference on Computational Complexity • 19-30 Gopalan P, Guruswami V
Conference Soft decoding, dual BCH codes, and better list-decodable $\varepsilon$-blascd codes 2008 • Proceedings of the Annual IEEE Conference on Computational Complexity • 163-174 Guruswami V, Rudra A
Conference A 3-query PCP over integers 2007 • Annual ACM Symposium on Theory of Computing • 198-206 Guruswami V, Raghavendra P
Conference Better Binary List-Decodable Codes Via Multilevel Concatenation 2007 • Lecture Notes in Computer Science • 4627:554-568 Guruswami V, Rudra A
