Publications by Venkatesan Guruswami

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 • 00: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

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

Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound

2021 • IEEE Transactions on Information Theory • 67(10):6384-6394
Guruswami V, Hastad 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

About Main page

Admissions Main page

Academics Main page

People Main page

Research Main page

Publications by Venkatesan Guruswami

Journal Article

Journal Article

Journal Article

Journal Article

Conference

Journal Article

Journal Article

Journal Article

Journal Article

Conference

Journal Article

Journal Article

Journal Article

Journal Article

Journal Article

Journal Article

Conference

Journal Article

Journal Article

Journal Article

Journal Article

Journal Article

Journal Article

Journal Article

Journal Article