Papers
  • FOCS 2022 (to appear)

    Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence

    Nima Anari, Yang P. Liu, Thuy-Duong Vuong

      arXiv  DBLP 

  • COLT 2022

    From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization

    Nima Anari, Thuy-Duong Vuong

      arXiv  DBLP  Link 

  • STOC 2022

    Entropic independence: optimal mixing of down-up random walks

    Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, Thuy-Duong Vuong

      DBLP  Link 

  • Manuscript

    Entropic Independence II: Optimal Sampling and Concentration via Restricted Modified Log-Sobolev Inequalities

    Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, Thuy-Duong Vuong

    Extended abstract merged with the paper "Entropic Independence I: Modified Log-Sobolev Inequalities for Fractionally Log-Concave Distributions and High-Temperature Ising Models".

      arXiv  DBLP 

  • Manuscript

    Entropic Independence I: Modified Log-Sobolev Inequalities for Fractionally Log-Concave Distributions and High-Temperature Ising Models

    Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, Thuy-Duong Vuong

    Extended abstract merged with the paper "Entropic Independence II: Optimal Sampling and Concentration via Restricted Modified Log-Sobolev Inequalities".

      arXiv  DBLP 

  • Manuscript

    Improved Sampling-to-Counting Reductions in High-Dimensional Expanders and Faster Parallel Determinantal Sampling

    Nima Anari, Callum Burgess, Kevin Tian, Thuy-Duong Vuong

      arXiv  DBLP 

  • ITCS 2022

    Domain Sparsification of Discrete Distributions Using Entropic Independence

    Nima Anari, Michal Derezinski, Thuy-Duong Vuong, Elizabeth Yang

      arXiv  DBLP  Link 

  • COLT 2021

    The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood

    Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford

      arXiv  DBLP  Link 

  • ITCS 2021

    Sampling Arborescences in Parallel

    Nima Anari, Nathan Hu, Amin Saberi, Aaron Schild

      arXiv  DBLP  Link 

  • CoRL 2021

    Learning Multimodal Rewards from Rankings

    Vivek Myers, Erdem Biyik, Nima Anari, Dorsa Sadigh

      arXiv  DBLP  Link 

  • STOC 2021

    Fractionally log-concave and sector-stable polynomials: counting planar matchings and more

    Yeganeh Alimohammadi, Nima Anari, Kirankumar Shiragur, Thuy-Duong Vuong

      arXiv  DBLP  Link 

  • STOC 2021

    Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests

    Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant, Thuy-Duong Vuong

      arXiv  DBLP  Link 

  • ITCS 2020

    Matching Is as Easy as the Decision Problem, in the NC Model

    Nima Anari, Vijay V. Vazirani

      arXiv  DBLP  Link 

  • APPROX 2020

    An Extension of Plücker Relations with Applications to Subdeterminant Maximization

    Nima Anari, Thuy-Duong Vuong

      arXiv  DBLP  Link 

  • FOCS 2020

    Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Bases

    Nima Anari, Michal Derezinski

      arXiv  DBLP  Link 

  • FOCS 2020

    Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model

    Nima Anari, Kuikui Liu, Shayan Oveis Gharan

    Invited to special issue of SIAM Journal on Computing.

      arXiv  DBLP  Link 

  • NeurIPS 2020

    Instance Based Approximations to Profile Maximum Likelihood

    Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford

      arXiv  DBLP  Link 

  • Manuscript

    Batch Active Learning Using Determinantal Point Processes

    Erdem Biyik, Kenneth Wang, Nima Anari, Dorsa Sadigh

      arXiv  DBLP 

  • EC 2019

    Nearly Optimal Pricing Algorithms for Production Constrained and Laminar Bayesian Selection

    Nima Anari, Rad Niazadeh, Amin Saberi, Ali Shameli

      arXiv  DBLP  Link 

  • STOC 2019

    Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid

    Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant

    Invited to Theory of Computing.
    Awarded Best Paper of STOC 2019.

      arXiv  DBLP  Link 

  • AISTATS 2019

    Structured Robust Submodular Maximization: Offline and Online Algorithms

    Nima Anari, Nika Haghtalab, Seffi Naor, Sebastian Pokutta, Mohit Singh, Alfredo Torrico

      arXiv  DBLP  Link 

  • FOCS 2019

    A Tight Analysis of Bethe Approximation for Permanent

    Nima Anari, Alireza Rezaei

    Invited to special issue of SIAM Journal on Computing.

      arXiv  DBLP  Link 

  • FOCS 2018

    Log-Concave Polynomials I: Entropy and a Deterministic Approximation Algorithm for Counting Bases of Matroids

    Nima Anari, Shayan Oveis Gharan, Cynthia Vinzant

      arXiv  DBLP  Link 

  • FOCS 2018

    Planar Graph Perfect Matching Is in NC

    Nima Anari, Vijay V. Vazirani

    Invited to special issue of SIAM Journal on Computing.

      arXiv  DBLP  Link 

  • Manuscript

    Log-Concave Polynomials III: Mason's Ultra-Log-Concavity Conjecture for Independent Sets of Matroids

    Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant

      arXiv  DBLP 

  • ITCS 2018

    Graph Clustering using Effective Resistance

    Vedat Levi Alev, Nima Anari, Lap Chi Lau, Shayan Oveis Gharan

      arXiv  DBLP  Link 

  • Manuscript

    The Kadison-Singer Problem for Strongly Rayleigh Measures and Applications to Asymmetric TSP

    Nima Anari, Shayan Oveis Gharan

      arXiv  DBLP 

  • NeurIPS 2018

    Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons

    Nima Anari, Constantinos Daskalakis, Wolfgang Maass, Christos H. Papadimitriou, Amin Saberi, Santosh S. Vempala

      arXiv  DBLP  Link 

  • Oper. Res.

    Budget Feasible Procurement Auctions

    Nima Anari, Gagan Goel, Afshin Nikzad

    Invited to GEB special issue on Algorithmic Game Theory.

      DBLP  Link 

  • SODA 2018

    Approximating the Largest Root and Applications to Interlacing Families

    Nima Anari, Shayan Oveis Gharan, Amin Saberi, Nikhil Srivastava

      arXiv  DBLP  Link 

  • SODA 2018

    Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities

    Nima Anari, Tung Mai, Shayan Oveis Gharan, Vijay V. Vazirani

      arXiv  DBLP  Link 

  • FOCS 2017

    Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices

    Nima Anari, Leonid Gurvits, Shayan Oveis Gharan, Amin Saberi

      arXiv  DBLP  Link 

  • ITCS 2017

    Nash Social Welfare, Matrix Permanent, and Stable Polynomials

    Nima Anari, Shayan Oveis Gharan, Amin Saberi, Mohit Singh

    Elevated to invited paper.

      arXiv  DBLP  Link 

  • STOC 2017

    A generalization of permanent inequalities and applications in counting and optimization

    Nima Anari, Shayan Oveis Gharan

      arXiv  DBLP  Link 

  • COLT 2016

    Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes

    Nima Anari, Shayan Oveis Gharan, Alireza Rezaei

      arXiv  DBLP  Link 

  • FOCS 2015

    Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP

    Nima Anari, Shayan Oveis Gharan

    Invited to special issue of SIAM Journal on Computing.

      arXiv  DBLP  Link 

  • FOCS 2014

    Mechanism Design for Crowdsourcing: An Optimal 1-1/e Competitive Budget-Feasible Mechanism for Large Markets

    Nima Anari, Gagan Goel, Afshin Nikzad

      arXiv  DBLP  Link 

  • CCCG 2011

    Euclidean Movement Minimization

    MohammadAmin Fazli, MohammadAli Safari, Nima Anari, Pooya Jalaly Khalilabadi, Mohammad Ghodsi

      DBLP  Link 

  • WINE 2010

    Equilibrium Pricing with Positive Externalities

    Nima Anari, Shayan Ehsani, Mohammad Ghodsi, Nima Haghpanah, Nicole Immorlica, Hamid Mahini, Vahab S. Mirrokni

      DBLP  Link 

© 2022 Nima Anari · Built with Gatsby