Venkatesan Guruswami

ORCID

Publication Activity (10 Years)

Years Active: 1998-2024
Publications (10 Years): 262

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

IEEE Trans. Inf. Theory

APPROX-RANDOM

Massachusetts Institute of Technology (PHD)

Education History

Massachusetts Institute of Technology

PHD

Publications

Hsin-Po Wang, Venkatesan Guruswami
How Many Matrices Should I Prepare To Polarize Channels Optimally Fast? CoRR (2024)
Venkatesan Guruswami, Hsin-Po Wang
Capacity-Achieving Gray Codes. CoRR (2024)
Omar Alrabiah, Venkatesan Guruswami, Ray Li
Randomly Punctured Reed-Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields. STOC (2024)
Hsin-Po Wang, Ryan Gabrys, Venkatesan Guruswami
Quickly-Decodable Group Testing with Fewer Tests: Price-Scarlett and Cheraghchi-Nakos's Nonadaptive Splitting with Explicit Scalars. CoRR (2024)
Venkatesan Guruswami, Rhea Jain
Exponential Time Approximation for Coloring 3-Colorable Graphs. CoRR (2024)
Omar Alrabiah, Venkatesan Guruswami
Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles. CoRR (2024)
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu
Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis. STOC (2024)
Venkatesan Guruswami, Xuandi Ren, Sai Sandeep
Baby PIH: Parameterized Inapproximability of Min CSP. CCC (2024)
Hsin-Po Wang, Venkatesan Guruswami
Successive Cancellation Sampling Decoder: An Attempt to Analyze List Decoding Theoretically. CoRR (2024)
Omar Alrabiah, Venkatesan Guruswami
Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles. Electron. Colloquium Comput. Complex. (2024)
Meghal Gupta, Venkatesan Guruswami, Mihir Singhal
Tight bounds for stream decodable error-correcting codes. CoRR (2024)
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu
Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH. CoRR (2024)
Vipul Arora, Arnab Bhattacharyya, Mathews Boban, Venkatesan Guruswami, Esty Kelman
Outlier Robust Multivariate Polynomial Regression. CoRR (2024)
Omar Alrabiah, Venkatesan Guruswami, Ray Li
AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets. SODA (2024)
Hsin-Po Wang, Venkatesan Guruswami
Isolate and then Identify: Rethinking Adaptive Group Testing. CoRR (2024)
Venkatesan Guruswami, Rishi Saket
Hardness of Learning Boolean Functions from Label Proportions. CoRR (2024)
Venkatesan Guruswami, Jun-Ting Hsieh, Prasad Raghavendra
Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the √n Dimension Threshold. CoRR (2024)
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu
Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH. Electron. Colloquium Comput. Complex. (2024)
Louis Golowich, Venkatesan Guruswami
Quantum Locally Recoverable Codes. CoRR (2023)
Omar Alrabiah, Venkatesan Guruswami, Ray Li
AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets. CoRR (2023)
Venkatesan Guruswami, Xiaoyu He, Ray Li
The Zero-Rate Threshold for Adversarial Bit-Deletions is Less Than 1/2. IEEE Trans. Inf. Theory 69 (4) (2023)
Venkatesan Guruswami, Xuandi Ren, Sai Sandeep
Baby PIH: Parameterized Inapproximability of Min CSP. Electron. Colloquium Comput. Complex. (2023)
Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro
Norms. STOC (2023)
Venkatesan Guruswami, Shilun Li
A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble. CoRR (2023)
Vijay Bhattiprolu, Mrinal Kanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
Inapproximability of Matrix p → q Norms. SIAM J. Comput. 52 (1) (2023)
Venkatesan Guruswami, Shilun Li
A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble. APPROX/RANDOM (2023)
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
SDPs and Robust Satisfiability of Promise CSP. STOC (2023)
Ryan Gabrys, Venkatesan Guruswami, João L. Ribeiro, Ke Wu
Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions. IEEE Trans. Inf. Theory 69 (1) (2023)
Michael Rudow, Venkatesan Guruswami, K. V. Rashmi
On expanding the toolkit of locality-based coded computation to the coordinates of inputs. ISIT (2023)
Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, Peter Manohar
Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold. FOCS (2023)
Venkatesan Guruswami, Rishi Saket
Hardness of Learning Boolean Functions from Label Proportions. FSTTCS (2023)
Hsin-Po Wang, Ryan Gabrys, Venkatesan Guruswami
Quickly-Decodable Group Testing with Fewer Tests: Price-Scarlett's Nonadaptive Splitting with Explicit Scalars. ISIT (2023)
Meghal Gupta, Venkatesan Guruswami, Rachel Yun Zhang
Binary Error-Correcting Codes with Minimal Noiseless Feedback. STOC (2023)
Louis Golowich, Venkatesan Guruswami
Quantum Locally Recoverable Codes. Electron. Colloquium Comput. Complex. (2023)
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu
Parameterized Inapproximability Hypothesis under ETH. Electron. Colloquium Comput. Complex. (2023)
Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler, Xin Li
Efficient Linear and Affine Codes for Correcting Insertions/Deletions. SIAM J. Discret. Math. 37 (2) (2023)
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
Conditional Dichotomy of Boolean Ordered Promise CSPs. TheoretiCS 2 (2023)
Venkatesan Guruswami, Xuandi Ren, Sai Sandeep
Baby PIH: Parameterized Inapproximability of Min CSP. CoRR (2023)
Omar Alrabiah, Venkatesan Guruswami, Ray Li
Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fields. Electron. Colloquium Comput. Complex. (2023)
Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, Peter Manohar
Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold. CoRR (2023)
Hsin-Po Wang, Venkatesan Guruswami
How Many Matrices Should I Prepare To Polarize Channels Optimally Fast? ISIT (2023)
Nouédyn Baspin, Venkatesan Guruswami, Anirudh Krishna, Ray Li
Improved rate-distance trade-offs for quantum codes with restricted connectivity. CoRR (2023)
Omar Alrabiah, Venkatesan Guruswami, Ray Li
Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fields. CoRR (2023)
Omar Alrabiah, Venkatesan Guruswami, Ray Li
AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets. Electron. Colloquium Comput. Complex. (2023)
Venkatesan Guruswami, Hsin-Po Wang
Noise-Resilient Group Testing with Order-Optimal Tests and Fast-and-Reliable Decoding. CoRR (2023)
Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation. STOC (2023)
Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation. CoRR (2023)
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu
Parameterized Inapproximability Hypothesis under ETH. CoRR (2023)
Venkatesan Guruswami, Jonathan Moshieff, Nicolas Resch, Shashwat Silas, Mary Wootters
Threshold Rates for Properties of Random Codes. IEEE Trans. Inf. Theory 68 (2) (2022)
Venkatesan Guruswami, Andrii Riazanov, Min Ye
Arıkan Meets Shannon: Polar Codes With Near-Optimal Convergence to Channel Capacity. IEEE Trans. Inf. Theory 68 (5) (2022)
Martin Grohe, Venkatesan Guruswami, Dániel Marx, Stanislav Zivný
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201). Dagstuhl Reports 12 (5) (2022)
Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters
Bounds for List-Decoding and List-Recovery of Random Linear Codes. IEEE Trans. Inf. Theory 68 (2) (2022)
Iwan M. Duursma, Ryan Gabrys, Venkatesan Guruswami, Ting-Chun Lin, Hsin-Po Wang
Accelerating Polarization via Alphabet Extension. CoRR (2022)
Sivakanth Gopi, Venkatesan Guruswami
Improved Maximally Recoverable LRCs Using Skew Polynomials. IEEE Trans. Inf. Theory 68 (11) (2022)
Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan
General Strong Polarization. J. ACM 69 (2) (2022)
Venkatesan Guruswami, Sai Sandeep
Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture. SODA (2022)
Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João L. Ribeiro
Norms. CoRR (2022)
Venkatesan Guruswami, Jonathan Mosheiff
Punctured Low-Bias Codes Behave Like Random Linear Codes. FOCS (2022)
Venkatesan Guruswami, Xin Lyu, Xiuhan Wang
Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness. APPROX/RANDOM (2022)
Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami
Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations. SIAM J. Comput. 51 (3) (2022)
Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number. CoRR (2022)
Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, Peter Manohar
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation. Electron. Colloquium Comput. Complex. (2022)
Venkatesan Guruswami, Xin Lyu, Xiuhan Wang
Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness. Electron. Colloquium Comput. Complex. (2022)
Venkatesan Guruswami, Chaoping Xing
Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes. J. ACM 69 (2) (2022)
Ryan Gabrys, Venkatesan Guruswami, João L. Ribeiro, Ke Wu
Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions. APPROX/RANDOM (2022)
Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João L. Ribeiro
Norms. Electron. Colloquium Comput. Complex. (2022)
Vikraman Arvind, Venkatesan Guruswami
CNF Satisfiability in a Subspace and Related Problems. Algorithmica 84 (11) (2022)
Venkatesan Guruswami, Xiaoyu He, Ray Li
The zero-rate threshold for adversarial bit-deletions is less than 1/2. FOCS (2022)
Iwan M. Duursma, Ryan Gabrys, Venkatesan Guruswami, Ting-Chun Lin, Hsin-Po Wang
Accelerating Polarization via Alphabet Extension. APPROX/RANDOM (2022)
Venkatesan Guruswami, Peter Manohar, Jonathan Mosheiff
-Spread and Restricted Isometry Properties of Sparse Random Matrices. CCC (2022)
Venkatesan Guruswami, Andrii Riazanov
-hashing. J. Comb. Theory, Ser. A 188 (2022)
Meghal Gupta, Venkatesan Guruswami, Rachel Yun Zhang
Binary Error-Correcting Codes with Minimal Noiseless Feedback. CoRR (2022)
Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number. APPROX/RANDOM (2022)
Venkatesan Guruswami, Peter Manohar, Jonathan Mosheiff
-Restricted Isometry. CoRR (2022)
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
SDPs and Robust Satisfiability of Promise CSP. CoRR (2022)
Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random. STOC (2022)
Omar Alrabiah, Venkatesan Guruswami
Revisiting a Lower Bound on the Redundancy of Linear Batch Codes. Electron. Colloquium Comput. Complex. 28 (2021)
Venkatesan Guruswami, Jonathan Mosheiff
Punctured Large Distance Codes, and Many Reed-Solomon Codes, Achieve List-Decoding Capacity. Electron. Colloquium Comput. Complex. 28 (2021)
Venkatesan Guruswami, Johan Håstad
Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound. IEEE Trans. Inf. Theory 67 (10) (2021)
Venkatesan Guruswami, Xiaoyu He, Ray Li
The zero-rate threshold for adversarial bit-deletions is less than 1/2. Electron. Colloquium Comput. Complex. 28 (2021)
Venkatesan Guruswami, Nicolas Resch, Chaoping Xing
Lossless Dimension Expanders Via Linearized Polynomials and Subspace Designs. Comb. 41 (4) (2021)
Vikraman Arvind, Venkatesan Guruswami
CNF Satisfiability in a Subspace and Related Problems. CoRR (2021)
Jackson Abascal, Venkatesan Guruswami, Pravesh K. Kothari
Strongly refuting all semi-random Boolean CSPs. SODA (2021)
Vikraman Arvind, Venkatesan Guruswami
CNF Satisfiability in a Subspace and Related Problems. Electron. Colloquium Comput. Complex. 28 (2021)
Vikraman Arvind, Venkatesan Guruswami
CNF Satisfiability in a Subspace and Related Problems. IPEC (2021)
Venkatesan Guruswami, Andrii Riazanov
Linear Shannon Capacity of Cayley Graphs. ISIT (2021)
Venkatesan Guruswami, Johan Håstad
Explicit two-deletion codes with redundancy matching the existential bound. SODA (2021)
Sivakanth Gopi, Venkatesan Guruswami
Improved Maximally Recoverable LRCs using Skew Polynomials. Electron. Colloquium Comput. Complex. 28 (2021)
Ryan Gabrys, Venkatesan Guruswami, João L. Ribeiro, Ke Wu
Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions. CoRR (2021)
Venkatesan Guruswami, Andrii Riazanov
Linear Programming Bounds for Almost-Balanced Binary Codes. CoRR (2021)
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
Conditional Dichotomy of Boolean Ordered Promise CSPs. CoRR (2021)
Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
Algorithms and Certificates for Boolean CSP Refutation: "Smoothed is no harder than Random". CoRR (2021)
Joshua Brakensiek, Venkatesan Guruswami
The Quest for Strong Inapproximability Results with Perfect Completeness. ACM Trans. Algorithms 17 (3) (2021)
Venkatesan Guruswami, Vinayak Kumar
Pseudobinomiality of the Sticky Random Walk. ITCS (2021)
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
Conditional Dichotomy of Boolean Ordered Promise CSPs. Electron. Colloquium Comput. Complex. 28 (2021)
Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi
Optimally Resilient Codes for List-Decoding From Insertions and Deletions. IEEE Trans. Inf. Theory 67 (12) (2021)
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
Conditional Dichotomy of Boolean Ordered Promise CSPs. ICALP (2021)
Michael Rudow, K. V. Rashmi, Venkatesan Guruswami
A locality-based lens for coded computation. ISIT (2021)
Omar Alrabiah, Venkatesan Guruswami
Visible Rank and Codes with Locality. APPROX-RANDOM (2021)
Venkatesan Guruswami, Xiaoyu He, Ray Li
The zero-rate threshold for adversarial bit-deletions is less than 1/2. FOCS (2021)

Venkatesan Guruswami.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Venkatesan Guruswami