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: A 3-Query PCP over Integers 2009 • ACM Transactions on Computation Theory • 1(2): Guruswami V, Raghavendra P
Journal Article Improved Inapproximability Results for Maximum k-Colorable Subgraph 2009 • Lecture Notes in Computer Science Guruswami V, Sinop AK
Journal Article Improved Inapproximability Results for Maximum k-Colorable Subgraph 2009 • Lecture Notes in Computer Science • 5687:163-176 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; <sup>N</sup><inf>1</inf> 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 LNCS: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 ℓ<inf>1</inf><sup>N</sup> with sublinear randomness and error-correction over the reals 2008 • Lecture Notes in Computer Science • 5171 LNCS: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 • IEEE International Symposium on Information Theory - Proceedings • 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 ε-biased 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 LNCS:554-568 Guruswami V, Rudra A
