
Entropic Independence in HighDimensional Expanders: Modified LogSobolev Inequalities for Fractionally LogConcave Polynomials and the Ising Model
We introduce a notion called entropic independence for distributions μ d...
read it

Simple and NearOptimal MAP Inference for Nonsymmetric DPPs
Determinantal point processes (DPPs) are widely popular probabilistic mo...
read it

Fractionally LogConcave and SectorStable Polynomials: Counting Planar Matchings and More
We show fully polynomial time randomized approximation schemes (FPRAS) f...
read it

Sampling Arborescences in Parallel
We study the problem of sampling a uniformly random directed rooted span...
read it

Instance Based Approximations to Profile Maximum Likelihood
In this paper we provide a new efficient algorithm for approximately com...
read it

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...
read it

Isotropy and LogConcave Polynomials: Accelerated Sampling and HighPrecision Counting of Matroid Bases
We define a notion of isotropy for discrete set distributions. If μ is a...
read it

LogConcave 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...
read it

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...
read it

Spectral Independence in HighDimensional Expanders and Applications to the Hardcore Model
We say a probability distribution μ is spectrally independent if an asso...
read it

Batch Active Learning Using Determinantal Point Processes
Data collection and labeling is one of the main challenges in employing ...
read it

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...
read it

A PseudoDeterministic RNC Algorithm for General Graph Perfect Matching
The difficulty of obtaining an NC perfect matching algorithm has led res...
read it

A Tight Analysis of Bethe Approximation for Permanent
We prove that the permanent of nonnegative matrices can be deterministic...
read it

LogConcave Polynomials II: HighDimensional Walks and an FPRAS for Counting Bases of a Matroid
We use recent developments in the area of high dimensional expanders and...
read it

LogConcave Polynomials III: Mason's UltraLogConcavity Conjecture for Independent Sets of Matroids
We give a selfcontained proof of the strongest version of Mason's conje...
read it

Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons
We analyze linear independence of rank one tensors produced by tensor po...
read it

Nearly Optimal Pricing Algorithms for Production Constrained and Laminar Bayesian Selection
We study online pricing algorithms for the Bayesian selection problem wi...
read it

Logconcave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids
We give a deterministic polynomial time 2^O(r)approximation algorithm f...
read it

Graph Clustering using Effective Resistance
#1#1 We design a polynomial time algorithm that for any weighted undire...
read it

Planar Graph Perfect Matching is in NC
Is perfect matching in NC? That is, is there a deterministic fast parall...
read it
Nima Anari
is this you? claim profile