research
∙
07/26/2023
On the hardness of finding balanced independent sets in random bipartite graphs
We consider the algorithmic problem of finding large balanced independen...
share
research
∙
07/19/2023
Percolation on hypergraphs and the hard-core model
We prove tight bounds on the site percolation threshold for k-uniform hy...
research
∙
05/03/2023
Perfect Sampling for Hard Spheres from Strong Spatial Mixing
We provide a perfect sampling algorithm for the hard-sphere model on sub...
research
∙
02/13/2023
Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization
For many computational problems involving randomness, intricate geometri...
research
∙
11/01/2022
On the zeroes of hypergraph independence polynomials
We study the locations of complex zeroes of independence polynomials of ...
research
∙
03/29/2022
Algorithms and Barriers in the Symmetric Binary Perceptron Model
The symmetric binary perceptron () exhibits a dramatic statistical-to-co...
research
∙
02/17/2022
Strong spatial mixing for repulsive point processes
We prove that a Gibbs point process interacting via a finite-range, repu...
research
∙
02/11/2022
Fast and perfect sampling of subgraphs and polymer systems
We give an efficient perfect sampling algorithm for weighted, connected ...
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
∙
09/08/2021
Approximately counting independent sets in bipartite graphs via graph containers
By implementing algorithmic versions of Sapozhenko's graph container met...
research
∙
08/26/2021
Approximation algorithms for the random-field Ising model
Approximating the partition function of the ferromagnetic Ising model wi...
research
∙
08/02/2021
Approximate counting and sampling via local central limit theorems
We give an FPTAS for computing the number of matchings of size k in a gr...
research
∙
02/09/2021
Approximately counting independent sets of a given size in bounded-degree graphs
We determine the computational complexity of approximately counting and ...
research
∙
06/20/2020
Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
For Δ≥ 5 and q large as a function of Δ, we give a detailed picture of t...
research
∙
01/15/2020
Correlation decay for hard spheres via Markov chains
We improve upon all known lower bounds on the critical fugacity and crit...
research
∙
09/20/2019
Efficient sampling and counting algorithms for the Potts model on Z^d at all temperatures
For d > 2 and all q≥ q_0(d) we give an efficient algorithm to approximat...
research
∙
06/04/2019
Counting independent sets in unbalanced bipartite graphs
We give an FPTAS for approximating the partition function of the hard-co...
research
∙
01/20/2019
Markov chains for the hard-core model via polymer models
Jenssen, Keevash and Perkins give an FPTAS and an efficient sampling alg...
research
∙
07/12/2018
Algorithms for #BIS-hard problems on expander graphs
We give an FPTAS and an efficient sampling algorithm for the high-fugaci...
research
∙
06/29/2018