| 2025 | FOCS | List Decoding Expander-Based Codes up to Capacity in Near-Linear Time. | Shashank Srivastava, Madhur Tulsiani |
| 2025 | STOC | Explicit Codes Approaching Generalized Singleton Bound using Expanders. | Fernando Granha Jeronimo, Tushant Mittal, Shashank Srivastava, Madhur Tulsiani |
| 2024 | FOCS | Efficient Certificates of Anti-Concentration Beyond Gaussians. | Ainesh Bakshi, Pravesh K. Kothari, Goutham Rajendran, Madhur Tulsiani, Aravindan Vijayaraghavan |
| 2023 | FOCS | List Decoding of Tanner and Expander Amplified Codes from Distance Certificates. | Fernando Granha Jeronimo, Shashank Srivastava, Madhur Tulsiani |
| 2023 | SODA | Concentration of polynomial random matrices via Efron-Stein inequalities. | Goutham Rajendran, Madhur Tulsiani |
| 2021 | FOCS | Sum-of-Squares Lower Bounds for Sparse Independent Set. | Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, Jeff Xu |
| 2021 | STOC | Near-linear time decoding of Ta-Shma's codes via splittable regularity. | Fernando Granha Jeronimo, Shashank Srivastava, Madhur Tulsiani |
| 2020 | FOCS | Unique Decoding of Explicit $\varepsilon$-balanced Codes Near the Gilbert-Varshamov Bound. | Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, Madhur Tulsiani |
| 2020 | SODA | List Decoding of Direct Sum Codes. | Vedat Levi Alev, Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, Madhur Tulsiani |
| 2019 | FOCS | Approximating Constraint Satisfaction Problems on High-Dimensional Expanders. | Vedat Levi Alev, Fernando Granha Jeronimo, Madhur Tulsiani |
| 2019 | SODA | Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness. | Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani |
| 2018 | SODA | Approximate Local Decoding of Cubic Reed-Muller Codes Beyond the List Decoding Radius. | Pooya Hatami, Madhur Tulsiani |
| 2017 | FOCS | Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere. | Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani |
| 2015 | SODA | Algorithmic regularity for polynomials and applications. | Arnab Bhattacharyya, Pooya Hatami, Madhur Tulsiani |
| 2014 | ICALP | Sampling-Based Proofs of Almost-Periodicity Results and Algorithmic Applications. | Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf |
| 2014 | ICALP | The Complexity of Somewhat Approximation Resistant Predicates. | Subhash Khot, Madhur Tulsiani, Pratik Worah |
| 2014 | ICALP | Optimal Strong Parallel Repetition for Projection Games on Low Threshold Rank Graphs. | Madhur Tulsiani, John Wright, Yuan Zhou |
| 2014 | IPCO | Linear Programming Hierarchies Suffice for Directed Steiner Tree. | Zachary Friggstad, Jochen Knemann, Young Kun-Ko, Anand Louis, Mohammad Shadravan, Madhur Tulsiani |
| 2014 | STOC | A characterization of strong approximation resistance. | Subhash Khot, Madhur Tulsiani, Pratik Worah |
| 2011 | FOCS | Quadratic Goldreich-Levin Theorems. | Madhur Tulsiani, Julia Wolf |
| 2011 | SODA | Algorithms and Hardness for Subspace Approximation. | Amit Deshpande, Madhur Tulsiani, Nisheeth K. Vishnoi |
| 2011 | SODA | On LP-Based Approximability for Strict CSPs. | Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth K. Vishnoi |
| 2010 | CRYPTO | Time Space Tradeoffs for Attacks against One-Way Functions and PRGs. | Anindya De, Luca Trevisan, Madhur Tulsiani |
| 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 |
| 2009 | STOC | CSP gaps and reductions in the lasserre hierarchy. | Madhur Tulsiani |
| 2008 | FOCS | Dense Subsets of Pseudorandom Sets. | Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan |
| 2008 | STOC | Unique games on expanding constraint graphs are easy: extended abstract. | Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, Nisheeth K. Vishnoi |
| 2007 | STOC | Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut. | Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani |