Madhur Tulsiani

Assistant Professor,
Toyota Technological Institute at Chicago

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

<concatenation of mad and hurt> at ttic dot edu

Madhur Tulsiani

Assistant Professor,
Toyota Technological Institute at Chicago

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

<concatenation of mad and hurt> at ttic dot edu

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

Editorial:
[Theory of Computing]
[Algorithmica]

PCs:
[STOC 2012]
[APPROX 2013]
[FSTTCS 2013]
[CCC 2014]

[RANDOM 2015]

Links:
[Theory@UChicago]
[Theory
Seminar]
[Theory Reading Group]

Teaching

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

Students

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

Papers

From Weak to Strong LP Gaps for all CSPs

(with Mrinalkanti Ghosh)

Manuscript.
[ECCC TR16-117]
[arXiv]

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(PDF)]

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 Approximation Resistance~~

~~(with Subhash Khot and Pratik Worah)~~

*This version of the paper had a bug in the trick for going from Strong
Approximation Resistance to Approximation Resistance.
The previous result for
Strong Approximation Resistance still holds.*

A Characterization of Strong Approximation Resistance

(with Subhash Khot and Pratik Worah)

STOC 2014.
[arXiv]
[ECCC TR13-075]
[Slides(PDF)]

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(PDF)]

Reductions between Expansion Problems

(with Prasad Raghavendra and David Steurer)

CCC 2012.
[Proceedings]
[arXiv]
[ECCC TR10-172]
[PDF]
[Slides(PDF)]

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]

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(PDF)]

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(PDF)]

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(PDF)]

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(PDF)]

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