A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover. - Grant Schoenebeck; Luca Trevisan 001; Madhur Tulsiani (Electron. Colloquium Comput. Complex., 2006)

Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut. - Grant Schoenebeck; Luca Trevisan 001; Madhur Tulsiani (Electron. Colloquium Comput. Complex., 2006)

Unique games on expanding constraint graphs are easy: extended abstract. - Sanjeev Arora; Subhash Khot; Alexandra Kolla; David Steurer; Madhur Tulsiani; Nisheeth K. Vishnoi (STOC, 2008)

Dense Subsets of Pseudorandom Sets. - Omer Reingold; Luca Trevisan 001; Madhur Tulsiani; Salil P. Vadhan (Electron. Colloquium Comput. Complex., 2008)

Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. - Luca Trevisan 001; Madhur Tulsiani; Salil P. Vadhan (Electron. Colloquium Comput. Complex., 2008)

CSP Gaps and Reductions in the Lasserre Hierarchy. - Madhur Tulsiani (Electron. Colloquium Comput. Complex., 2008)

Algorithms and Hardness for Subspace Approximation - Amit Deshpande 001; Kasturi R. Varadarajan; Madhur Tulsiani; Nisheeth K. Vishnoi (CoRR, 2009)

Improved Pseudorandom Generators for Depth 2 Circuits. - Anindya De; Omid Etesami; Luca Trevisan 001; Madhur Tulsiani (Electron. Colloquium Comput. Complex., 2009)

Non-uniform attacks against one-way functions and PRGs. - Anindya De; Luca Trevisan 001; Madhur Tulsiani (Electron. Colloquium Comput. Complex., 2009)

Optimal Sherali-Adams Gaps from Pairwise Independence. - Konstantinos Georgiou; Avner Magen; Madhur Tulsiani (Electron. Colloquium Comput. Complex., 2009)

On the Optimality of a Class of LP-based Algorithms. - Amit Kumar 001; Rajsekar Manokaran; Madhur Tulsiani; Nisheeth K. Vishnoi (Electron. Colloquium Comput. Complex., 2009)

Local Constraints in Combinatorial Optimization. - Madhur Tulsiani (2009)

Time Space Tradeoffs for Attacks against One-Way Functions and PRGs. - Anindya De; Luca Trevisan 001; Madhur Tulsiani (CRYPTO, 2010)

SDP Gaps for 2-to-1 and Other Label-Cover Variants. - Venkatesan Guruswami; Subhash Khot; Ryan O'Donnell; Preyas Popat; Madhur Tulsiani; Yi Wu 002 (ICALP (1), 2010)

Reductions Between Expansion Problems. - Prasad Raghavendra; David Steurer; Madhur Tulsiani (Electron. Colloquium Comput. Complex., 2010)

Algorithms and Hardness for Subspace Approximation. - Amit Deshpande 001; Madhur Tulsiani; Nisheeth K. Vishnoi (SODA, 2011)

On LP-Based Approximability for Strict CSPs. - Amit Kumar 001; Rajsekar Manokaran; Madhur Tulsiani; Nisheeth K. Vishnoi (SODA, 2011)

Cuts in Cartesian Products of Graphs - Sushant Sachdeva; Madhur Tulsiani (CoRR, 2011)

Graph densification. - Moritz Hardt; Nikhil Srivastava; Madhur Tulsiani (ITCS, 2012)

Sampling-based proofs of almost-periodicity results and algorithmic applications. - Eli Ben-Sasson; Noga Ron-Zewi; Madhur Tulsiani; Julia Wolf (Electron. Colloquium Comput. Complex., 2012)

Towards An Optimal Query Efficient PCP? - Subhash Khot; Muli Safra; Madhur Tulsiani (Electron. Colloquium Comput. Complex., 2012)

The Complexity of Somewhat Approximation Resistant Predicates. - Subhash Khot; Madhur Tulsiani; Pratik Worah (Electron. Colloquium Comput. Complex., 2012)

$LS_+$ Lower Bounds from Pairwise Independence. - Madhur Tulsiani; Pratik Worah (Electron. Colloquium Comput. Complex., 2012)

SDP Gaps from Pairwise Independence. - Siavosh Benabbas; Konstantinos Georgiou; Avner Magen; Madhur Tulsiani (Theory Comput., 2012)

LS+ Lower Bounds from Pairwise Independence. - Madhur Tulsiani; Pratik Worah (CCC, 2013)

An Arithmetic Analogue of Fox's Triangle Removal Argument - Pooya Hatami; Sushant Sachdeva; Madhur Tulsiani (CoRR, 2013)

A Characterization of Strong Approximation Resistance. - Subhash Khot; Madhur Tulsiani; Pratik Worah (Electron. Colloquium Comput. Complex., 2013)

A Characterization of Approximation Resistance. - Subhash Khot; Madhur Tulsiani; Pratik Worah (Electron. Colloquium Comput. Complex., 2013)

Optimal Strong Parallel Repetition for Projection Games on Low Threshold Rank Graphs. - Madhur Tulsiani; John Wright 004; Yuan Zhou 007 (ICALP (1), 2014)

Linear Programming Hierarchies Suffice for Directed Steiner Tree. - Zachary Friggstad; Jochen Könemann; Young Kun-Ko; Anand Louis; Mohammad Shadravan; Madhur Tulsiani (IPCO, 2014)

Quadratic Goldreich-Levin Theorems. - Madhur Tulsiani; Julia Wolf (SIAM J. Comput., 2014)

Algorithmic regularity for polynomials and applications. - Arnab Bhattacharyya 001; Pooya Hatami; Madhur Tulsiani (SODA, 2015)

