Nima Anari

Nima Anari

Computer Science Department, Stanford University

I am a researcher in the Computer Science Theory Group at Stanford University. I am also at the Simons Institute for the Theory of Computing during spring 2019 as a Microsoft Research Fellow for the Geometry of Polynomials program.

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

22

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

and

Manuscript

21

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

, , , and

Manuscript

20

A Tight Analysis of Bethe Approximation for Permanent

and

FOCS 2019

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.

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

Invited to special issue of SIAM Journal on Computing.

13

Budget Feasible Procurement Auctions

, , and

Oper. Res. 66

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