research
∙
07/25/2023
Spectral Independence Lecture Notes
These are self-contained lecture notes for spectral independence. For an...
share
research
∙
07/15/2023
Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees
We study the mixing time of the single-site update Markov chain, known a...
research
∙
10/02/2022
Beyond the Existential Theory of the Reals
We show that completeness at higher levels of the theory of the reals is...
research
∙
07/19/2022
Identity Testing for High-Dimensional Distributions via Entropy Tensorization
We present improved algorithms and matching statistical and computationa...
research
∙
06/23/2022
Approximating observables is as hard as counting
We study the computational complexity of estimating local observables fo...
research
∙
06/15/2022
Spiraling and Folding: The Topological View
For every n, we construct two curves in the plane that intersect at leas...
research
∙
02/11/2022
Metastability of the Potts ferromagnet on random regular graphs
We study the performance of Markov chains for the q-state ferromagnetic ...
research
∙
11/07/2021
Fast sampling via spectral independence beyond bounded-degree graphs
Spectral independence is a recently-developed framework for obtaining sh...
research
∙
05/04/2021
Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness Region
For spin systems, such as the q-colorings and independent-set models, ap...
research
∙
03/12/2021
On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization
For general spin systems, we prove that a contractive coupling for any l...
research
∙
07/16/2020
The Swendsen-Wang Dynamics on Trees
The Swendsen-Wang algorithm is a sophisticated, widely-used Markov chain...
research
∙
07/16/2020
Rapid Mixing for Colorings via Spectral Independence
The spectral independence approach of Anari et al. (2020) utilized recen...
research
∙
06/30/2020
Understanding Diversity based Pruning of Neural Networks – Statistical Mechanical Analysis
Deep learning architectures with a huge number of parameters are often c...
research
∙
04/22/2020
Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models
We study identity testing for restricted Boltzmann machines (RBMs), and ...
research
∙
04/20/2020
The complexity of approximating averages on bounded-degree graphs
We prove that, unless P=NP, there is no polynomial-time algorithm to app...
research
∙
09/16/2019
Improved Strong Spatial Mixing for Colorings on Trees
Strong spatial mixing (SSM) is a form of correlation decay that has play...
research
∙
01/22/2019
Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
We study the identity testing problem in the context of spin systems or ...
research
∙
07/13/2018
The complexity of approximating the matching polynomial in the complex plane
We study the problem of approximating the value of the matching polynomi...
research
∙
04/22/2018
Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs
We consider the problem of sampling from the Potts model on random regul...
research
∙
12/20/2017
On Counting Perfect Matchings in General Graphs
Counting perfect matchings has played a central role in the theory of co...
research
∙
11/01/2017
Inapproximability of the independent set polynomial in the complex plane
We study the complexity of approximating the independent set polynomial ...
research
∙
08/17/2017
Structure Learning of H-colorings
We study the structure learning problem for graph homomorphisms, commonl...
research
∙
04/06/2017
Rapid Mixing Swendsen-Wang Sampler for Stochastic Partitioned Attractive Models
The Gibbs sampler is a particularly popular Markov chain used for learni...
research
∙
03/21/2017
On The Projection Operator to A Three-view Cardinality Constrained Set
The cardinality constraint is an intrinsic way to restrict the solution ...
research
∙
09/26/2012