Madhur Tulsiani

Associate Professor, Toyota Technological Institute at Chicago

Associate Professor (part time), Department of Computer Science, University of Chicago

<concatenation of mad and hurt> at ttic dot edu

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.

I am interested in Theoretical Computer Science, particularly in Complexity Theory. My research is funded by NSF Career Award 1254044 and NSF Award 1816372.

Editorial: [Theory of Computing]     [Algorithmica]
PCs: [STOC 2012]     [APPROX 2013]     [FSTTCS 2013]     [CCC 2014]
            [RANDOM 2015]     [CCC 2018]     [ITCS 2019]
Links: [Theory@UChicago]     [Theory Seminar]     [Midwest Theory Day 2018]


Spring 2013: Mathematical Toolkit

Summer 2013: Linear Algebra and Combinatorics (REU - Apprentice Program)

Summer 2014: Semidefinite Programming and Constraint Satisfaction (REU)

Autumn 2014: Information and Coding Theory

Autumn 2015: Mathematical Toolkit

Autumn 2016: Mathematical Toolkit

Autumn 2017: Information and Coding Theory

Autumn 2018: Mathematical Toolkit


Pratik Worah (University of Chicago, co-advised with Janos Simon) PhD 2013
Pooya Hatami (University of Chicago, co-advised with Sasha Razborov) PhD 2015
Mrinalkanti Ghosh (TTI-Chicago)
Fernando Granha Jeronimo (University of Chicago, co-advised with Andrew Drucker)
Goutham Rajendran (University of Chicago, co-advised with Janos Simon)
Shashank Srivastava (TTI-Chicago)


Approximating Operator Norms via Generalized Krivine Rounding
(with Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami and Euiwoong Lee)
SODA 2019 (merged with the paper below).     [arXiv]    

Inapproximability of Matrix p → q Norms
(with Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami and Euiwoong Lee)
SODA 2019 (merged with the paper above).     [ECCC TR18-037]     [arXiv]     [Slides]    

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]    
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