9 citations · 13 across the 8 of their papers we have counts for
11 papers
Approximation Algorithms for Quantum Max--Cut
Charlie Carlson, Zackary Jorquera, Alexandra Kolla +2
We initiate the algorithmic study of the Quantum Max--Cut problem, a quantum generalization of the well-known Max--Cut problem. The Quantum Max--Cut problem involves findi…
Approximation Algorithms for Norm Multiway Cut
Charlie Carlson, Jafar Jafarov, Konstantin Makarychev +2
We consider variants of the classic Multiway Cut problem. Multiway Cut asks to partition a graph into parts so as to separate given terminals. Recently, Chandrasekaran…
Approximately counting independent sets in dense bipartite graphs via subspace enumeration
Charlie Carlson, Ewan Davies, Alexandra Kolla +1
We give a randomized algorithm that approximates the number of independent sets in a dense, regular bipartite graph -- in the language of approximate counting, we give an FPRAS for…
A quantum advantage over classical for local max cut
Charlie Carlson, Zackary Jorquera, Alexandra Kolla +1
We compare the performance of a quantum local algorithm to a similar classical counterpart on a well-established combinatorial optimization problem LocalMaxCut. We show that a popu…
Algorithms for the ferromagnetic Potts model on expanders
Charlie Carlson, Ewan Davies, Nicolas Fraiman +3
We give algorithms for approximating the partition function of the ferromagnetic -color Potts model on graphs of maximum degree . Our primary contribution is a fully polynomi…
Computational thresholds for the fixed-magnetization Ising model
Charlie Carlson, Ewan Davies, Alexandra Kolla +1
The ferromagnetic Ising model is a model of a magnetic material and a central topic in statistical physics. It also plays a starring role in the algorithmic study of approximate co…
Efficient algorithms for the Potts model on small-set expanders
Charles Carlson, Ewan Davies, Alexandra Kolla
An emerging trend in approximate counting is to show that certain `low-temperature' problems are easy on typical instances, despite worst-case hardness results. For the class of re…
Lower bounds for Max-Cut in -free graphs via semidefinite programming
Charles Carlson, Alexandra Kolla, Ray Li +3
For a graph , let denote the size of the maximum cut in . The problem of estimating as a function of the number of vertices and edges of has a long history…
Improving the smoothed complexity of FLIP for max cut problems
Ali Bibak, Charles Carlson, Karthekeyan Chandrasekaran
Finding locally optimal solutions for max-cut and max--cut are well-known PLS-complete problems. An instinctive approach to finding such a locally optimum solution is the FLIP m…
Optimal Lower Bounds for Sketching Graph Cuts
Charles Carlson, Alexandra Kolla, Nikhil Srivastava +1
We study the space complexity of sketching cuts and Laplacian quadratic forms of graphs. We show that any data structure which approximately stores the sizes of all cuts in an undi…
Invertibility and Largest Eigenvalue of Symmetric Matrix Signings
Charles Carlson, Karthekeyan Chandrasekaran, Hsien-Chih Chang +1
The spectra of signed matrices have played a fundamental role in social sciences, graph theory, and control theory. In this work, we investigate the computational problems of ident…