Aviad Rubinstein

I am a final year Computer Science PhD candidate at UC Berkeley, advised by Christos Papadimitriou.
My research looks, through the Lens of Theoretical Computer Science, at a variety of problems from the studies of Evolution, Statistics, Stopping Theory, and Game Theory. Two lines of works that I am particularly thrilled about are: (1) understanding the terrain of computational complexity between P and NP, and (2) understanding mechanism design subject to simplicity constraints.

During the last few summers, I interned at Microsoft Research labs in Hertzeliyah (Israel), Beijing, and New England.
Prior to coming to Berkeley I completed my MSc at Tel-Aviv University with Muli Safra.

My research is supported in part by a MSR PhD Fellowship.

PC member: EC 2016, ITCS 2017.

      aviad [at]eecs.berkeley.edu

Selected publications (there are more here)

  • Yakov Babichenko, Aviad Rubinstein: “Communication complexity of approximate Nash equilibria” (arXiv)
    Update: Our new version (9/2016) extends the lower bound to randomized communication!
  • Mark Braverman, Young Kun Ko, Aviad Rubinstein, Omri Weinstein: “ETH Hardness for Densest-k-Subgraph with Perfect Completeness”.
    SODA 2017, to appear. (ECCC)
  • 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)
  • 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
  • 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 Electrical Engineering and Computer Sciences
University of California at Berkeley

Last updated 10/16