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”.
    STOC 2017, to appear. (arXiv)
  • Aviad Rubinstein: "“Detecting communities is hard, and counting them is even harder”.
    ITCS 2017, to appear. (arXiv)
    Best Student Paper Award (co-winner)
  • 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)
    To appear in HALG 2017 (by invitation)
  • 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 Electrical Engineering and Computer Sciences
University of California at Berkeley

Last updated 2/17