Nima Anari

Nima Anari

Computer Science Department, Stanford University

I am an assistant professor in the Computer Science Theory Group at Stanford University.

I obtained my Ph.D. in Computer Science at UC Berkeley. At Berkeley, I was advised by Satish Rao, and was part of the Theory Group. Before that, I received my B.Sc. in Computer Engineering and Mathematics from Sharif University of Technology in Tehran.

I am broadly interested in the design and analysis of algorithms and more generally theoretical computer science. Some topics that I have worked on include:

  • Geometry of Polynomials and Algorithmic Applications
  • Approximate Sampling and Counting
  • Spectral Graph Theory and Spectral Algorithms
  • Algorithmic Game Theory and Mechanism Design

Take a look at my Curriculum Vitae, Google Scholar Profile, or DBLP Page.

Teaching

CS 263: Counting and Sampling

Nima Anari

Autumn 2020

CS 221: Artificial Intelligence: Principles and Techniques

Chelsea Finn and Nima Anari

Spring 2020

CS 260: Geometry of Polynomials in Algorithm Design

Nima Anari

Winter 2020

Papers

28

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

, , , and

Manuscript

27

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

, , , and

Manuscript

26

Batch Active Learning Using Determinantal Point Processes

, , , and

Manuscript

25

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

, , , and

Manuscript

24

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

, , and

FOCS 2020

Invited to special issue of SIAM Journal on Computing.

23

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

and

FOCS 2020

22

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

and

APPROX 2020

21

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

and

ITCS 2020

20

A Tight Analysis of Bethe Approximation for Permanent

and

FOCS 2019

Invited to special issue of SIAM Journal on Computing.

19

Nearly Optimal Pricing Algorithms for Production Constrained and Laminar Bayesian Selection

, , , and

EC 2019

18

Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid

, , , and

STOC 2019

Awarded best paper.
Invited to Theory of Computing.

17

Structured Robust Submodular Maximization: Offline and Online Algorithms

, , , , , and

AISTATS 2019

16

Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons

, , , , , and

NeurIPS 2018

15

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

, , and

FOCS 2018

14

Planar Graph Perfect Matching is in NC

and

FOCS 2018
J. ACM 67

Invited to special issue of SIAM Journal on Computing.

13

Budget Feasible Procurement Auctions

, , and

Oper. Res. 66

Invited to GEB special issue on Algorithmic Game Theory.

12

Graph Clustering using Effective Resistance

, , , and

ITCS 2018

11

Approximating the Largest Root and Applications to Interlacing Families

, , , and

SODA 2018

10

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

, , , and

SODA 2018

9

Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices

, , , and

FOCS 2017

8

A Generalization of Permanent Inequalities and Applications in Counting and Optimization

and

STOC 2017

7

Nash Social Welfare, Matrix Permanent, and Stable Polynomials

, , , and

ITCS 2017

Elevated to invited paper.

6

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

, , and

COLT 2016

5

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

and

FOCS 2015

Invited to special issue of SIAM Journal on Computing.

4

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

and

Manuscript

3

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

, , and

FOCS 2014

2

Euclidean Movement Minimization

, , , and

CCCG 2011
J. Comb. Optim. 32

1

Equilibrium Pricing with Positive Externalities

, , , , , , and

WINE 2010
Theor. Comput. Sci. 476

Contact

Email
anari@cs.stanford.edu
Phone
+1 (510) 520-7774
Homepage
https://nimaanari.com
Address
353 Jane Stanford Way
Gates 474
Stanford, CA 94305