Nima Anari

According to our database, Nima Anari authored at least 59 papers between 2010 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Batch Active Learning of Reward Functions from Human Preferences.

Erdem Biyik, Nima Anari, Dorsa Sadigh

ACM Trans. Hum. Robot Interact., June, 2024

Trickle-Down in Localization Schemes and Applications.

Nima Anari, Frederic Koehler, Thuy-Duong Vuong

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Parallel Sampling via Counting.

Nima Anari, Ruiquan Gao, Aviad Rubinstein

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Universality of Spectral Independence with Applications to Fast Mixing in Spin Glasses.

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

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Fast parallel sampling under isoperimetry.

Nima Anari, Sinho Chewi, Thuy-Duong Vuong

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

2023

Parallel Discrete Sampling via Continuous Walks.

Nima Anari, Yizhi Huang, Tianyu Liu, Thuy-Duong Vuong, Brian Xu, Katherine Yu

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Quadratic Speedups in Parallel Sampling from Determinantal Distributions.

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

Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, 2023

Distortion in metric matching with ordinal preferences.

Nima Anari, Moses Charikar, Prasanna Ramakrishnan

Proceedings of the 24th ACM Conference on Economics and Computation, 2023

Parallel Sampling of Diffusion Models.

Andy Shih, Suneel Belkhale, Stefano Ermon, Dorsa Sadigh, Nima Anari

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

2022

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

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

CoRR, 2022

Entropic independence: optimal mixing of down-up random walks.

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

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Domain Sparsification of Discrete Distributions Using Entropic Independence.

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

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

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

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

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

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

Nima Anari, Thuy-Duong Vuong

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021

Structured Robust Submodular Maximization: Offline and Online Algorithms.

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

INFORMS J. Comput., 2021

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

CoRR, 2021

Entropic Independence in High-Dimensional Expanders: Modified Log-Sobolev Inequalities for Fractionally Log-Concave Polynomials and the Ising Model.

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

CoRR, 2021

Simple and Near-Optimal MAP Inference for Nonsymmetric DPPs.

Nima Anari, Thuy-Duong Vuong

CoRR, 2021

Log-concave polynomials in theory and applications (tutorial).

Nima Anari, Cynthia Vinzant

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 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

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

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

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

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Sampling Arborescences in Parallel.

Nima Anari, Nathan Hu, Amin Saberi, Aaron Schild

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Learning Multimodal Rewards from Rankings.

Vivek Myers, Erdem Biyik, Nima Anari, Dorsa Sadigh

Proceedings of the Conference on Robot Learning, 8-11 November 2021, London, UK., 2021

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

Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford

Proceedings of the Conference on Learning Theory, 2021

2020

Planar Graph Perfect Matching Is in NC.

Nima Anari, Vijay V. Vazirani

J. ACM, 2020

Log-Concave Polynomials IV: Exchange Properties, Tight Mixing Times, and Faster Sampling of Spanning Trees.

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

CoRR, 2020

Instance Based Approximations to Profile Maximum Likelihood.

Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

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

Nima Anari, Vijay V. Vazirani

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

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

Nima Anari, Kuikui Liu, Shayan Oveis Gharan

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

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

Nima Anari, Michal Derezinski

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

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

Nima Anari, Thuy-Duong Vuong

Proceedings of the Approximation, 2020

2019

Batch Active Learning Using Determinantal Point Processes.

Erdem Biyik, Kenneth Wang, Nima Anari, Dorsa Sadigh

CoRR, 2019

A Pseudo-Deterministic RNC Algorithm for General Graph Perfect Matching.

Nima Anari, Vijay V. Vazirani

CoRR, 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

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

A Tight Analysis of Bethe Approximation for Permanent.

Nima Anari, Alireza Rezaei

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Nearly Optimal Pricing Algorithms for Production Constrained and Laminar Bayesian Selection.

Nima Anari, Rad Niazadeh, Amin Saberi, Ali Shameli

Proceedings of the 2019 ACM Conference on Economics and Computation, 2019

2018

Budget Feasible Procurement Auctions.

Nima Anari, Gagan Goel, Afshin Nikzad

Oper. Res., 2018

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

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

CoRR, 2018

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

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

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Approximating the Largest Root and Applications to Interlacing Families.

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

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Graph Clustering using Effective Resistance.

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

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Log-Concave Polynomials, Entropy, and a Deterministic Approximation Algorithm for Counting Bases of Matroids.

Nima Anari, Shayan Oveis Gharan, Cynthia Vinzant

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Robust Submodular Maximization: Offline and Online Algorithms.

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

CoRR, 2017

A generalization of permanent inequalities and applications in counting and optimization.

Nima Anari, Shayan Oveis Gharan

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Nash Social Welfare, Matrix Permanent, and Stable Polynomials.

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

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices.

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

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Euclidean movement minimization.

Nima Anari, MohammadAmin Fazli, Mohammad Ghodsi, MohammadAli Safari

J. Comb. Optim., 2016

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

Nima Anari, Shayan Oveis Gharan, Alireza Rezaei

CoRR, 2016

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

Nima Anari, Shayan Oveis Gharan, Alireza Rezaei

Proceedings of the 29th Conference on Learning Theory, 2016

2015

New Approaches to the Asymmetric Traveling Salesman and Related Problems.

Nima Anari

PhD thesis, 2015

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

Nima Anari, Shayan Oveis Gharan

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

Mechanisms Design for Crowdsourcing: An Optimal 1-1/e Approximate Budget-Feasible Mechanism for Large Markets.

Nima Anari, Gagan Goel, Afshin Nikzad

CoRR, 2014

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

Nima Anari, Shayan Oveis Gharan

CoRR, 2014

Effective-Resistance-Reducing Flows and Asymmetric TSP.

Nima Anari, Shayan Oveis Gharan

CoRR, 2014

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

Nima Anari, Gagan Goel, Afshin Nikzad

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Equilibrium pricing with positive externalities.

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

Theor. Comput. Sci., 2013

2011

Euclidean Movement Minimization.

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

Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

2010

Equilibrium Pricing with Positive Externalities (Extended Abstract).

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

Proceedings of the Internet and Network Economics - 6th International Workshop, 2010