Papers

Convex Relaxations and Hardness of Approximation

Towards an Optimal Query Efficient PCP?

(with Subhash Khot and Muli Safra)

Manuscript.

LS+ Lower Bounds from Pairwise Independence

(with Pratik Worah)

Manuscript.

Graph Densification

(with Moritz Hardt and Nikhil Srivastava)

ITCS’12.

Cuts in Cartesian Products of Graphs

(with Sushant Sachdeva)

Manuscript.    [arXiv]    [PDF]

Reductions between Expansion Problems

(with Prasad Raghavendra and David Steurer)

CCC’12 (to appear).    [arXiv]    [ECCC TR10-172]    [PDF]    [Slides(PDF)]

Algorithms and Hardness for Subspace Approximation

(with Amit Deshpande and Nisheeth Vishnoi)

SODA’11.    [arXiv]    [PDF]

On LP-based Approximability for Strict CSPs

(with Amit Kumar, Rajsekar Manokaran and Nisheeth Vishnoi)

SODA’11.    [arXiv]    [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’10.     [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’09.    [Proceedings]    [ECCC TR09-061]    [PDF]

CSP Gaps and Reductions in the Lasserre Hierarchy

STOC’09.    [Proceedings]    [ECCC TR08-104]    [PDF]    [Slides(PDF)]

Unique Games on Expanding Constraint Graphs are Easy

(with Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer and Nisheeth Vishnoi)

STOC’08.    [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’07.    [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’07.    [Proceedings]    [ECCC TR06-98]    [PDF]    [Slides(PPT)]

Pseudorandomness, Cryptography and Complexity

Quadratic Goldreich-Levin Theorems

(with Julia Wolf)

FOCS’11.    [ECCC TR11-084]   [arXiv]   [PDF]

Improved Pseudorandom Generators for Depth 2 Circuits

(with Anindya De, Omid Etesami and Luca Trevisan)

RANDOM’10.    [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’10.    [Proceedings]   [ECCC TR09-113]    [PDF]    [Slides(PDF)]

Boosting, Regularity and Efficiently Simulating Every High-Entropy Distribution

(with Luca Trevisan and Salil Vadhan)

CCC’09.    [Proceedings]    [ECCC TR08-103]    [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’08.    [Proceedings]    [ECCC TR08-045]    [PDF]    [Slides(PDF)]

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

Links:    Theory@UChicago | Theory@Berkeley | Blog | Pics