Proving Weak Approximability Without Algorithms. - Ridwan Syed; Madhur Tulsiani (APPROX-RANDOM, 2016)

Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere. - Vijay V. S. P. Bhattiprolu; Mrinalkanti Ghosh; Venkatesan Guruswami; Euiwoong Lee; Madhur Tulsiani (Electron. Colloquium Comput. Complex., 2016)

From Weak to Strong LP Gaps for all CSPs. - Mrinalkanti Ghosh; Madhur Tulsiani (Electron. Colloquium Comput. Complex., 2016)

Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere. - Vijay Bhattiprolu; Mrinalkanti Ghosh; Venkatesan Guruswami; Euiwoong Lee; Madhur Tulsiani (FOCS, 2017)

Finding Pseudorandom Colorings of Pseudorandom Graphs. - Akash Kumar 003; Anand Louis; Madhur Tulsiani (FSTTCS, 2017)

Approximate Local Decoding of Cubic Reed-Muller Codes Beyond the List Decoding Radius. - Pooya Hatami; Madhur Tulsiani (SODA, 2018)

Inapproximability of Matrix p→q Norms. - Vijay Bhattiprolu; Mrinalkanti Ghosh; Venkatesan Guruswami; Euiwoong Lee; Madhur Tulsiani (Electron. Colloquium Comput. Complex., 2018)

Approximating Operator Norms via Generalized Krivine Rounding. - Vijay Bhattiprolu; Mrinalkanti Ghosh; Venkatesan Guruswami; Euiwoong Lee; Madhur Tulsiani (Electron. Colloquium Comput. Complex., 2018)

From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems. - Mrinalkanti Ghosh; Madhur Tulsiani (Theory Comput., 2018)

Approximating Constraint Satisfaction Problems on High-Dimensional Expanders. - Vedat Levi Alev; Fernando Granha Jeronimo; Madhur Tulsiani (FOCS, 2019)

Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness. - Vijay Bhattiprolu; Mrinalkanti Ghosh; Venkatesan Guruswami; Euiwoong Lee; Madhur Tulsiani (SODA, 2019)

Unique Decoding of Explicit $ varepsilon$-balanced Codes Near the Gilbert-Varshamov Bound. - Fernando Granha Jeronimo; Dylan Quintana; Shashank Srivastava; Madhur Tulsiani (FOCS, 2020)

List Decoding of Direct Sum Codes. - Vedat Levi Alev; Fernando Granha Jeronimo; Dylan Quintana; Shashank Srivastava; Madhur Tulsiani (SODA, 2020)

Unique Decoding of Explicit ε-balanced Codes Near the Gilbert-Varshamov Bound. - Fernando Granha Jeronimo; Dylan Quintana; Shashank Srivastava; Madhur Tulsiani (CoRR, 2020)

Explicit and structured sum of squares lower bounds from high dimensional expanders. - Irit Dinur; Yuval Filmus; Prahladh Harsha; Madhur Tulsiani (Electron. Colloquium Comput. Complex., 2020)

Sum-of-Squares Lower Bounds for Sparse Independent Set. - Chris Jones; Aaron Potechin; Goutham Rajendran; Madhur Tulsiani; Jeff Xu (FOCS, 2021)

Explicit SoS Lower Bounds from High-Dimensional Expanders. - Irit Dinur; Yuval Filmus; Prahladh Harsha; Madhur Tulsiani (ITCS, 2021)

Near-linear time decoding of Ta-Shma's codes via splittable regularity. - Fernando Granha Jeronimo; Shashank Srivastava; Madhur Tulsiani (STOC, 2021)

Separating the NP-Hardness of the Grothendieck Problem from the Little-Grothendieck Problem. - Vijay Bhattiprolu; Euiwoong Lee; Madhur Tulsiani (ITCS, 2022)

Explicit Abelian Lifts and Quantum LDPC Codes. - Fernando Granha Jeronimo; Tushant Mittal; Ryan O'Donnell; Pedro Paredes 002; Madhur Tulsiani (ITCS, 2022)

List Decoding of Tanner and Expander Amplified Codes from Distance Certificates. - Fernando Granha Jeronimo; Shashank Srivastava; Madhur Tulsiani (FOCS, 2023)

Concentration of polynomial random matrices via Efron-Stein inequalities. - Goutham Rajendran; Madhur Tulsiani (SODA, 2023)

Inapproximability of Matrix p → q Norms. - Vijay Bhattiprolu; Mrinal Kanti Ghosh; Venkatesan Guruswami; Euiwoong Lee; Madhur Tulsiani (SIAM J. Comput., 2023)

Efficient Certificates of Anti-Concentration Beyond Gaussians. - Ainesh Bakshi; Pravesh K. Kothari; Goutham Rajendran; Madhur Tulsiani; Aravindan Vijayaraghavan (FOCS, 2024)

List Decodable Quantum LDPC Codes. - Thiago Bergamaschi; Fernando Granha Jeronimo; Tushant Mittal; Shashank Srivastava; Madhur Tulsiani (CoRR, 2024)

Simple Norm Bounds for Polynomial Random Matrices via Decoupling. - Madhur Tulsiani; June Wu (ITCS, 2025)

Ellipsoid fitting up to constant via empirical covariance estimation. - Madhur Tulsiani; June Wu (SOSA, 2025)

Explicit Codes Approaching Generalized Singleton Bound using Expanders. - Fernando Granha Jeronimo; Tushant Mittal; Shashank Srivastava; Madhur Tulsiani (STOC, 2025)

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time. - Shashank Srivastava; Madhur Tulsiani (CoRR, 2025)