research
∙
07/19/2023
Universality of Spectral Independence with Applications to Fast Mixing in Spin Glasses
We study Glauber dynamics for sampling from discrete distributions μ on ...
share
research
∙
05/25/2023
Parallel Sampling of Diffusion Models
Diffusion models are powerful generative models but suffer from slow sam...
research
∙
05/20/2023
Distortion in metric matching with ordinal preferences
Suppose that we have n agents and n items which lie in a shared metric s...
research
∙
04/06/2022
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence
We design fast algorithms for repeatedly sampling from strongly Rayleigh...
research
∙
03/21/2022
Improved Sampling-to-Counting Reductions in High-Dimensional Expanders and Faster Parallel Determinantal Sampling
We study parallel sampling algorithms for classes of distributions defin...
research
∙
11/05/2021
Entropic Independence II: Optimal Sampling and Concentration via Restricted Modified Log-Sobolev Inequalities
We introduce a framework for obtaining tight mixing times for Markov cha...
research
∙
09/27/2021
Learning Multimodal Rewards from Rankings
Learning from human feedback has shown to be a useful approach in acquir...
research
∙
09/14/2021
Domain Sparsification of Discrete Distributions using Entropic Independence
We present a framework for speeding up the time it takes to sample from ...
research
∙
06/08/2021
Entropic Independence in High-Dimensional Expanders: Modified Log-Sobolev Inequalities for Fractionally Log-Concave Polynomials and the Ising Model
We introduce a notion called entropic independence for distributions μ d...
research
∙
02/10/2021
Simple and Near-Optimal MAP Inference for Nonsymmetric DPPs
Determinantal point processes (DPPs) are widely popular probabilistic mo...
research
∙
02/04/2021
Fractionally Log-Concave and Sector-Stable Polynomials: Counting Planar Matchings and More
We show fully polynomial time randomized approximation schemes (FPRAS) f...
research
∙
12/17/2020
Sampling Arborescences in Parallel
We study the problem of sampling a uniformly random directed rooted span...
research
∙
11/05/2020
Instance Based Approximations to Profile Maximum Likelihood
In this paper we provide a new efficient algorithm for approximately com...
research
∙
04/26/2020
An Extension of Plücker Relations with Applications to Subdeterminant Maximization
Given a matrix A and k≥ 0, we study the problem of finding the k× k subm...
research
∙
04/20/2020
Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Bases
We define a notion of isotropy for discrete set distributions. If μ is a...
research
∙
04/15/2020
Log-Concave Polynomials IV: Exchange Properties, Tight Mixing Times, and Faster Sampling of Spanning Trees
We prove tight mixing time bounds for natural random walks on bases of m...
research
∙
04/06/2020
The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood
In this paper we consider the problem of computing the likelihood of the...
research
∙
01/02/2020
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
We say a probability distribution μ is spectrally independent if an asso...
research
∙
06/19/2019
Batch Active Learning Using Determinantal Point Processes
Data collection and labeling is one of the main challenges in employing ...
research
∙
01/29/2019
Matching is as Easy as the Decision Problem, in the NC Model
We give an NC reduction from search to decision for the problem of findi...
research
∙
01/29/2019
A Pseudo-Deterministic RNC Algorithm for General Graph Perfect Matching
The difficulty of obtaining an NC perfect matching algorithm has led res...
research
∙
11/07/2018
A Tight Analysis of Bethe Approximation for Permanent
We prove that the permanent of nonnegative matrices can be deterministic...
research
∙
11/05/2018
Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid
We use recent developments in the area of high dimensional expanders and...
research
∙
11/05/2018
Log-Concave Polynomials III: Mason's Ultra-Log-Concavity Conjecture for Independent Sets of Matroids
We give a self-contained proof of the strongest version of Mason's conje...
research
∙
10/28/2018
Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons
We analyze linear independence of rank one tensors produced by tensor po...
research
∙
07/15/2018
Nearly Optimal Pricing Algorithms for Production Constrained and Laminar Bayesian Selection
We study online pricing algorithms for the Bayesian selection problem wi...
research
∙
07/02/2018
Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids
We give a deterministic polynomial time 2^O(r)-approximation algorithm f...
research
∙
11/17/2017
Graph Clustering using Effective Resistance
#1#1 We design a polynomial time algorithm that for any weighted undire...
research
∙
09/22/2017