Aviad Rubinstein

I am a Computer Science PhD student at UC Berkeley, advised by Christos Papadimitriou. In general, I am interested in Theory of Computer Science (and its applications). Lately, for example, I have been particularly curious about the connection between different bilinear optimization problems such as Nash equilibrium, Densest k-Subgraph, and Sparse PCA. Prior to coming to Berkeley I completed my MSc at Tel-Aviv University with Muli Safra.

I thank Microsoft Research for the MSR PhD Fellowship, as well as wonderful summer internships at MSR Hertzeliyah (2013, with Yishay Mansour and Moshe Tennenholtz), MSR Beijing (2014, with Wei Chen), and MSR New England (2015, with Nicole Immorlica).

      aviad [at]eecs.berkeley.edu

Selected publications (more)

  • Mark Braverman, Young Kun Ko, Aviad Rubinstein, Omri Weinstein: “ETH Hardness for Densest-k-Subgraph with Perfect Completeness” (ECCC)
  • Yakov Babichenko, Christos Papadimitriou, Aviad Rubinstein: “Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash” (arXiv)
  • Aviad Rubinstein: “Inapproximability of Nash equilibrium”
    STOC 2015, to appear. (ECCC)
  • Christos Papadimitriou, George Pierrakos, Christos-Alexandros Psomas, Aviad Rubinstein: “The Intractability of Dynamic Mechanism Design” (arXiv)
  • Abraham Othman, Christos Papadimitriou, Aviad Rubinstein: "The Complexity of Fairness through Equilibrium"
    EC 2014: 209-226. (arXiv)

Department of Electrical Engineering and Computer Sciences
University of California at Berkeley

Last updated 9/14