Journal Article Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture 2020 Guruswami V, Sandeep S
Conference Arikan Meets Shannon: Polar Codes with Near-Optimal Convergence to Channel Capacity 2020 • Annual ACM Symposium on Theory of Computing • 552-564 Guruswami V, Riazanov A, Ye M
Journal Article Bounds for list-decoding and list-recovery of random linear codes 2020 • Leibniz International Proceedings in Informatics • 176: Guruswami V, Li R, Mosheiff J, Resch N, Silas S, Wootters M
Journal Article Coding Against Deletions in Oblivious and Online Models 2020 • IEEE Transactions on Information Theory • 66(4):2352-2374 Guruswami V, Li R
Journal Article Constructions of Maximally Recoverable Local Reconstruction Codes via Function Fields 2020 • IEEE Transactions on Information Theory • 66(10):6133-6143 Guruswami V, Jin L, Xing C
Conference d-To-1 hardness of coloring 3-colorable graphs with O(1) colors 2020 • Leibniz International Proceedings in Informatics • 168: Guruswami V, Sandeep S
Journal Article Leakage-resilient secret sharing in non-compartmentalized models 2020 • Leibniz International Proceedings in Informatics • 163: Lin F, Cheraghchi M, Guruswami V, Safavi-Naini R, Wang H
Journal Article Maximally Recoverable LRCs: A Field Size Lower Bound and Constructions for Few Heavy Parities 2020 • IEEE Transactions on Information Theory • 66(10):6066-6083 Gopi S, Guruswami V, Yekhanin S
Journal Article Optimally Resilient Codes for List-Decoding from Insertions and Deletions 2020 • Annual ACM Symposium on Theory of Computing • 524-537 Guruswami V, Haeupler B, Shahrasbi A
Journal Article RAINBOW COLORING HARDNESS VIA LOW SENSITIVITY POLYMORPHISMS 2020 • SIAM Journal on Discrete Mathematics • 34(1):520-537 Guruswami V, Sandeep S
Conference Revisiting alphabet reduction in Dinur's PCP 2020 • Leibniz International Proceedings in Informatics • 176: Guruswami V, Opršal J, Sandeep S
Conference Symmetric Polymorphisms and Efficient Decidability of Promise CSPs 2020 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 297-304 Brakensiek J, Guruswami V
Journal Article THE POWER OF THE COMBINED BASIC LINEAR PROGRAMMING AND AFFINE RELAXATION FOR PROMISE CONSTRAINT SATISFACTION PROBLEMS 2020 • SIAM journal on computing (Print) • 49(6):1232-1248 Brakensiek J, Guruswami V, Wrochna M, Zivny S
Journal Article ε-MSR Codes: Contacting Fewer Code Blocks for Exact Repair 2020 • IEEE Transactions on Information Theory • 66(11):6749-6761 Guruswami V, Lokam SV, Jayaraman SVM
Journal Article Algorithmic polarization for hidden markov models 2019 • Leibniz International Proceedings in Informatics • 124: Guruswami V, Nakkiran P, Sudan M
Journal Article An algorithmic blend of LPS and ring equations for pROMISE CSPs 2019 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 436-455 Brakensiek J, Guruswami V
Journal Article An Exponential Lower Bound on the Sub-Packetization of MSR Codes 2019 • Annual ACM Symposium on Theory of Computing • 979-985 Alrabiah O, Guruswami V
Conference Approximability of P → Q matrix norms: Generalized krivine rounding and hypercontractive hardness 2019 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 1358-1368 Bhattiprolu V, Ghosh M, Guruswami V, Lee E, Tulsiani M
Journal Article Arıkan meets Shannon: Polar codes with near-optimal convergence to channel capacity 2019 Guruswami V, Riazanov A, Ye M
Journal Article Beating Fredman-Komlós for perfect k-hashing 2019 • Leibniz International Proceedings in Informatics • 132: Guruswami V, Riazanov A
Journal Article Bridging between 0/1 and Linear Programming via Random Walks 2019 • Annual ACM Symposium on Theory of Computing • 568-577 Brakensiek J, Guruswami V
Journal Article Constructions of maximally recoverable local reconstruction codes via function fields 2019 • Leibniz International Proceedings in Informatics • 132: Guruswami V, Jin L, Xing C
Journal Article CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations 2019 • Annual ACM Symposium on Theory of Computing • 590-601 Brakensiek J, Gopi S, Guruswami V
Journal Article How Long Can Optimal Locally Repairable Codes Be? 2019 • IEEE Transactions on Information Theory • 65(6):3662-3670 Guruswami V, Xing C, Yuan C
