Conference Maximum-likelihood decoding of Reed-Solomon codes is NP-hard 2005 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 470-478 Guruswami V, Vardy A
Conference On profit-maximizing envy-free pricing 2005 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 1164-1173 Guruswami V, Hartline JD, Karlin AR, Kempe D, Kenyon C, McSherry F
Journal Article The complexity of making unique choices:: Approximating 1-in-<i>k</i> SAT 2005 • Lecture Notes in Computer Science • 3624:99-110 Guruswami V, Trevisan L
Journal Article The complexity of the covering radius problem 2005 • Computational Complexity • 14(2):90-121 Guruswami V, Micciancio D, Regev O
Journal Article Tolerant locally testable codes 2005 • Lecture Notes in Computer Science • 3624:306-317 Guruswami V, Rudra A
Conference Better extractors for better codes? 2004 • Conference Proceedings of the Annual ACM Symposium on Theory of Computing • 436-444 Guruswami V
Conference Efficiently Decodable Codes Meeting Gilbert-Varshamov Bound for Low Rates 2004 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 15:749-750 Guruswami V, Indyk P
Journal Article Inapproximability results for set splitting and satisfiability problems with no mixed clauses 2004 • Algorithmica • 38(3):451-469 Guruswami V
Journal Article Is constraint satisfaction over two variables always easy? 2004 • Random structures & algorithms (Print) • 25(2):150-178 Engebretsen L, Guruswami V
Journal Article Linear-time list decoding in error-free settings - (Extended abstract) 2004 • Lecture Notes in Computer Science • 3142:695-707 Guruswami V, Indyk P
Journal Article List decoding of error-correcting codes winning thesis of the 2002 ACM doctoral disseration competition 2004 • Lecture Notes in Computer Science • 3282: Guruswami V
Journal Article On the hardness of 4-coloring a 3-colorable graph 2004 • SIAM Journal on Discrete Mathematics • 18(1):30-40 Guruswami V, Khanna S
Journal Article Special issue on FOCS 2002 - Guest editors' foreword 2004 • Journal of Computer and System Sciences • 68(4):701-701 Cohen E, Guruswami V
Conference The complexity of the covering radius problem on lattices and codes 2004 • Proceedings of the Annual IEEE Conference on Computational Complexity • 19:161-173 Guruswami V, Micciancio D, Regev O
Conference A new multilayered PCP and the hardness of hypergraph vertex cover 2003 • Conference Proceedings of the Annual ACM Symposium on Theory of Computing • 595-601 Dinur I, Khot S, Guruswami V, Regev O
Conference Clustering with Qualitative Information 2003 • Annual Symposium on Foundations of Computer Science • 524-533 Charikar M, Guruswami V, Wirth A
Conference Clustering with qualitative information 2003 • Annual Symposium on Foundations of Computer Science • 524-533 Charikar M, Guruswami V, Wirth A
Journal Article Constructions of codes from number fields 2003 • IEEE Transactions on Information Theory • 49(3):594-603 Guruswami V
Conference Embeddings and non-approximability of geometric problems 2003 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 537-538 Guruswami V, Indyk P
Conference Linear time encodable and list decodable codes 2003 • Conference Proceedings of the Annual ACM Symposium on Theory of Computing • 126-135 Guruswami V, Indyk P
Journal Article List decoding from erasures: Bounds and code constructions 2003 • IEEE Transactions on Information Theory • 49(11):2826-2833 Guruswami V
Conference List decoding with side information 2003 • Proceedings of the Annual IEEE Conference on Computational Complexity • 300-309 Guruswami V
Journal Article Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems 2003 • Journal of Computer and System Sciences • 67(3):473-496 Guruswami V, Khanna S, Rajaraman R, Shepherd B, Yannakakis M
Conference Unconditional proof of tightness of Johnson bound 2003 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 754-755 Guruswami V, Shparlinski I
Journal Article Combinatorial bounds for list decoding 2002 • IEEE Transactions on Information Theory • 48(5):1021-1034 Guruswami V, Håstad J, Sudan M, Zuckerman D
