Madhur Tulsiani
Professor,
Toyota Technological Institute at Chicago
Professor,
Department of Computer Science,
University of Chicago
(part-time appointment)
<concatenation of mad and hurt> at ttic dot edu
I am interested in Theoretical Computer Science, particularly in Complexity
Theory. My research has been supported by NSF Career Award 1254044,
NSF Award 1816372
and NSF Award 2326685.
Brief bio: I did my bachelor’s in Computer Science at IIT Kanpur
(2001-05) and a Ph.D. at UC Berkeley (2005-09) advised by Luca Trevisan.
I also spent two years as a postdoc at the Institute for Advanced Study
and Princeton University.
Here’s a CV
if you want to know more.
Editorial:
[Theory of Computing]
PCs:
[STOC 2012]
[APPROX 2013]
[FSTTCS 2013]
[CCC 2014]
[RANDOM 2015]
[CCC 2018]
[ITCS 2019]
[ITCS 2020]
[STOC 2020]
[STOC 2023]
[RANDOM 2023]
[STOC 2024]
[SODA 2025]
Links:
[Theory@TTIC]
[Theory@UChicago]
[New Horizons in TCS]
Teaching
Information and Coding Theory
[2022]
[2021
(with videos)]
[2017]
[2014]
Mathematical Toolkit
[2023]
[2021 (with videos)]
[2019]
[2018]
[2016]
[2015]
[2013]
Students
Papers
Ellipsoid fitting up to constant via empirical covariance estimation
(with June Wu)
Manuscript.
[arXiv]
List Decoding of Tanner and Expander Amplified Codes from Distance Certificates
(with Fernando Granha Jeronimo and Shashank Srivastava)
FOCS 2023.
[arXiv]
[Talk]
Concentration of polynomial random matrices via Efron-Stein inequalities
(with Goutham Rajendran)
SODA 2023.
[arXiv]
[Talk]
Explicit Abelian Lifts and Quantum LDPC Codes
(with Fernando Granha Jeronimo, Tushant Mittal, Pedro Paredes, and Ryan O'Donnell)
ITCS 2022.
[arXiv]
Separating the NP-Hardness of the Grothendieck problem from the Little-Grothendieck problem
(with Vijay Bhattiprolu and Euiwoong Lee)
ITCS 2022. [Draft]
Sum-of-Squares Lower Bounds for Sparse Independent Set
(with Chris Jones, Aaron Potechin, Goutham Rajendran, and Jeff Xu)
FOCS 2021.
[arXiv]
Near-linear Time Decoding of Ta-Shma’s Codes via Splittable Regularity
(with Fernando Granha Jeronimo and Shashank Srivastava)
STOC 2021. [Draft]
[Talk]
Explicit SoS lower bounds from high-dimensional expanders
(with Irit Dinur, Yuval Filmus and Prahladh Harsha)
ITCS 2021.
[ECCC TR20-136]
[arXiv]
[Talk]
Unique Decoding of Explicit ϵ-balanced Codes Near the Gilbert-Varshamov Bound
(with Fernando Granha Jeronimo, Dylan Quintana and Shashank Srivastava)
FOCS 2020.
[arXiv]
[Talk]
Invited to special issue on FOCS 2020.
List Decoding of Direct Sum Codes
(with Vedat Levi Alev, Fernando Granha Jeronimo, Dylan Quintana and Shashank Srivastava)
SODA 2020.
[arXiv]
[Talk]
Approximating Constraint Satisfaction Problems on High-Dimensional Expanders
(with Vedat Levi Alev and Fernando Granha Jeronimo)
FOCS 2019.
[arXiv]
Approximating Operator Norms via Generalized Krivine Rounding
(with Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami and Euiwoong Lee)
SODA 2019 (merged with paper below).
[arXiv]
Inapproximability of Matrix p → q Norms
(with Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami and Euiwoong Lee)
SODA 2019 (merged with paper above).
[ECCC TR18-037]
[arXiv]
[Slides]
[Talk]
Approximate Local Decoding of Cubic Reed-Muller Codes Beyond the List Decoding Radius
(with Pooya Hatami)
SODA 2018.
[PDF]
Finding Pseudorandom Colorings of Pseudorandom Graphs
(with Akash Kumar and Anand Louis)
FSTTCS 2017.
Weak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere
(with Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami and Euiwoong Lee)
FOCS 2017.
[ECCC TR16-185]
[arXiv]
From Weak to Strong LP Gaps for all CSPs
(with Mrinalkanti Ghosh)
CCC 2017.
[ECCC TR16-117]
[arXiv]
[Journal Version]
[Slides]
[Talk]
Invited to special issue on CCC 2017.
Proving Weak Approximability without Algorithms
(with Ridwan Syed)
APPROX 2016.
An Arithmetic Analogue of Fox's Triangle Removal Argument
(with Pooya Hatami and Sushant Sachdeva)
Online Journal of Analytic Combinatorics.
[Journal Version]
[arXiv]
Algorithmic Regularity for Polynomials and Applications
(with Arnab Bhattacharyya and Pooya Hatami)
SODA 2015.
[arXiv]
[PDF]
Optimal strong parallel repetition for projection games on low threshold rank graphs
(with John Wright and Yuan Zhou)
ICALP 2014.
The Complexity of Somewhat Approximation Resistant Predicates
(with Subhash Khot and Pratik Worah)
ICALP 2014.
[ECCC TR12-151]
[Slides]
Sampling-based proofs of almost-periodicity results and algorithmic applications
(with Eli Ben-Sasson, Noga Ron-Zewi and Julia Wolf)
ICALP 2014.
[arXiv]
[ECCC TR12-135]
A Characterization of Strong Approximation Resistance
(with Subhash Khot and Pratik Worah)
STOC 2014.
[arXiv]
[ECCC TR13-075]
[Slides]
Linear Programming Hierarchies Suffice for Directed Steiner Tree
(with Zachary Friggstad, Young Kun Ko, Jochen Könemann, Anand Louis and Mohammad Shadravan)
IPCO 2014.
LS+ Lower Bounds from Pairwise Independence
(with Pratik Worah)
CCC 2013.
[ECCC TR12-105]
Towards An Optimal Query Efficient PCP?
(with Subhash Khot and Muli Safra)
ITCS 2013.
[ECCC TR12-109]
[Slides]
Reductions between Expansion Problems
(with Prasad Raghavendra and David Steurer)
CCC 2012.
[Proceedings]
[arXiv]
[ECCC TR10-172]
[PDF]
[Slides]
Graph Densification
(with Motiz Hardt and Nikhil Srivastava)
ITCS 2012.
[Proceedings]
Quadratic Goldreich-Levin Theorems
(with Julia Wolf)
FOCS 2011.
[Proceedings]
[arXiv]
[ECCC TR11-084]
[PDF]
Invited to special issue on FOCS 2011.
Cuts in Cartesian Products of Graphs
(with Sushant Sachdeva)
Manuscript.
[arXiv]
[PDF]
Algorithms and Hardness for Subspace Approximation
(with Amit Deshpande and Nisheeth Vishnoi)
SODA 2011.
[arXiv]
[PDF]
On LP-based Approximability for Strict CSPs
(with Amit Kumar, Rajsekar Manokaran and Nisheeth Vishnoi)
SODA 2011.
[arXiv]
[PDF]
Improved Pseudorandom Generators for Depth 2 Circuits
(with Anindya De, Omid Etesami and Luca Trevisan)
RANDOM 2010.
[Proceedings]
[ECCC TR09-141]
[PDF]
[Slides]
Time-Space Tradeoffs for Attacks against One-Way Functions and PRGs
(with Anindya De and Luca Trevisan)
CRYPTO 2010.
[Proceedings]
[ECCC TR09-113]
[PDF]
[Slides]
SDP Gaps for 2-to-1 and other Label Cover Variants
(with Venkatesan Guruswami, Subhash Khot, Preyas Popat, Ryan O’Donnell and Yi Wu)
ICALP 2010.
[Proceedings]
[PDF]
SDP Gaps from Pairwise Independence
Updated version of the APPROX paper which only showed LP gaps.
(with Siavosh Benabbas, Costis Georgiou and Avner Magen)
APPROX 2009.
[Proceedings]
[ECCC TR09-061]
[PDF]
Boosting, Regularity and Efficiently Simulating Every High-Entropy Distribution
(with Luca Trevisan and Salil Vadhan)
CCC 2009.
[Proceedings]
[ECCC TR08-103]
[PDF]
CSP Gaps and Reductions in the Lasserre Hierarchy
STOC 2009.
[Proceedings]
[ECCC TR08-104]
[PDF]
New Proofs of the Green-Tao-Ziegler Dense Model Theorem: An Exposition
(with Omer Reingold, Luca Trevisan and Salil Vadhan)
Note.
[arXiv]
[PDF]
Dense Subsets of Pseudorandom Sets
(with Omer Reingold, Luca Trevisan and Salil Vadhan)
FOCS 2008.
[Proceedings]
[ECCC TR08-045]
[PDF]
[Slides]
Unique Games on Expanding Constraint Graphs are Easy
(with Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer and Nisheeth Vishnoi)
STOC 2008.
[Proceedings]
[PDF]
Playing Random and Expanding Unique Games
(with Alexandra Kolla)
Manuscript.
[PDF]
Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut
(with Grant Schoenebeck and Luca Trevisan)
STOC 2007.
[Proceedings]
[ECCC TR06-132]
[PDF]
[Slides(PPT)]
A Linear Round Lower Bound for Lovasz Schrijver SDP Relaxations of Vertex Cover
(with Grant Schoenebeck and Luca Trevisan)
CCC 2007.
[Proceedings]
[ECCC TR06-098]
[PDF]
[Slides(PPT)]
Surveys and Book Chapters
Survey talk on LP and SDP Hierarchies
[Slides]
Given at a Center for Intractability meeting
Lovasz-Schrijver Reformulation
[PDF]
Draft of article written for Wiley Encyclopedia of Operations Research & Management Science
Convex Relaxations and Integrality Gaps
[PDF]
(with Eden Chlamtac)
Article written for the Handbook on Semidefinite, Cone and Polynomial Optimization