6 citations · 12 across the 6 of their papers we have counts for
8 papers · 1 filter
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…
Statistical physics approaches to Unique Games
Matthew Coulson, Ewan Davies, Alexandra Kolla +2
We show how two techniques from statistical physics can be adapted to solve a variant of the notorious Unique Games problem, potentially opening new avenues towards the Unique Game…
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…
Spectrally Robust Graph Isomorphism
Alexandra Kolla, Ioannis Koutis, Vivek Madan +1
We initiate the study of spectral generalizations of the graph isomorphism problem. (a)The Spectral Graph Dominance (SGD) problem: On input of two graphs and does there exi…
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…
Multisection in the Stochastic Block Model using Semidefinite Programming
Naman Agarwal, Afonso S. Bandeira, Konstantinos Koiliaris +1
We consider the problem of identifying underlying community-like structures in graphs. Towards this end we study the Stochastic Block Model (SBM) on -clusters: a random model on…