Journal Article PCPs via the low-degree long code and hardness for constrained hypergraph coloring 2015 • Israel Journal of Mathematics • 209(2):611-649 Dinur I, Guruswami V
Journal Article Polar Codes: Speed of Polarization and Polynomial Gap to Capacity 2015 • IEEE Transactions on Information Theory • 61(1):3-16 Guruswami V, Xia P
Conference Preface 2015 • Annual Symposium on Foundations of Computer Science • 2015-December:xii Guruswami V
Conference Strong inapproximability results on balanced rainbow-colorable hypergraphs 2015 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 2015-January(January):822-836 Guruswami V, Lee E
Conference Towards a characterization of approximation resistance for Symmetric CSPs 2015 • Leibniz International Proceedings in Informatics • 40:305-322 Guruswami V, Lee E
Conference (2+ε)-SAT is NP-hard 2014 • Annual Symposium on Foundations of Computer Science • 1-10 Austrin P, Guruswami V, Hastad J
Journal Article An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets 2014 Guruswami V, Velingker A
Journal Article Capacity of non-malleable codes 2014 • ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science • 155-168 Cheraghchi M, Guruswami V
Journal Article Combinatorial Limitations of Average-Radius List-Decoding 2014 • IEEE Transactions on Information Theory • 60(10):5827-5842 Guruswami V, Narayanan S
Conference Complexity of approximating CSP with balance / Hard constraints 2014 • ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science • 439-448 Guruswami V, Lee E
Journal Article CONSTANT FACTOR LASSERRE INTEGRALITY GAPS FOR GRAPH PARTITIONING PROBLEMS 2014 • SIAM Journal on Optimization • 24(4):1698-1717 Guruswami V, Sinop AK, Zhou Y
Conference Evading subspaces over large fields and explicit list-decodable rank-metric codes 2014 • Leibniz International Proceedings in Informatics • 28:748-761 Guruswami V, Wang C
Conference Hitting Sets for Low-Degree Polynomials with Optimal Density 2014 • Proceedings of the Annual IEEE Conference on Computational Complexity • 161-168 Guruswami V, Xing C
Journal Article Non-malleable Coding against Bit-Wise and Split-State Tampering 2014 • Lecture Notes in Computer Science • 8349:440-464 Cheraghchi M, Guruswami V
Conference Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets 2014 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 1858-1866 Guruswami V, Xing C
Journal Article Super-polylogarithmic hypergraph coloring hardness via low-degree long codes 2014 • Annual ACM Symposium on Theory of Computing • 614-623 Guruswami V, Harsha P, Hastad J, Srinivasan S, Varma G
Conference Approximating Non-Uniform Sparsest Cut via Generalized Spectra 2013 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 295-305 Guruswami V, Sinop AK
Conference Combinatorial limitations of average-radius list decoding 2013 • Lecture Notes in Computer Science • 8096 LNCS:591-606 Guruswami V, Narayanan S
Conference CopyCatch: Stopping group attacks by spotting lockstep behavior in social networks 2013 • WWW 2013 - Proceedings of the 22nd International Conference on World Wide Web • 119-129 Beutel A, Xu W, Guruswami V, Palow C, Faloutsos C
Journal Article Explicit rank-metric codes list-decodable with optimal redundancy 2013 Guruswami V, Wang C
Conference Explicit Subspace Designs 2013 • Annual Symposium on Foundations of Computer Science • 608-617 Guruswami V, Kopparty S
Journal Article Linear-Algebraic List Decoding for Variants of Reed-Solomon Codes 2013 • IEEE Transactions on Information Theory • 59(6):3257-3268 Guruswami V, Wang C
Conference List decoding Reed-Solomon, Algebraic -Geometric, and Gabidulin subcodes up to the Singleton bound 2013 • Annual ACM Symposium on Theory of Computing • 843-852 Guruswami V, Xing C
