Alexandra Kolla I am an Assistant Professor at the Computer Science Department at UIUC. I got my PhD at U.C. Berkeley. My advisor was Umesh Vazirani. After that, I did a postdoc at the Institute for Advanced Study and at Microsoft Research in Redmond. Research interests: Spectral Graph Theory, Algorithms, Complexity, Convex Programming, Quantum Computing. I am particularly interested in the use of spectral methods in graph algorithms and more so in developing new spectral techniques that use the full power of graph spectra (for example, see this paper). I believe that such techniques will help shed light into various unanswered complexity questions, like the Unique Games Conjecture. Contact Information: akolla [at] illinois [dot] edu #3222 Siebel Center 201 N. Goodwin ave. Urbana, IL 61801

Teaching

Spring 2017, Computational Complexity(CS 579).

Fall 2016, Algorithms and Models of Computation(CS 374).

Spring 2016, Computational Complexity (CS 579).

Fall 2015, Randomized Algorithms (CS 574).

Spring 2015, Spectral Graph Theory (CS 598).

Fall 2014, Undergraduate Algorithms (CS 473).

Spring 2013, Undergraduate Algorithms (CS 473).

Fall 2012, Computational Complexity (CS 579).

Spring 2012, Spectral Graph Theory (CS 598).

Papers

1. Spectral Graph Isomorphism. With Vivek Madan, Ali Sinop.
   Submitted, 2017

2. Invertibility and Largest Eigenvalue of Symmetric Matrix Signings. With Charles Carlson, Karthekeyan Chandrasekaran and Hsien-Chih Chang.
   Submitted, 2017

3. On the Expansion of Group-Based Lifts. With Naman Agarwal, Karthekeyan Chandrasekaran and Vivek Madan.
   To appear at RANDOM, 2017.

4. Measuring and Understanding Throughput of Network Topologies. With Sangeetha Abdu Jyothi, Ankit Singla and P. Brighten Godfrey.
   ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis 2016 (SC'16)

5. Dimension-Free \Ell_p-Maximal Inequalities in Z_{m+1}^n. With Jordan Greenblatt and Ben Krause.
   Submitted, 2016.

6. Approximation of Non-Boolean 2-CSP. With Guy Kindler and Luca Trevisan.
   SODA, 2016.

7. Multisection in the Stochastic Block Model Using Semidefinite Programming. With Naman Agarwal, Afonso Bandeira and Konstantinos Koiliaris.
   Book chapter in the book ``Compressed Sensing and its Applications'', Birkhauser; Auflage, 2016.

8. Unique Games on The Hypercube. With Naman Agarwal, Guy Kindler and Luca Trevisan.
   Published in The Chicago Journal of Theoretical Computer Science, 2014.

9. Measuring and Understanding Throughput of Network Topologies. With Sanjeetha Abdu Jyothi, Ankit Singla and Brighten Godfrey.
   Short Paper, SIGMETRICS 2014.

10. Small Lifts of Expander Graphs are Expanding. With Naman Agarwal and Vivek Madhan.
    Submitted, 2014.

11. High Throughput Data Center Topology Design.
    With Ankit Singla and Brighten Godfrey.
    NSDI 2014.

12. Specta of Random Graphs With Planted Partitions.
    With Sanjoy Dasgupta and Konstantinos Koiliaris.
    Manuscript, 2013.

13. Maximal Inequality for Sperical Means on the Hypercube.
    With Aram Harrow and Leonard Schulman.
    Published in the Special Issue of the Journal of Theory of Computing, 2013.
    Appeared on popular mathematics blog.

14. How to Play Unique Games Against a Semi-Random Adversary.
    With Konstantin Makarychev and Yury Makarychev.
    FOCS 2011.

15. Sparsest Cut on quotients of the hypercube.
    With James Lee.
    CATS 2011.

16. Spectral Algorithms for Unique Games.
    CCC 2010. Invited to CCC 2010 journal, Special Issue.

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

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

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

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

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

P.h.D Thesis

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

Students

1. Naman Agarwal: Masters Student, 2012 - 2014.
2. David Hannasch: Masters Student, 2012 - 2014.
3. Konstantinos Koiliaris: PhD Student, 2013 - 2016.
4. Charles Carlson: Masters Student, continuing for PhD, 2016 - Present.
5. Hsien Chih-Chang: Research Assistant, 2015-Present.

 

Program Comittees

1. SODA 2014
2. FOCS 2016