Alex

Alexandra Kolla

I am an Assistant Professor at the Computer Science Department at UC Santa Cruz .
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. Before joining UCSC, I was a professor at CU Boulder. Here is my Boulder webpage.

Research interests: Spectral Graph Theory, Algorithms, Complexity, Statistical Physics, 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] UCSC [dot] edu
Office 345B
Engineering Building 2, UCSC Campus

Teaching at UCSC

Fall 2023 Introduction to Discrete Mathematics, CSE16.

Winter 2023 Introduction to Algorithms, CSE102.

Fall 2022 Introduction to Quantum Computing, CSE109/PHYS150.

Spring 2022 Randomized Algorithms, CSE 290A.

Winter 2022 Introduction to Algorithms, CSE 102.

      Papers

      1. Quantum Advantage Over Classical for Local Max Cut. With Charlie Carlson, Zackary Jorquera, and Steven Kordonowy.
        Submitted, 2023.

      2. Approximately counting independent sets in dense bipartite graphs via subspace enumeration. With Charlie Carlson, Ewan Davies, Aditya Potukuchi
        Submitted, 2023.

      3. Approximation Algorithms for Quantum Max-d-Cut. With Charlie Carlson, Zackary Jorquera, Steven Kordonowy, and Stuart Wayland.
        Submitted, 2023.

      4. Efficient algorithms for the Potts model on small-set expanders. With Charlie Carlson, Ewan Davies.
        Accepted for Publication in the Chicago Journal of Computing, 2023.

      5. Algorithms for the Ferromagnetic Potts Model on Expanders. With Charlie Carlson, Ewan Davies, Nicolas Fraiman, Aditya Potukuchi, and Corrine Yap.
        In Proceedings of the 63rd IEEE Symposium on Foundation of Computer Science (FOCS), 2022.

      6. Computational thresholds for the fixed-magnetization Ising model. With Charlie Carlson, Ewan Davies, and Will Perkins.
        In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC), 2022.

      7. Statistical Physics Algorithms for Unique Games. With Matthew Coulson, Ewan Davies, Viresh Patel, Guus Regts.
        In Proceedings of the Computational Complexity Conference (CCC), 2020.

      8. Spectral Aspects of Symmetric Matrix Signings. With Charlie Carlson, Karthekeyan Chandrasekaran, Hsien-Chih Chang and Naonori Kakimura.
        Published in the Journal of Discrete Optimization, Volume 37, 2020. Conference version in Proceedings of MCFCS, 2019: 44th International Symposium on Mathematical Foundations of Computer Science.

      9. A Ramsey-Type theorem on the Max-Cut value of d-Regular graphs. With Charlie Carlson, Ray Li, Nitya Mani, Benny Sudakov, Luca Trevisan.
        In Proceedings of LATIN 2020.

      10. On the Expansion of Group-Based Lifts. With Naman Agarwal, Karthekeyan Chandrasekaran and Vivek Madan.
        Published at SIDMA, Volume 33, Issue 3, 2019.

      11. Invertibility and Largest Eigenvalue of Symmetric Matrix Signings. With Charlie Carlson, Karthekeyan Chandrasekaran and Hsien-Chih Chang.
        In Proceedings of MCFCS, 2019: 44th International Symposium on Mathematical Foundations of Computer Science.

      12. Optimal Lowerbounds for Sketching Graph Cuts. With Charlie Carlson, Nikhil Srivastava, and Luca Trevisan.
        In SODA, 2019.

      13. Dimension-Free \Ell_p-Maximal Inequalities in Z_{m+1}^n. With Jordan Greenblatt and Ben Krause.
        To Appear, Journal of International Mathematics Research Notices, 2018.

      14. Spectrally Robust Graph Isomorphism. With Yannis Koutis, Vivek Madan, Ali Sinop.
        ICALP, 2018.
      15. On the Expansion of Group-Based Lifts. With Naman Agarwal, Karthekeyan Chandrasekaran and Vivek Madan.
        RANDOM, 2017.

      16. 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).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

      Past Students

        1. Naman Agarwal : Masters Student, UIUC, 2012 - 2014. Now at Google research.
        2. David Hannasch: Masters Student, UIUC, 2012 - 2014.
        3. Konstantinos Koiliaris: PhD Student, UIUC, 2013 - 2016.Now atGoldman Saks
        4. Hsien Chih-Chang : Research Assistant, 2015-2017.

      Current Students

        1. Charlie Carlson: PhD Student, CU Boulder, 2016 - 2023. Now a Postdoc at UC Santa Barbara.
        2. Steven Kordonowy: PhD Student, UC Santa Cruz,  2019 - Present.
        3. Zackary Jorquera : PhD Student, UC Santa Cruz,  2022 - Present.

      Postdocs

        1. Ali Kemal Sinop , UIUC 2015 - 2017. Now at Google.
        2. Nathan Lindzey , CU Boulder 2019 - 2022.
        3. Eric Reckwerdt , CU Boulder 2019 - 2021.
        4. Ewan Davies , CU Boulder 2019 - 2022, Now a professor at Colorado State University.

         

      Program Comittees

      1. SODA 2014
      2. FOCS 2016
      3. FOCS 2018
      4. FOCS 2020
      5. SODA 2024

         

      Conference Organization

      1. FOCS 2021, FOCS 2022, FOCS 2023