| 2026 | STOC | Ideals, Macaulay Bases, and PCPs. | Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, Sophus Valentin Willumsgaard |
| 2025 | FOCS | Lower Bounds for Non-adaptive Local Computation Algorithms. | Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, Madhu Sudan |
| 2025 | ICALP | A Near-Optimal Polynomial Distance Lemma over Boolean Slices. | Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan |
| 2025 | ICALP | A Theory of Spectral CSP Sparsification. | Sanjeev Khanna, Aaron Putterman, Madhu Sudan |
| 2025 | ICALP | Near-Optimal Hypergraph Sparsification in Insertion-Only and Bounded-Deletion Streams. | Sanjeev Khanna, Aaron Putterman, Madhu Sudan |
| 2025 | SODA | Low Degree Local Correction Over the Boolean Cube. | Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan |
| 2025 | SODA | Streaming Algorithms via Local Algorithms for Maximum Directed Cut. | Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy |
| 2025 | STOC | Improved PIR Schemes using Matching Vectors and Derivatives. | Fatemeh Ghasemi, Swastik Kopparty, Madhu Sudan |
| 2025 | STOC | Efficient Algorithms and New Characterizations for CSP Sparsification. | Sanjeev Khanna, Aaron Putterman, Madhu Sudan |
| 2024 | COLT | Errors are Robustly Tamed in Cumulative Knowledge Processes. | Anna M. Brandenberger, Cassandra Marcussen, Elchanan Mossel, Madhu Sudan |
| 2024 | FOCS | An Improved Line-Point Low-Degree Test. | Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan |
| 2024 | FOCS | Near-Optimal Size Linear Sketches for Hypergraph Cut Sparsifiers. | Sanjeev Khanna, Aaron Putterman, Madhu Sudan |
| 2024 | ICALP | Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs. | Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan |
| 2024 | ISIT | On $k$-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction. | Kuan Cheng, Elena Grigorescu, Xin Li, Madhu Sudan, Minshen Zhu |
| 2024 | SODA | Code Sparsification and its Applications. | Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan |
| 2024 | STOC | Local Correction of Linear Functions over the Boolean Cube. | Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan |
| 2023 | FOCS | Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots. | Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy |
| 2023 | SODA | Streaming complexity of CSPs with randomly ordered constraints. | Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy |
| 2022 | ICALP | Streaming and Sketching Complexity of CSPs: A Survey (Invited Talk). | Madhu Sudan |
| 2022 | STOC | Linear space streaming lower bounds for approximating CSPs. | Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy |
| 2021 | FOCS | Approximability of all finite CSPs with linear sketches. | Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy |
| 2021 | ISIT | Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance. | Elena Grigorescu, Madhu Sudan, Minshen Zhu |
| 2021 | STOC | Decoding multivariate multiplicity codes on product sets. | Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan |
| 2020 | SODA | Round Complexity of Common Randomness Generation: The Amortized Setting. | Noah Golowich, Madhu Sudan |
| 2019 | FOCS | Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time. | Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, Madhu Sudan |
| 2019 | SODA | Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation. | Madhu Sudan, Badih Ghazi, Noah Golowich, Mitali Bafna |
| 2018 | ICALP | Synchronization Strings: List Decoding for Insertions and Deletions. | Bernhard Haeupler, Amirbehshad Shahrasbi, Madhu Sudan |
| 2018 | STOC | General strong polarization. | Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan |
| 2017 | ICALP | The Power of Shared Randomness in Uncertain Communication. | Badih Ghazi, Madhu Sudan |
| 2017 | SODA | (1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space. | Michael Kapralov, Sanjeev Khanna, Madhu Sudan, Ameya Velingker |
| 2016 | FOCS | Decidability of Non-interactive Simulation of Joint Distributions. | Badih Ghazi, Pritish Kamath, Madhu Sudan |
| 2016 | SODA | Communication with Contextual Uncertainty. | Badih Ghazi, Ilan Komargodski, Pravesh Kothari, Madhu Sudan |
| 2016 | SODA | Communication Complexity of Permutation-Invariant Functions. | Badih Ghazi, Pritish Kamath, Madhu Sudan |
| 2015 | FOCS | Robust Testing of Lifted Codes with Applications to Low-Degree Testing. | Alan Guo, Elad Haramaty, Madhu Sudan |
| 2015 | SODA | Limitations on Testable Affine-Invariant Codes in the High-Rate Regime. | Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang |
| 2015 | SODA | Streaming Lower Bounds for Approximating MAX-CUT. | Michael Kapralov, Sanjeev Khanna, Madhu Sudan |
| 2014 | SODA | Approximating matching size from random streams. | Michael Kapralov, Sanjeev Khanna, Madhu Sudan |
| 2014 | STOC | Optimal error rates for interactive coding I: adaptivity and other settings. | Mohsen Ghaffari, Bernhard Haeupler, Madhu Sudan |
| 2012 | FOCS | Sparse Affine-Invariant Linear Codes Are Locally Testable. | Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan |
| 2012 | ITW | Communication amid uncertainty. | Madhu Sudan |
| 2011 | FOCS | Optimal Testing of Multivariate Polynomials over Small Prime Fields. | Elad Haramaty, Amir Shpilka, Madhu Sudan |
| 2011 | FOCS | Delays and the Capacity of Continuous-Time Channels. | Sanjeev Khanna, Madhu Sudan |
| 2011 | PODC | A theory of goal-oriented communication. | Oded Goldreich, Brendan Juba, Madhu Sudan |
| 2010 | FOCS | Optimal Testing of Reed-Muller Codes. | Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman |
| 2010 | ISIT | Tight asymptotic bounds for the deletion channel with small deletion probabilities. | Adam Kalai, Michael Mitzenmacher, Madhu Sudan |
| 2009 | FOCS | Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers. | Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan |
| 2009 | STACS | Testing Linear-Invariant Non-Linear Properties. | Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie |
| 2008 | ISSAC | Algebraic algorithms and coding theory. | Madhu Sudan |
| 2008 | STOC | Decodability of group homomorphisms beyond the johnson bound. | Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan |
| 2008 | STOC | Universal semantic communication I. | Brendan Juba, Madhu Sudan |
| 2008 | STOC | Algebraic property testing: the role of invariance. | Tali Kaufman, Madhu Sudan |
| 2007 | CRYPTO | Amplifying Collision Resistance: A Complexity-Theoretic Treatment. | Ran Canetti, Ronald L. Rivest, Madhu Sudan, Luca Trevisan, Salil P. Vadhan, Hoeteck Wee |
| 2007 | FOCS | Sparse Random Linear Codes are Locally Decodable and Testable. | Tali Kaufman, Madhu Sudan |
| 2006 | LATIN | Modelling Errors and Recovery for Communication. | Madhu Sudan |
| 2005 | STOC | Derandomization of auctions. | Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan |
| 2005 | STOC | Simple PCPs with poly-log rate and query complexity. | Eli Ben-Sasson, Madhu Sudan |
| 2005 | TCC | Optimal Error Correction Against Computationally Bounded Noise. | Silvio Micali, Chris Peikert, Madhu Sudan, David A. Wilson |
| 2004 | STOC | Robust pcps of proximity, shorter pcps and applications to coding. | Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan |
| 2003 | STOC | Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. | Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, Avi Wigderson |
| 2003 | STOC | Reconstructing curves in three (and higher) dimensional space from noisy data. | Don Coppersmith, Madhu Sudan |
| 2002 | FOCS | Locally Testable Codes and PCPs of Almost-Linear Length. | Oded Goldreich, Madhu Sudan |
| 2002 | SODA | Guessing secrets efficiently via list decoding. | Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan |
| 2002 | SODA | Harmonic broadcasting is optimal. | Lars Engebretsen, Madhu Sudan |
| 2001 | FOCS | Coding Theory: Tutorial and Survey. | Madhu Sudan |
| 2001 | STACS | Small PCPs with Low Query Complexity. | Prahladh Harsha, Madhu Sudan |
| 2000 | ESA | On Representations of Algebraic-Geometric Codes for List Decoding. | Venkatesan Guruswami, Madhu Sudan |
| 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 | Random walks with "back buttons" (extended abstract). | Ronald Fagin, Anna R. Karlin, Jon M. Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, Madhu Sudan, Andrew Tomkins |
| 2000 | STOC | List decoding algorithms for certain concatenated codes. | Venkatesan Guruswami, Madhu Sudan |
| 1999 | FOCS | Hardness of Approximating the Minimum Distance of a Linear Code. | Ilya Dumer, Daniele Micciancio, Madhu Sudan |
| 1999 | STOC | Chinese Remaindering with Errors. | Oded Goldreich, Dana Ron, Madhu Sudan |
| 1999 | STOC | Pseudorandom Generators Without the XOR Lemma (Extended Abstract). | Madhu Sudan, Luca Trevisan, Salil P. Vadhan |
| 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 | FOCS | Probabilistically Checkable Proofs with Low Amortized Query Complexity. | Madhu Sudan, Luca Trevisan |
| 1997 | INFOCOM | Gateway Based Approach for Conducting Multiparty Multimedia Sessions over Heterogeneous Signaling Domains. | Madhu Sudan, Nachum Shacham |
| 1997 | STOC | Improved Low-Degree Testing and its Applications. | Sanjeev Arora, Madhu Sudan |
| 1997 | STOC | A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. | Sanjeev Khanna, Madhu Sudan, David P. Williamson |
| 1996 | FOCS | Maximum Likelihood Decoding of Reed Solomon Codes. | Madhu Sudan |
| 1996 | FOCS | Gadgets, Approximation, and Linear Programming (extended abstract). | Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson |
| 1996 | STOC | Adversarial Queueing Theory. | Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson |
| 1995 | ESA | A Geometric Approach to Betweenness. | Benny Chor, Madhu Sudan |
| 1995 | FOCS | Linearity Testing in Characteristic Two. | Mihir Bellare, Don Coppersmith, Johan Hstad, Marcos A. Kiwi, Madhu Sudan |
| 1995 | FOCS | Free Bits, PCPs and Non-Approximability - Towards Tight Results. | Mihir Bellare, Oded Goldreich, Madhu Sudan |
| 1995 | FOCS | Private Information Retrieval. | Benny Chor, Oded Goldreich, Eyal Kushilevitz, Madhu Sudan |
| 1995 | FOCS | Learning Polynomials with Queries: The Highly Noisy Case. | Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan |
| 1995 | IPCO | Approximating Minimum Feedback Sets and Multi-Cuts in Directed Graphs. | Guy Even, Joseph Naor, Baruch Schieber, Madhu Sudan |
| 1995 | SODA | Guaranteeing Fair Service to Persistent Dependent Tasks. | Amotz Bar-Noy, Alain J. Mayer, Baruch Schieber, Madhu Sudan |
| 1994 | FOCS | Priority Encoding Transmission | Andres Albanese, Johannes Blmer, Jeff Edmonds, Michael Luby, Madhu Sudan |
| 1994 | FOCS | Approximate Graph Coloring by Semidefinite Programming | David R. Karger, Rajeev Motwani, Madhu Sudan |
| 1994 | FOCS | On Syntactic versus Computational Views of Approximability | Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani |
| 1994 | FOCS | Motion Planning on a Graph (Extended Abstract) | Christos H. Papadimitriou, Prabhakar Raghavan, Madhu Sudan, Hisao Tamaki |
| 1994 | SODA | Efficient Routing and Scheduling Algorithms for Optical Networks. | Alok Aggarwal, Amotz Bar-Noy, Don Coppersmith, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan |
| 1994 | STOC | Improved non-approximability results. | Mihir Bellare, Madhu Sudan |
| 1994 | STOC | The minimum latency problem. | Avrim Blum, Prasad Chalasani, Don Coppersmith, William R. Pulleyblank, Prabhakar Raghavan, Madhu Sudan |
| 1992 | FOCS | Reconstructing Algebraic Functions from Mixed Data | Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan |
| 1992 | FOCS | Proof Verification and Hardness of Approximation Problems | Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy |
| 1992 | SODA | Self-Testing Polynomial Functions Efficiently and Over Rational Domains. | Ronitt Rubinfeld, Madhu Sudan |
| 1991 | STOC | Self-Testing/Correcting for Polynomials and for Approximate Functions | Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson |
| 1990 | STOC | Online Algorithms for Locating Checkpoints | Marshall W. Bern, Daniel H. Greene, Arvind Raghunathan, Madhu Sudan |