research
∙
07/18/2023
Approximately counting independent sets in dense bipartite graphs via subspace enumeration
We give a randomized algorithm that approximates the number of independe...
share
research
∙
04/05/2022
Algorithms for the ferromagnetic Potts model on expanders
We give algorithms for approximating the partition function of the ferro...
research
∙
11/04/2021
Computational thresholds for the fixed-magnetization Ising model
The ferromagnetic Ising model is a model of a magnetic material and a ce...
research
∙
03/02/2020
Efficient algorithms for the Potts model on small-set expanders
We develop an approximation algorithm for the partition function of the ...
research
∙
11/04/2019
Statistical physics approaches to Unique Games
We show how two techniques from statistical physics can be adapted to so...
research
∙
10/23/2018
A Ramsey-type Theorem on the Max-Cut Value of d-Regular Graphs
In this paper we study the problem of finding large cuts in K_r-free gra...
research
∙
05/01/2018
Spectrally Robust Graph Isomorphism
We initiate the study of spectral generalizations of the graph isomorphi...
research
∙
12/29/2017
Optimal Lower Bounds for Sketching Graph Cuts
We study the space complexity of sketching cuts and Laplacian quadratic ...
research
∙
07/08/2015