Aviad Rubinstein

In Fall 2018 I will join the Stanford Computer Science department as an Assistant Professor. Currently (2017-18) I'm a Rabin Postdoc at Harvard. Prior to coming to Harvard, I did my PhD at UC Berkeley, advised by Christos Papadimitriou. Before that, I completed my MSc at Tel-Aviv University with Muli Safra.

My research looks, through the Lens of Theoretical Computer Science, at a variety of problems from Evolution, Statistics, Stopping Theory, and Game Theory.
My favorite questions are when and why some problems are intractable - even when we're willing to settle for approximate solutions: At Berkeley I wrote a thesis about hardness of approximation between P and NP. More recently, I've also been interested in understanding hardness of approximation inside P.

I served on some PCs recently: EC 2016-17, ITCS 2017, WINE 2017, SODA 2018.

      aviad [at]cs.stanford.edu

Selected publications (see dblp for more...)

  • Amir Abboud, Aviad Rubinstein, Ryan Williams: “Distributed PCP Theorems for Hardness of Approximation in P”.
    FOCS 2017, to appear.
    Note: the FOCS proceedings version contains a bug :-( Please refer to the arXiv version!
  • Yakov Babichenko, Aviad Rubinstein: “Communication complexity of approximate Nash equilibria”.
    STOC 2017: 878-889. (arXiv)
    See also this really nice Quanta Magazine article about our work, by Erica Klarreich.
  • Aviad Rubinstein: “Settling the complexity of computing approximate two-player Nash equilibria”
    FOCS 2016, to appear. (arXiv)
    Best Paper Award (co-winner)
    Machtey Best Student Paper Award (co-winner)
    Appeared in HALG 2017 (by invitation)
    See also letter in SIGecom Exchanges.
  • Aviad Rubinstein: “Beyond matroids: secretary problem and prophet inequality with general constraints”
    STOC 2016: 324-332. (arXiv)
  • Aviad Rubinstein: “On the Computational Complexity of Optimal Simple Mechanisms”
    ITCS 2016: 21-28. (arXiv)
    Best Student Paper Award
    See also letter in SIGecom Exchanges.
  • Christos Papadimitriou, George Pierrakos, Christos-Alexandros Psomas, Aviad Rubinstein: “The Intractability of Dynamic Mechanism Design”
    SODA 2016: 1458-1475. (arXiv)
  • Aviad Rubinstein: “Inapproximability of Nash equilibrium”
    STOC 2015: 409-418. (arXiv)
    Danny Lewin Best Student Paper Award
    Accepted to special issue of SICOMP for STOC 2015 (invited paper)
  • Abraham Othman, Christos Papadimitriou, Aviad Rubinstein: "The Complexity of Fairness through Equilibrium"
    ACM Transactions on Economics and Computation 4(4): 20 (arXiv)
    Special issue on EC'14 (invited paper)

Department of Computer Sciences
Stanford University

Last updated 11/17