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 Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs 2015 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 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 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 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:591-606 Guruswami V, Narayanan S
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
