| 2026 | CP | Classification of Non-Redundancy of Boolean Predicates of Arity 4. | Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman |
| 2026 | ICALP | Multiplicative Error Set System Sparsification: A Simpler Proof via Chain Length Contraction. | Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman |
| 2026 | SODA | New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs. | Joshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami, Aaron Potechin, Stanislav Zivn |
| 2026 | SODA | Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case. | Venkatesan Guruswami, Xin Lyu, Weiqiang Yuan |
| 2026 | STOC | Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes. | Rohan Goyal, Venkatesan Guruswami |
| 2026 | SPAA | Brief Announcement: Scheduling Problems with Constrained Rejections. | Sami Davies, Venkatesan Guruswami, Xuandi Ren |
| 2025 | FOCS | Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices. | Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee, Xuandi Ren |
| 2025 | FOCS | Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks. | Louis Golowich, Venkatesan Guruswami |
| 2025 | IPCO | Semirandom Planted Clique via 1-Norm Isometry Property. | Venkatesan Guruswami, Hsin-Po Wang |
| 2025 | SODA | Quantum Locally Recoverable Codes. | Louis Golowich, Venkatesan Guruswami |
| 2025 | STOC | Redundancy Is All You Need. | Joshua Brakensiek, Venkatesan Guruswami |
| 2025 | STOC | Asymptotically Good Quantum Codes with Transversal Non-Clifford Gates. | Louis Golowich, Venkatesan Guruswami |
| 2025 | STOC | Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH. | Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu |
| 2024 | ESA | Outlier Robust Multivariate Polynomial Regression. | Vipul Arora, Arnab Bhattacharyya, Mathews Boban, Venkatesan Guruswami, Esty Kelman |
| 2024 | FOCS | Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles. | Omar Alrabiah, Venkatesan Guruswami |
| 2024 | FOCS | Decoding Quasi-Cyclic Quantum LDPC Codes. | Louis Golowich, Venkatesan Guruswami |
| 2024 | FOCS | Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the √n Dimension Threshold. | Venkatesan Guruswami, Jun-Ting Hsieh, Prasad Raghavendra |
| 2024 | ISIT | Successive Cancellation Sampling Decoder: An Attempt to Analyze List Decoding Theoretically. | Hsin-Po Wang, Venkatesan Guruswami |
| 2024 | ISIT | Isolate and then Identify: Rethinking Adaptive Group Testing. | Hsin-Po Wang, Venkatesan Guruswami |
| 2024 | SODA | AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets. | Omar Alrabiah, Venkatesan Guruswami, Ray Li |
| 2024 | STOC | Randomly Punctured Reed-Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields. | Omar Alrabiah, Venkatesan Guruswami, Ray Li |
| 2024 | STOC | Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis. | Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu |
| 2023 | FOCS | Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold. | Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, Peter Manohar |
| 2023 | ISIT | On expanding the toolkit of locality-based coded computation to the coordinates of inputs. | Michael Rudow, Venkatesan Guruswami, K. V. Rashmi |
| 2023 | ISIT | How Many Matrices Should I Prepare To Polarize Channels Optimally Fast? | Hsin-Po Wang, Venkatesan Guruswami |
| 2023 | ISIT | Quickly-Decodable Group Testing with Fewer Tests: Price-Scarlett's Nonadaptive Splitting with Explicit Scalars. | Hsin-Po Wang, Ryan Gabrys, Venkatesan Guruswami |
| 2023 | STOC | A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation. | Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar |
| 2023 | STOC | Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓ | Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, Joo Ribeiro |
| 2023 | STOC | SDPs and Robust Satisfiability of Promise CSP. | Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep |
| 2023 | STOC | Binary Error-Correcting Codes with Minimal Noiseless Feedback. | Meghal Gupta, Venkatesan Guruswami, Rachel Yun Zhang |
| 2022 | FOCS | Punctured Low-Bias Codes Behave Like Random Linear Codes. | Venkatesan Guruswami, Jonathan Mosheiff |
| 2022 | SODA | Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture. | Venkatesan Guruswami, Sai Sandeep |
| 2022 | STOC | Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random. | Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar |
| 2021 | FOCS | The zero-rate threshold for adversarial bit-deletions is less than 1/2. | Venkatesan Guruswami, Xiaoyu He, Ray Li |
| 2021 | ICALP | Conditional Dichotomy of Boolean Ordered Promise CSPs. | Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep |
| 2021 | ISIT | Linear Shannon Capacity of Cayley Graphs. | Venkatesan Guruswami, Andrii Riazanov |
| 2021 | ISIT | Linear Programming Bounds for Almost-Balanced Binary Codes. | Venkatesan Guruswami, Andrii Riazanov |
| 2021 | ISIT | A locality-based lens for coded computation. | Michael Rudow, K. V. Rashmi, Venkatesan Guruswami |
| 2021 | SODA | Strongly refuting all semi-random Boolean CSPs. | Jackson Abascal, Venkatesan Guruswami, Pravesh K. Kothari |
| 2021 | SODA | Efficient Linear and Affine Codes for Correcting Insertions/Deletions. | Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler, Xin Li |
| 2021 | SODA | Explicit two-deletion codes with redundancy matching the existential bound. | Venkatesan Guruswami, Johan Hstad |
| 2020 | ICALP | d-To-1 Hardness of Coloring 3-Colorable Graphs with O(1) Colors. | Venkatesan Guruswami, Sai Sandeep |
| 2020 | SODA | Symmetric Polymorphisms and Efficient Decidability of Promise CSPs. | Joshua Brakensiek, Venkatesan Guruswami |
| 2020 | STOC | Optimally resilient codes for list-decoding from insertions and deletions. | Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi |
| 2020 | STOC | Arikan meets Shannon: polar codes with near-optimal convergence to channel capacity. | Venkatesan Guruswami, Andrii Riazanov, Min Ye |
| 2019 | ICALP | Constructions of Maximally Recoverable Local Reconstruction Codes via Function Fields. | Venkatesan Guruswami, Lingfei Jin, Chaoping Xing |
| 2019 | ICALP | Beating Fredman-Komls for Perfect k-Hashing. | Venkatesan Guruswami, Andrii Riazanov |
| 2019 | ISIT | Near-optimal Repair of Reed-Solomon Codes with Low Sub-packetization. | Venkatesan Guruswami, Haotian Jiang |
| 2019 | SODA | Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness. | Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani |
| 2019 | SODA | An Algorithmic Blend of LPs and Ring Equations for Promise CSPs. | Joshua Brakensiek, Venkatesan Guruswami |
| 2019 | SODA | Maximally Recoverable LRCs: A field size lower bound and constructions for few heavy parities. | Sivakanth Gopi, Venkatesan Guruswami, Sergey Yekhanin |
| 2019 | STOC | An exponential lower bound on the sub-packetization of MSR codes. | Omar Alrabiah, Venkatesan Guruswami |
| 2019 | STOC | Bridging between 0/1 and linear programming via random walks. | Joshua Brakensiek, Venkatesan Guruswami |
| 2019 | STOC | CSPs with global modular constraints: algorithms and hardness via polynomial representations. | Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami |
| 2018 | ISIT | ∊-MSR Codes: Contacting Fewer Code Blocks for Exact Repair. | Venkatesan Guruswami, Satyanarayana V. Lokam, Sai Vikneshwar Mani Jayaraman |
| 2018 | ISIT | On the List-Decodability of Random Linear Rank-Metric Codes. | Venkatesan Guruswami, Nicolas Resch |
| 2018 | SODA | Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy. | Joshua Brakensiek, Venkatesan Guruswami |
| 2018 | SODA | Coding against deletions in oblivious and online models. | Venkatesan Guruswami, Ray Li |
| 2018 | STOC | General strong polarization. | Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan |
| 2017 | FOCS | Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere. | Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani |
| 2017 | ICALP | Subspace Designs Based on Algebraic Function Fields. | Venkatesan Guruswami, Chaoping Xing, Chen Yuan |
| 2017 | ISIT | An improved bound on the zero-error list-decoding capacity of the 4/3 channel. | Marco Dalai, Venkatesan Guruswami, Jaikumar Radhakrishnan |
| 2017 | ISIT | ∊-MSR codes with small sub-packetization. | Ankit Singh Rawat, Itzhak Tamo, Venkatesan Guruswami, Klim Efremenko |
| 2017 | SODA | MDS Code Constructions with Small Sub-packetization and Near-optimal Repair Bandwidth. | Venkatesan Guruswami, Ankit Singh Rawat |
| 2016 | FOCS | Robust Fourier and Polynomial Curve Fitting. | Venkatesan Guruswami, David Zuckerman |
| 2016 | ISIT | Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes. | Venkatesan Guruswami, Ray Li |
| 2016 | SODA | Efficient Low-Redundancy Codes for Correcting Multiple Deletions. | Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky |
| 2016 | SODA | An improved bound on the fraction of correctable deletions. | Boris Bukh, Venkatesan Guruswami |
| 2016 | SODA | Nearly Optimal NP-Hardness of Unique Coverage. | Venkatesan Guruswami, Euiwoong Lee |
| 2016 | STOC | Repairing Reed-solomon codes. | Venkatesan Guruswami, Mary Wootters |
| 2015 | SODA | Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs. | Venkatesan Guruswami, Euiwoong Lee |
| 2015 | SODA | Limitations on Testable Affine-Invariant Codes in the High-Rate Regime. | Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang |
| 2014 | FOCS | (2 + epsilon)-Sat Is NP-Hard. | Per Austrin, Johan Hstad, Venkatesan Guruswami |
| 2014 | SODA | Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets. | Venkatesan Guruswami, Chaoping Xing |
| 2014 | STOC | Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. | Venkatesan Guruswami, Prahladh Harsha, Johan Hstad, Srikanth Srinivasan, Girish Varma |
| 2014 | TCC | Non-malleable Coding against Bit-Wise and Split-State Tampering. | Mahdi Cheraghchi, Venkatesan Guruswami |
| 2013 | FOCS | PCPs via Low-Degree Long Code and Hardness for Constrained Hypergraph Coloring. | Irit Dinur, Venkatesan Guruswami |
| 2013 | FOCS | Explicit Subspace Designs. | Venkatesan Guruswami, Swastik Kopparty |
| 2013 | FOCS | Polar Codes: Speed of Polarization and Polynomial Gap to Capacity. | Venkatesan Guruswami, Patrick Xia |
| 2013 | WWW | CopyCatch: stopping group attacks by spotting lockstep behavior in social networks. | Alex Beutel, Wanhong Xu, Venkatesan Guruswami, Christopher Palow, Christos Faloutsos |
| 2013 | SODA | Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. | Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker |
| 2013 | SODA | Approximating Non-Uniform Sparsest Cut Via Generalized Spectra. | Venkatesan Guruswami, Ali Kemal Sinop |
| 2013 | STOC | List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound. | Venkatesan Guruswami, Chaoping Xing |
| 2012 | FOCS | Faster SDP Hierarchy Solvers for Local Rounding Algorithms. | Venkatesan Guruswami, Ali Kemal Sinop |
| 2012 | SODA | Polynomial integrality gaps for strong SDP relaxations of Densest | Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, Venkatesan Guruswami, Yuan Zhou |
| 2012 | SODA | Bypassing UGC from some optimal geometric inapproximability results. | Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu |
| 2012 | SODA | Optimal column-based low-rank matrix reconstruction. | Venkatesan Guruswami, Ali Kemal Sinop |
| 2012 | STOC | Folded codes from function field towers and improved optimal rate list decoding. | Venkatesan Guruswami, Chaoping Xing |
| 2011 | FOCS | Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives. | Venkatesan Guruswami, Ali Kemal Sinop |
| 2011 | SODA | The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number. | Venkatesan Guruswami, Ali Kemal Sinop |
| 2011 | SODA | Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set. | Venkatesan Guruswami, Yuan Zhou |
| 2010 | FOCS | Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate. | Venkatesan Guruswami, Adam D. Smith |
| 2010 | ICALP | SDP Gaps for 2-to-1 and Other Label-Cover Variants. | Venkatesan Guruswami, Subhash Khot, Ryan O'Donnell, Preyas Popat, Madhur Tulsiani, Yi Wu |
| 2010 | ICALP | On the Inapproximability of Vertex Cover on | Venkatesan Guruswami, Rishi Saket |
| 2010 | STOC | On the list-decodability of random linear codes. | Venkatesan Guruswami, Johan Hstad, Swastik Kopparty |
| 2009 | FOCS | Agnostic Learning of Monomials by Halfspaces Is Hard. | Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu |
| 2009 | STOC | MaxMin allocation via degree lower-bounded arborescences. | MohammadHossein Bateni, Moses Charikar, Venkatesan Guruswami |
| 2009 | STOC | List decoding tensor products and interleaved codes. | Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra |
| 2009 | STOC | Artin automorphisms, cyclotomic function fields, and folded list-decodable codes. | Venkatesan Guruswami |
| 2008 | FOCS | Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph. | Venkatesan Guruswami, Rajsekar Manokaran, Prasad Raghavendra |
| 2008 | ISIT | Explicit interleavers for a Repeat Accumulate Accumulate (RAA) code construction. | Venkatesan Guruswami, Widad Machmouchi |
| 2008 | SODA | Almost Euclidean subspaces of l | Venkatesan Guruswami, James R. Lee, Alexander A. Razborov |
| 2008 | SODA | Concatenated codes can achieve list-decoding capacity. | Venkatesan Guruswami, Atri Rudra |
| 2007 | STOC | Hardness of routing with congestion in directed graphs. | Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar |
| 2007 | STOC | A 3-query PCP over integers. | Venkatesan Guruswami, Prasad Raghavendra |
| 2006 | FOCS | Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets. | Venkatesan Guruswami, Anindya C. Patthak |
| 2006 | FOCS | Hardness of Learning Halfspaces with Noise. | Venkatesan Guruswami, Prasad Raghavendra |
| 2006 | ISAAC | On 2-Query Codeword Testing with Near-Perfect Completeness. | Venkatesan Guruswami |
| 2006 | ITW | List Decoding in Average-Case Complexity and Pseudorandomness. | Venkatesan Guruswami |
| 2006 | LATIN | Algorithms for Modular Counting of Roots of Multivariate Polynomials. | Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton |
| 2006 | LATIN | Hardness Amplification Via Space-Efficient Direct Products. | Venkatesan Guruswami, Valentine Kabanets |
| 2006 | SODA | Correlation clustering with a fixed number of clusters. | Ioannis Giotis, Venkatesan Guruswami |
| 2006 | STOC | Explicit capacity-achieving list-decodable codes. | Venkatesan Guruswami, Atri Rudra |
| 2005 | SODA | On profit-maximizing envy-free pricing. | Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, Frank McSherry |
| 2005 | SODA | Maximum-likelihood decoding of Reed-Solomon codes is NP-hard. | Venkatesan Guruswami, Alexander Vardy |
| 2005 | STOC | Limits to list decoding Reed-Solomon codes. | Venkatesan Guruswami, Atri Rudra |
| 2004 | ICALP | Linear-Time List Decoding in Error-Free Settings: (Extended Abstract). | Venkatesan Guruswami, Piotr Indyk |
| 2004 | SODA | Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates. | Venkatesan Guruswami, Piotr Indyk |
| 2004 | STOC | Better extractors for better codes? | Venkatesan Guruswami |
| 2003 | FOCS | Clustering with Qualitative Information. | Moses Charikar, Venkatesan Guruswami, Anthony Wirth |
| 2003 | SODA | Embeddings and non-approximability of geometric problems. | Venkatesan Guruswami, Piotr Indyk |
| 2003 | SODA | Unconditional proof of tightness of Johnson bound. | Venkatesan Guruswami, Igor E. Shparlinski |
| 2003 | STOC | A new multilayered PCP and the hardness of hypergraph vertex cover. | Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev |
| 2003 | STOC | Linear time encodable and list decodable codes. | Venkatesan Guruswami, Piotr Indyk |
| 2002 | SODA | Guessing secrets efficiently via list decoding. | Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan |
| 2002 | STOC | Limits to list decodability of linear codes. | Venkatesan Guruswami |
| 2002 | STOC | Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. | Venkatesan Guruswami, Piotr Indyk |
| 2001 | FOCS | Expander-Based Constructions of Efficiently Decodable Codes. | Venkatesan Guruswami, Piotr Indyk |
| 2000 | ESA | On Representations of Algebraic-Geometric Codes for List Decoding. | Venkatesan Guruswami, Madhu Sudan |
| 2000 | FOCS | Combinatorial feature selection problems. | Moses Charikar, Venkatesan Guruswami, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai |
| 2000 | FOCS | Hardness of Approximate Hypergraph Coloring. | Venkatesan Guruswami, Johan Hstad, Madhu Sudan |
| 2000 | FOCS | "Soft-decision" Decoding of Chinese Remainder Codes. | Venkatesan Guruswami, Amit Sahai, Madhu Sudan |
| 2000 | STOC | Query strategies for priced information (extended abstract). | Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M. Kleinberg, Prabhakar Raghavan, Amit Sahai |
| 2000 | STOC | List decoding algorithms for certain concatenated codes. | Venkatesan Guruswami, Madhu Sudan |
| 1999 | COLT | Multiclass Learning, Boosting, and Error-Correcting Codes. | Venkatesan Guruswami, Amit Sahai |
| 1999 | SODA | The 2-Catalog Segmentation Problem. | Yevgeniy Dodis, Venkatesan Guruswami, Sanjeev Khanna |
| 1999 | STOC | Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. | Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis |
| 1998 | FOCS | A Tight Characterization of NP with 3 Query PCPs. | Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan |
| 1998 | FOCS | Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes. | Venkatesan Guruswami, Madhu Sudan |
| 1998 | WG | The Vertex-Disjoint Triangles Problem. | Venkatesan Guruswami, C. Pandu Rangan, Maw-Shang Chang, Gerard J. Chang, C. K. Wong |