Conference PCPs via low-degree long code and hardness for constrained hypergraph coloring 2013 • Annual Symposium on Foundations of Computer Science • 340-349 Dinur I, Guruswami V
Journal Article Polar Codes: Speed of polarization and polynomial gap to capacity 2013 • Annual Symposium on Foundations of Computer Science • 310-319 Guruswami V, Xia P
Journal Article Polar Codes: Speed of polarization and polynomial gap to capacity 2013 Guruswami V, Xia P
Journal Article RESTRICTED ISOMETRY OF FOURIER MATRICES AND LIST DECODABILITY OF RANDOM LINEAR CODES 2013 • SIAM journal on computing (Print) • 42(5):1888-1914 Cheraghchi M, Guruswami V, Velingker A
Journal Article Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes 2013 • PROCEEDINGS OF THE TWENTY-FOURTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA 2013) • 432-442 Cheraghchi M, Guruswami V, Velingker A
Journal Article Rounding Lasserre SDPs using column selection and spectrum-based approximation schemes for graph partitioning and Quadratic IPs 2013 Guruswami V, Sinop AK
Conference Superlinear lower bounds for multipass graph processing 2013 • Proceedings of the Annual IEEE Conference on Computational Complexity • 287-298 Guruswami V, Onak K
Journal Article AGNOSTIC LEARNING OF MONOMIALS BY HALFSPACES IS HARD 2012 • SIAM journal on computing (Print) • 41(6):1558-1590 Feldman V, Guruswami V, Raghavendra P, Wu Y
Conference Approximating Bounded Occurrence Ordering CSPs 2012 • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) • 7408:158-169 Guruswami V, Zhou Y
Conference Bypassing UGC from some Optimal Geometric Inapproximability Results 2012 699-717 Guruswami V, Raghavendra P, Saket R, Wu Y
Journal Article Faster SDP Hierarchy Solvers for Local Rounding Algorithms 2012 • Annual Symposium on Foundations of Computer Science • 197-206 Guruswami V, Sinop AK
Journal Article Faster SDP hierarchy solvers for local rounding algorithms 2012 Guruswami V, Sinop AK
Journal Article Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding 2012 Guruswami V, Xing C
Journal Article Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding 2012 • Annual ACM Symposium on Theory of Computing • 339-350 Guruswami V, Xing C
Journal Article List decoding subspace codes from insertions and deletions 2012 183-189 Guruswami V, Narayanan S, Wang C
Journal Article Optimal Column-Based Low-Rank Matrix Reconstruction 2012 1207-1214 Guruswami V, Sinop AK
Journal Article Polynomial integrality gaps for strong SDP relaxations of Densest k -subgraph 2012 388-405 Bhaskara A, Charikar M, Guruswami V, Vijayaraghavan A, Zhou Y
Conference Preface 2012 • Proceedings of the Annual IEEE Conference on Computational Complexity • ix-ix Guruswami V
Journal Article BEATING THE RANDOM ORDERING IS HARD: EVERY ORDERING CSP IS APPROXIMATION RESISTANT 2011 • SIAM journal on computing (Print) • 40(3):878-914 Guruswami V, Hastad J, Manokaran R, Raghavendra P, Charikar M
Journal Article Hardness amplification within NP against deterministic algorithms 2011 • Journal of Computer and System Sciences • 77(1):107-121 Gopalan P, Guruswami V
Journal Article Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives 2011 Guruswami V, Sinop AK
Journal Article Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives 2011 • Annual Symposium on Foundations of Computer Science • 482-491 Guruswami V, Sinop AK
Conference Linear-algebraic list decoding of folded Reed-Solomon codes 2011 • Proceedings of the Annual IEEE Conference on Computational Complexity • 77-85 Guruswami V
Journal Article LIST DECODING TENSOR PRODUCTS AND INTERLEAVED CODES 2011 • SIAM journal on computing (Print) • 40(5):1432-1462 Gopalan P, Guruswami V, Raghavendra P
