Journal Article Algorithms and Certificates for Boolean CSP Refutation: Smoothed Is No Harder Than Random 2022 • Annual ACM Symposium on Theory of Computing • 678-689 Guruswami V, Kothari PK, Manohar P
Journal Article Bounds for List-Decoding and List-Recovery of Random Linear Codes 2022 • IEEE Transactions on Information Theory • 68(2):923-939 Guruswami V, Li R, Mosheiff J, Resch N, Silas S, Wootters M
Journal Article Threshold Rates for Properties of Random Codes 2022 • IEEE Transactions on Information Theory • 68(2):905-922 Guruswami V, Moshieff J, Resch N, Silas S, Wootters M
Journal Article $\ell_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices 2021 Guruswami V, Manohar P, Mosheiff J
Conference A locality-based lens for coded computation 2021 • IEEE International Symposium on Information Theory - Proceedings • 2021-July:1070-1075 Rudow M, Rashmi KV, Guruswami V
Journal Article An Exponential Lower Bound on the Sub-Packetization of Minimum Storage Regenerating Codes 2021 • IEEE Transactions on Information Theory • 67(12):8086-8093 Alrabiah O, Guruswami V
Journal Article CNF satisfiability in a subspace and related problems 2021 • Leibniz International Proceedings in Informatics • 214: Arvind V, Guruswami V
Journal Article Conditional dichotomy of boolean ordered promise CSPs 2021 • Leibniz International Proceedings in Informatics • 198: Brakensiek J, Guruswami V, Sandeep S
Journal Article Efficient linear and affine codes for correcting insertions/deletions 2021 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 1-20 Cheng K, Guruswami V, Haeupler B, Li X
Journal Article Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound 2021 • IEEE Transactions on Information Theory • 67(10):6384-6394 Guruswami V, Hastad J
Conference Explicit two-deletion codes with redundancy matching the existential bound 2021 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 21-32 Guruswami V, Håstad J
Journal Article Linear Programming Bounds for Almost-Balanced Binary Codes 2021 • IEEE International Symposium on Information Theory - Proceedings • 1302-1307 Guruswami V, Riazanov A
Journal Article Linear Shannon Capacity of Cayley Graphs 2021 • IEEE International Symposium on Information Theory - Proceedings • 988-992 Guruswami V, Riazanov A
Journal Article LOSSLESS DIMENSION EXPANDERS VIA LINEARIZED POLYNOMIALS AND SUBSPACE DESIGNS 2021 • Combinatorica • 41(4):545-579 Guruswami V, Resch N, Xing C
Journal Article Optimally Resilient Codes for List-Decoding From Insertions and Deletions 2021 • IEEE Transactions on Information Theory • 67(12):7837-7856 Guruswami V, Haeupler B, Shahrasbi A
Journal Article Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy 2021 • SIAM journal on computing (Print) • 50(6):1663-1700 Brakensiek J, Guruswami V
Conference Pseudobinomiality of the sticky random walk 2021 • Leibniz International Proceedings in Informatics • 185: Guruswami V, Kumar VM
Journal Article Punctured Low-Bias Codes Behave Like Random Linear Codes 2021 Guruswami V, Mosheiff J
Journal Article Sharp threshold rates for random codes 2021 • Leibniz International Proceedings in Informatics • 185: Guruswami V, Mosheiff J, Resch N, Silas S, Wootters M
Journal Article Strongly refuting all semi-random Boolean CSPs 2021 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 454-472 Abascal J, Guruswami V, Kothari PK
Journal Article The Quest for Strong Inapproximability Results with Perfect Completeness 2021 • ACM Transactions on Algorithms (TALG) • 17(3): Brakensiek J, Guruswami V
Journal Article The zero-rate threshold for adversarial bit-deletions is less than 1/2 2021 Guruswami V, He X, Li R
Journal Article Visible rank and codes with locality 2021 • Leibniz International Proceedings in Informatics • 207: Alrabiah O, Guruswami V
Journal Article AC-DC: Amplification Curve Diagnostics for Covid-19 Group Testing 2020 Gabrys R, Pattabiraman S, Rana V, Ribeiro J, Cheraghchi M, Guruswami V, Milenkovic O
Journal Article An Improved Bound on the Zero-Error List-Decoding Capacity of the 4/3 Channel 2020 • IEEE Transactions on Information Theory • 66(2):749-756 Dalai M, Guruswami V, Radhakrishnan J
