Alexandra Kolla I am a fifth-year Graduate Student in Computer Science, U. C. Berkeley. My advisor is 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.

Papers

1. On parallel composition of zero-knowledge proofs with black-box quantum simulators
   with Rahul Jain, Gatis Midrijanis, and Ben Reichardt.
   To appear, QIC Journal.
2. 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.
3. Unique Games on Expanding Constraint Graphs are Easy.
   With Sanjeev Arora, Subhash Khot, David Steurer, Madhur Tulsiani and Nisheeth Vishnoi.
   STOC 2008.
4. Playing Unique Games Using Graph Spectra.
   With Madhur Tulsiani.
   Under Submission, 2008.
5. Approximation Algorithms for Spectral Optimization.
   With Yury Makarychev, Amin Saberi, Shang-hua Teng.
   Under Submission, Patent Filed 2008.
6. Sparsest Cut on quotients of the hypercube.
   With James Lee.
   Submitted, CCC 2009.
7. Integrality Gaps for Lasserre Relaxations via Semidefinite Programming Duality.
   With Satyen Kale and Madhur Tulsiani.
   Submitted, CCC 2009.