Nima Anari

Nima Anari

Researcher
Computer Science Department, Stanford University

I am a researcher in the Computer Science Theory Group at Stanford University.

Previously I was a research fellow at the Simons Institute for the Theory of Computing, and a postdoctoral researcher at Stanford MS&E. 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 Applications in Algorithms, Combinatorics, and Probability
  • 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.

Papers

21

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

, , , and

Manuscript

20

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

, , , and

Manuscript

19

A Tight Analysis of Bethe Approximation for Permanent

and

Manuscript

18

Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons

, , , , , and

NIPS 2018

17

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

, , and

FOCS 2018

16

Planar Graph Perfect Matching is in NC

and

FOCS 2018

Invited to special issue of SIAM Journal on Computing.

15

Nearly Optimal Pricing Algorithms for Production Constrained and Laminar Bayesian Selection

, , , and

Manuscript

14

Budget Feasible Procurement Auctions

, , and

Oper. Res. 66

13

Graph Clustering using Effective Resistance

, , , and

ITCS 2018

12

Approximating the Largest Root and Applications to Interlacing Families

, , , and

SODA 2018

11

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

, , , and

SODA 2018

10

Robust Submodular Maximization: Offline and Online Algorithms

, , , , , and

Manuscript

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
Skype
nima.ahmadi.pour.anari
Homepage
https://nimaanari.com
Address
Gates Computer Science 484
353 Serra Mall
Stanford, CA 94305