124 citations · 275 across the 42 of their papers we have counts for
11 papers · 1 filter
Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling
Antonio Blanca, Zongchen Chen, Daniel Štefankovič +1
We study the identity testing problem for high-dimensional distributions. Given as input an explicit distribution , an , and access to sampling oracle(s) for a hi…
Fast sampling via spectral independence beyond bounded-degree graphs
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg +1
Spectral independence is a recently-developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal…
Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness Region
Zongchen Chen, Andreas Galanis, Daniel Štefankovič +1
For spin systems, such as the -colorings and independent-set models, approximating the partition function in the so-called non-uniqueness region, where the model exhibits long-r…
Rapid Mixing for Colorings via Spectral Independence
Zongchen Chen, Andreas Galanis, Daniel Štefankovič +1
The spectral independence approach of Anari et al. (2020) utilized recent results on high-dimensional expanders of Alev and Lau (2020) and established rapid mixing of the Glauber d…
Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models
Antonio Blanca, Zongchen Chen, Daniel Štefankovič +1
We study identity testing for restricted Boltzmann machines (RBMs), and more generally for undirected graphical models. Given sample access to the Gibbs distribution corresponding…
Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
Ivona Bezakova, Antonio Blanca, Zongchen Chen +2
We study the identity testing problem in the context of spin systems or undirected graphical models, where it takes the following form: given the parameter specification of the mod…
On Counting Perfect Matchings in General Graphs
Daniel Štefankovič, Eric Vigoda, John Wilmes
Counting perfect matchings has played a central role in the theory of counting problems. The permanent, corresponding to bipartite graphs, was shown to be #P-complete to compute ex…
Spatial mixing and the connective constant: Optimal bounds
Alistair Sinclair, Piyush Srivastava, Daniel Štefankovič +1
We study the problem of deterministic approximate counting of matchings and independent sets in graphs of bounded connective constant. More generally, we consider the problem of ev…
A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions
Daniel Stefankovic, Santosh Vempala, Eric Vigoda
Given n elements with nonnegative integer weights w1,..., wn and an integer capacity C, we consider the counting version of the classic knapsack problem: find the number of distinc…
Approximating L1-distances between mixture distributions using random projections
Satyaki Mahalanabis, Daniel Stefankovic
We consider the problem of computing L1-distances between every pair ofcprobability densities from a given family. We point out that the technique of Cauchy random projections (Ind…
Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting
Daniel Stefankovic, Santosh Vempala, Eric Vigoda
We present a near-optimal reduction from approximately counting the cardinality of a discrete set to approximately sampling elements of the set. An important application of our wor…