Alexandra Kolla I am a fourth-year Graduate Student in Computer Science, U. C. Berkeley. My advisor is Umesh Vazirani. I am an Intern in Microsoft NE for the summer. Research interests: Complexity theory, algorithms, combinatorial optimization. I am particularly interested in semidefinite programming hierarchies. I am also interested in spectral graph theory and quanutm cryptography.

Papers

1. On parallel composition of zero-knowledge proofs with black-box quantum simulators
   with Rahul Jain, Gatis Midrijanis, and Ben Reichardt.
   Submitted to QIC.
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.
   Manuscript 2008.