Nima Anari

Nima Anari

Research Fellow
Simons Institute

I am a research fellow at Simons Institute for the Theory of Computing for the program on Bridging Continuous and Discrete Optimization. After this program, in January 2018, I will start at Stanford's Computer Science Department as a research engineer.

Previously I was a postdoctoral researcher at Stanford MS&E, hosted by Amin Saberi. 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 specific topics that I have worked on include:

  • Applications of Polynomials in Algorithms, Combinatorics, and Probability
  • (Algorithmic) Spectral Graph Theory
  • Approximation Algorithms
  • Algorithmic Game Theory and Mechanism Design

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

Papers

Planar Graph Perfect Matching is in NC

and

Manuscript

Graph Clustering using Effective Resistance

, , , and

ITCS 2018

Approximating the Largest Root and Applications to Interlacing Families

, , , and

SODA 2018

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

, , , and

SODA 2018

Robust Submodular Maximization: Offline and Online Algorithms

, , , , , and

Manuscript

Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices

, , , and

FOCS 2017

A Generalization of Permanent Inequalities and Applications in Counting and Optimization

and

STOC 2017

Nash Social Welfare, Matrix Permanent, and Stable Polynomials

, , , and

ITCS 2017

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

, , and

COLT 2016

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

and

FOCS 2015

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

and

Manuscript

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

, , and

FOCS 2014

Euclidean Movement Minimization

, , , and

CCCG 2011
J. Comb. Optim. 32

Equilibrium Pricing with Positive Externalities

, , , , , , and

WINE 2010
Theor. Comput. Sci. 476

Contact

Email
anari@berkeley.edu
Phone
+1 (510) 520-7774
Skype
nima.ahmadi.pour.anari
Homepage
https://nimaanari.com
Address
Calvin Laboratory #314
Berkeley, CA 94720