Madhur Tulsiani
School of Mathematics
Institute for Advanced Study, Princeton
<concatenation of mad and hurt> at math dot ias dot edu

I am interested in Complexity Theory (here's why).
I am now a postdoc at the IAS. Before this, I did my bachelor's in Computer Science
at IIT Kanpur and a Ph.D. at Berkeley advised by Luca Trevisan.
CV:  [pdf] [ps]

Papers

    LP/SDP Relaxations
  1. Amit Deshpande, Madhur Tulsiani, Kasturi Varadarjan and Nisheeth Vishnoi
    Algorithms and Hardness for Subspace Approximation
    [pdf], Manuscript

  2. Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani and Nisheeth Vishnoi
    On the Optimality of a Class of LP-based Algorithms
    [pdf], Manuscript

  3. Konstantinos Georgiou, Avner Magen and Madhur Tulsiani
    Optimal Sherali-Adams Gaps from Pairwise Independence
    [pdf], APPROX 2009

  4. Madhur Tulsiani
    CSP Gaps and Reductions in the Lasserre Hierarchy
    [ECCC TR08-104], STOC 2009 [Conference Proceedings]

  5. Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani and Nisheeth Vishnoi
    Unique Games on Expanding Constraint Graphs are Easy
    [pdf], STOC 2008 [Conference Proceedings]

  6. Grant Schoenebeck, Luca Trevisan and Madhur Tulsiani
    Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut
    [ECCC TR06-132], STOC 2007 [Conference Proceedings]

  7. Grant Schoenebeck, Luca Trevisan and Madhur Tulsiani
    A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover
    [ECCC TR06-98], CCC 2007 [Conference Proceedings]


    Additive Combinatorics, Cryptography and Complexity
  1. Anindya De, Luca Trevisan and Madhur Tulsiani
    Non-uniform Attacks against One-Way Functions and PRGs
    [ECCC TR09-113], Manuscript

  2. Luca Trevisan, Madhur Tulsiani and Salil Vadhan
    Boosting, Regularity and Efficiently Simulating Every High-Entropy Distribution
    [ECCC TR08-103], CCC 2009

  3. Omer Reingold, Luca Trevisan, Madhur Tulsiani and Salil Vadhan
    New Proofs of the Green-Tao-Ziegler Dense Model Theorem: An Exposition
    [arXiv]

  4. Omer Reingold, Luca Trevisan, Madhur Tulsiani and Salil Vadhan
    Dense Subsets of Pseudorandom Sets
    [ECCC TR08-045], FOCS 2008 [Conference Proceedings]


Notes (Based on reading: results are by others, any errors are by me)

  1. Two applications of the Pattern Matrix Method [pdf] 
    A summary of results by Sherstov and Razborov on Quantum Communication Complexity and hardness of AC^0 functions.

Links:    TGIF | Complexity Reading Group | Theory@Berkeley | Blog | Photos

Friends:    Aman | Sushobhan | Pulkit | Grant | Tom | Abhishek