I am an assistant professor in Computer Science at Stanford.
Teaching
- Fall 2018- Design and Analysis of Algorithms (CS161)
- Spring 2019- Topics in Intractability: Unfulfilled Algorithmic Fantasies (CS354)
Research
Below are some buzzwords and select publications.
(See dblp for more buzzwords and more publications.)
Approximation: algorithms vs hardness.
When and why can we come up with algorithms for some problems, but others are intractable - even when we're willing to settle for approximate solutions?
- Amir Abboud, Aviad Rubinstein, Ryan Williams: "Distributed PCP Theorems for Hardness of Approximation in P".
FOCS 2017 (arXiv)
Invited talk at HALG 2018.
In this paper (STOC 2018), we obtained some stronger results using AG codes.
Optimizing without knowing the input
Some of the coolest questions in our field are about optimization over input
that is kept by selfish agents ("mechanism design"),
depends on future events ("online algorithms"),
or has to be reconstructed from noisy samples ("machine learning").
- Eric Balkanski, Aviad Rubinstein, Yaron Singer: "The Limitations of Optimization from Samples".
STOC 2017 (arXiv)
See also this related paper from NIPS 2016.
- Aviad Rubinstein: “Beyond matroids: secretary problem and prophet inequality with general constraints”
STOC 2016 (arXiv)
- Christos Papadimitriou, George Pierrakos, Christos-Alexandros Psomas, Aviad Rubinstein: “The Intractability of Dynamic Mechanism Design”
SODA 2016 (arXiv)
Invited to special issue of GEB.
Complexity of Nash equilibrium
This is a favorite meta-question in the intersection of the previous two themes.
- Yakov Babichenko, Aviad Rubinstein: “Communication complexity of approximate Nash equilibria”.
STOC 2017 (arXiv)
Invited to special issue of GEB.
See also this really nice Quanta Magazine article about our work,
by Erica Klarreich.
See also this paper with Mika Goos (FOCS 2018) where we obtain near-tight bounds.
- Aviad Rubinstein: “Settling the complexity of computing approximate two-player Nash equilibria”
FOCS 2016. (arXiv)
Best Paper Award (co-winner)
Machtey Best Student Paper Award (co-winner)
Invited talk in HALG 2017
See also letter in SIGecom Exchanges.
Service
- Manolis Zampetakis and I are organizing a workshop in FOCS 2018 on total search problems.
- PC: WINE 2017,2018, SODA 2018, ITCS 2017,2019, STOC 2019, ESA 2019.
- Junior PC / Reviewer: EC 2016-18, NIPS 2018.
email:
aviad [at]cs.stanford.edu
|
