Alexandra Kolla

According to our database, Alexandra Kolla authored at least 32 papers between 2008 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

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

Charlie Carlson, Ewan Davies, Alexandra Kolla, Aditya Potukuchi

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023

Special Section on the Fifty-Ninth Annual IEEE Symposium on Foundations of Computer Science (2018).

Elette Boyle, Vincent Cohen-Addad, Alexandra Kolla, Mikkel Thorup

SIAM J. Comput., December, 2023

Approximately counting independent sets in dense bipartite graphs via subspace enumeration.

Charlie Carlson, Ewan Davies, Alexandra Kolla, Aditya Potukuchi

CoRR, 2023

2022

Computational thresholds for the fixed-magnetization Ising model.

Charlie Carlson, Ewan Davies, Alexandra Kolla, Will Perkins

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Algorithms for the ferromagnetic Potts model on expanders.

Charlie Carlson, Ewan Davies, Nicolas Fraiman, Alexandra Kolla, Aditya Potukuchi, Corrine Yap

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Lower Bounds for Max-Cut in H-Free Graphs via Semidefinite Programming.

Charles Carlson, Alexandra Kolla, Ray Li, Nitya Mani, Benny Sudakov, Luca Trevisan

SIAM J. Discret. Math., 2021

2020

Spectral aspects of symmetric matrix signings.

Charles Carlson, Karthekeyan Chandrasekaran, Hsien-Chih Chang, Naonori Kakimura, Alexandra Kolla

Discret. Optim., 2020

Efficient algorithms for the Potts model on small-set expanders.

Charles Carlson, Ewan Davies, Alexandra Kolla

CoRR, 2020

Lower Bounds for Max-Cut via Semidefinite Programming.

Charles Carlson, Alexandra Kolla, Ray Li, Nitya Mani, Benny Sudakov, Luca Trevisan

Proceedings of the LATIN 2020: Theoretical Informatics, 2020

Statistical Physics Approaches to Unique Games.

Matthew Coulson, Ewan Davies, Alexandra Kolla, Viresh Patel, Guus Regts

Proceedings of the 35th Computational Complexity Conference, 2020

2019

On the Expansion of Group-Based Lifts.

Naman Agarwal, Karthekeyan Chandrasekaran, Alexandra Kolla, Vivek Madan

SIAM J. Discret. Math., 2019

Optimal Lower Bounds for Sketching Graph Cuts.

Charles Carlson, Alexandra Kolla, Nikhil Srivastava, Luca Trevisan

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018

A Ramsey-type Theorem on the Max-Cut Value of d-Regular Graphs.

Charles Carlson, Alexandra Kolla, Luca Trevisan

CoRR, 2018

Spectrally Robust Graph Isomorphism.

Alexandra Kolla, Ioannis Koutis, Vivek Madan, Ali Kemal Sinop

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2016

Largest Eigenvalue and Invertibility of Symmetric Matrix Signings.

Charles Carlson, Karthekeyan Chandrasekaran, Hsien-Chih Chang, Alexandra Kolla

CoRR, 2016

Approximation of non-boolean 2CSP.

Guy Kindler, Alexandra Kolla, Luca Trevisan

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Measuring and understanding throughput of network topologies.

Sangeetha Abdu Jyothi, Ankit Singla, Brighten Godfrey, Alexandra Kolla

Proceedings of the International Conference for High Performance Computing, 2016

2015

Multisection in the Stochastic Block Model using Semidefinite Programming.

Naman Agarwal, Afonso S. Bandeira, Konstantinos Koiliaris, Alexandra Kolla

CoRR, 2015

Unique Games on the Hypercube.

Naman Agarwal, Guy Kindler, Alexandra Kolla, Luca Trevisan

Chic. J. Theor. Comput. Sci., 2015

2014

Dimension-Free L₂ Maximal Inequality for Spherical Means in the Hypercube.

Aram W. Harrow, Alexandra Kolla, Leonard J. Schulman

Theory Comput., 2014

Measuring throughput of data center network topologies.

Sangeetha Abdu Jyothi, Ankit Singla, Brighten Godfrey, Alexandra Kolla

Proceedings of the ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, 2014

High Throughput Data Center Topology Design.

Ankit Singla, Philip Brighten Godfrey, Alexandra Kolla

Proceedings of the 11th USENIX Symposium on Networked Systems Design and Implementation, 2014

2013

Small Lifts of Expander Graphs are Expanding.

Naman Agarwal, Alexandra Kolla, Vivek Madan

CoRR, 2013

2011

How to Play Unique Games against a Semi-Random Adversary

Alexandra Kolla, Konstantin Makarychev, Yury Makarychev

CoRR, 2011

Spectral Algorithms for Unique Games.

Alexandra Kolla

Comput. Complex., 2011

How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games.

Alexandra Kolla, Konstantin Makarychev, Yury Makarychev

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Sparsest Cut on Quotients of the Hypercube.

Alexandra Kolla, James Lee

Proceedings of the Seventeenth Computing: The Australasian Theory Symposium, 2011

2010

Subgraph sparsification and nearly optimal ultrasparsifiers.

Alexandra Kolla, Yury Makarychev, Amin Saberi, Shang-Hua Teng

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

2009

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

Alexandra Kolla

PhD thesis, 2009

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

Rahul Jain, Alexandra Kolla, Gatis Midrijanis, Ben W. Reichardt

Quantum Inf. Comput., 2009

2008

Unique games on expanding constraint graphs are easy: extended abstract.

Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, Nisheeth K. Vishnoi

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Making Classical Honest Verifier Zero Knowledge Protocols Secure against Quantum Attacks.

Sean Hallgren, Alexandra Kolla, Pranab Sen, Shengyu Zhang

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008