Madhur Tulsiani Fourth 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.

1. Konstantinos Georgiou, Avner Magen and Madhur Tulsiani
   Optimal Sherali-Adams Gaps from Pairwise Independence
   Submitted

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

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

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

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

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

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

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