Alexandra Kolla I am a DIMACS post-doctoral fellow, at the Institute for Advanced Study. I got my PhD at U.C berkeley. My advisor was Umesh Vazirani. Research interests: Complexity theory, algorithms, combinatorial optimization. I am particularly interested in semidefinite programming and spectral graph theory. I am also interested in quanutm cryptography. Contact Information: akolla [at] math [dot] ias [dot] edu

Papers

1. Subgraph Sparsification and Nearly Optimal Ultrasparsifiers.
   With Yury Makarychev, Amin Saberi, Shang-hua Teng.
   Submitted 2009.

2. Fast Online Graph Sparsification for Approximating Vertex Expansion .
   With Nikhil R. Devanur.
   Submitted 2009.

3. Sparsest Cut on quotients of the hypercube.
   With James Lee.
   Manuscript, 2009.

4. Integrality Gaps for Lasserre Relaxations via Semidefinite Programming Duality.
   With Satyen Kale and Madhur Tulsiani.
   Manuscript, 2009.

5. Unique Games on Expanding Constraint Graphs are Easy.
   With Sanjeev Arora, Subhash Khot, David Steurer, Madhur Tulsiani and Nisheeth Vishnoi.
   STOC 2008.

6. Playing Unique Games Using Graph Spectra.
   With Madhur Tulsiani.
   Under Submission, 2008.

7. Making classical honest verifier protocols secure against quantum attacks.
   with Sean Hallgren, Pranab Sen and Shengyu Zhang.
   ICALP 2008, BEST PAPER AWARD FOR TRACK C.

8. On parallel composition of zero-knowledge proofs with black-box quantum simulators
   with Rahul Jain, Gatis Midrijanis, and Ben Reichardt.
   Accepted for publication. QIC Journal, 2007.