Alexandra Kolla I am a postdoc 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 CV               Research Statement

Papers

1. Spectral Algorithms for Unique Games.
   To Appear, CCC 2010.

2. Subgraph Sparsification and Nearly Optimal Ultrasparsifiers.
   With Yury Makarychev, Amin Saberi, Shang-hua Teng.
   To Appear, STOC 2010.

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

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

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

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

7. Playing Unique Games Using Graph Spectra.
   With Madhur Tulsiani.
   Manuscript, 2007.

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

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

P.h.D Thesis

Merging Techniques for Combinatorial Optimization: Spectral Graph Theory and Semidefinite Programming.