23 citations · 101 across the 39 of their papers we have counts for
6 papers · 1 filter
Log-Concave Polynomials III: Mason's Ultra-Log-Concavity Conjecture for Independent Sets of Matroids
Nima Anari, Kuikui Liu, Shayan Oveis Gharan +1
We give a self-contained proof of the strongest version of Mason's conjecture, namely that for any matroid the sequence of the number of independent sets of given sizes is ultra lo…
A Tight Analysis of Bethe Approximation for Permanent
Nima Anari, Alireza Rezaei
We prove that the permanent of nonnegative matrices can be deterministically approximated within a factor of in polynomial time, improving upon the previous determinis…
Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid
Nima Anari, Kuikui Liu, Shayan Oveis Gharan +1
We design an FPRAS to count the number of bases of any matroid given by an independent set oracle, and to estimate the partition function of the random cluster model of any matroid…
Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons
Nima Anari, Constantinos Daskalakis, Wolfgang Maass +3
We analyze linear independence of rank one tensors produced by tensor powers of randomly perturbed vectors. This enables efficient decomposition of sums of high-order tensors. Our…
Linear Programming Based Near-Optimal Pricing for Laminar Bayesian Online Selection
Nima Anari, Rad Niazadeh, Amin Saberi +1
The Bayesian online selection problem aims to design a pricing scheme for a sequence of arriving buyers that maximizes the expected social welfare (or revenue) subject to different…
Log-Concave Polynomials I: Entropy and a Deterministic Approximation Algorithm for Counting Bases of Matroids
Nima Anari, Shayan Oveis Gharan, Cynthia Vinzant
We give a deterministic polynomial time -approximation algorithm for the number of bases of a given matroid of rank and the number of common bases of any two matroids…