Alexandra Kolla

Classical Algorithms for Bipartite Quantum Max-Cut on Dense Expanders

With Stuart Wayland and Zackary Jorquera.

Preprint, arXiv:2610.03670 (2026).

Monogamy of Entanglement Bounds and Improved Approximation Algorithms for Qudit Hamiltonians

With Zackary Jorquera, Steven Kordonowy, Juspreet Singh Sandhu, and Stuart Wayland.

Quantum 10, 2088 (2026).

A Spectral Approach to Approximately Counting Independent Sets in Dense Bipartite Graphs

With Charlie Carlson, Ewan Davies, and Aditya Potukuchi.

ICALP 2024, LIPIcs 297, 35:1–35:18.

Algorithms for the ferromagnetic Potts model on expanders

With Charlie Carlson, Ewan Davies, Nicolas Fraiman, Aditya Potukuchi, and Corrine Yap.

Combinatorics, Probability and Computing 33(4), 487–517 (2024). Conference version: FOCS 2022.

Efficient algorithms for the Potts model on small-set expanders

With Charlie Carlson and Ewan Davies.

Chicago Journal of Theoretical Computer Science, 2024, Article 1, 1–31.

Approximation Algorithms for Quantum Max-d-Cut

With Charlie Carlson, Zackary Jorquera, Steven Kordonowy, and Stuart Wayland.

Preprint, arXiv:2309.10957 (2023). Presented as a poster at QIP 2024.

A quantum advantage over classical for local max cut

With Charlie Carlson, Zackary Jorquera, and Steven Kordonowy.

Preprint, arXiv:2304.08420 (2023). Presented as a poster at QIP 2024.

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.

Statistical Physics Algorithms for Unique Games

With Matthew Coulson, Ewan Davies, Viresh Patel, Guus Regts.

In Proceedings of the Computational Complexity Conference (CCC), 2020.

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 MFCS, 2019: 44th International Symposium on Mathematical Foundations of Computer Science.

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.

On the Expansion of Group-Based Lifts

With Naman Agarwal, Karthekeyan Chandrasekaran and Vivek Madan.

Published at SIDMA, Volume 33, Issue 3, 2019.

Invertibility and Largest Eigenvalue of Symmetric Matrix Signings

With Charlie Carlson, Karthekeyan Chandrasekaran and Hsien-Chih Chang.

In Proceedings of MFCS, 2019: 44th International Symposium on Mathematical Foundations of Computer Science.

Optimal Lowerbounds for Sketching Graph Cuts

With Charlie Carlson, Nikhil Srivastava, and Luca Trevisan.

In SODA, 2019.

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.

Spectrally Robust Graph Isomorphism

With Yannis Koutis, Vivek Madan, Ali Sinop.

ICALP, 2018.

On the Expansion of Group-Based Lifts

With Naman Agarwal, Karthekeyan Chandrasekaran and Vivek Madan.

RANDOM, 2017.

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

Approximation of Non-Boolean 2-CSP

With Guy Kindler and Luca Trevisan.

SODA, 2016.

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.

Unique Games on The Hypercube

With Naman Agarwal, Guy Kindler and Luca Trevisan.

Published in The Chicago Journal of Theoretical Computer Science, 2014.

Measuring and Understanding Throughput of Network Topologies

With Sanjeetha Abdu Jyothi, Ankit Singla and Brighten Godfrey.

Short Paper, SIGMETRICS 2014.

Small Lifts of Expander Graphs are Expanding

With Naman Agarwal and Vivek Madhan.

Submitted, 2014.

High Throughput Data Center Topology Design

With Ankit Singla and Brighten Godfrey.

NSDI 2014.

Spectra of Random Graphs With Planted Partitions

With Sanjoy Dasgupta and Konstantinos Koiliaris.

Manuscript, 2013.

Maximal Inequality for Spherical 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.

How to Play Unique Games Against a Semi-Random Adversary

With Konstantin Makarychev and Yury Makarychev.

FOCS 2011.

Sparsest Cut on quotients of the hypercube

With James Lee.

CATS 2011.

Spectral Algorithms for Unique Games

CCC 2010. Invited to CCC 2010 journal, Special Issue.

Subgraph Sparsification and Nearly Optimal Ultrasparsifiers

With Yury Makarychev, Amin Saberi, Shang-hua Teng.

STOC 2010.

Unique Games on Expanding Constraint Graphs are Easy

With Sanjeev Arora, Subhash Khot, David Steurer, Madhur Tulsiani and Nisheeth Vishnoi.

STOC 2008.

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.

Playing Unique Games Using Graph Spectra

With Madhur Tulsiani.

Manuscript, 2007.

On parallel composition of zero-knowledge proofs with black-box quantum simulators

with Rahul Jain, Gatis Midrijanis, and Ben Reichardt.

QIC Journal, 2007.