Madhur Tulsiani
Third year Ph.D. student in Computer Science
University of California, Berkeley
<concatenation of mad and hurt> at cs dot berkeley dot edu

I am interested in Complexity Theory (here's why) and am working with Luca Trevisan.
Before coming to Berkeley, I did my bachelor's in Computer Science at IIT Kanpur.

CV:  [pdf] [ps]

Papers

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

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

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

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

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

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 - written for Luca's complexity class.

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