Hardness of Approximation between P and NP
- Aviad Rubinstein: "ETH-Hardness for Symmetric Signaling in Zero-Sum Games".
- 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)
- Mark Braverman, Young Kun Ko, Aviad Rubinstein, Omri Weinstein: “ETH Hardness for Densest-k-Subgraph with Perfect Completeness”.
SODA 2017: 1326-1341. (ECCC)
- Aviad Rubinstein: “Settling the complexity of computing approximate two-player Nash equilibria”
FOCS 2016, 258-265. (arXiv)
Best Paper Award (co-winner)
Machtey Best Student Paper Award (co-winner)
To appear in HALG 2017 (invited paper)
- Yakov Babichenko, Christos H. Papadimitriou, Aviad Rubinstein: "Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash".
ITCS 2016: 1-9. (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)
Simple Mechanism Design
- Aviad Rubinstein: “On the Computational Complexity of Optimal Simple Mechanisms”
ITCS 2016: 21-28. (arXiv)
Best Student Paper Award
- Christos Papadimitriou, George Pierrakos, Christos-Alexandros Psomas, Aviad Rubinstein: “The Intractability of Dynamic Mechanism Design”
SODA 2016: 1458-1475. (arXiv)
Aviad Rubinstein, S. Matthew Weinberg: “Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity”.
EC 2015: 377-394. (arXiv)
Learning / Statistics
Eric Balkanski, Aviad Rubinstein, Yaron Singer: "The Limitations of Optimization from Samples".
STOC 2017, to appear. (arXiv)
- Aviad Rubinstein, Shai Vardi: "Sorting from Noisier Samples".
SODA 2017: 960-972.
- Eric Balkanski, Aviad Rubinstein, Yaron Singer: "The Power of Optimization from Samples".
NIPS 2016: 4017-4025.
- Siu On Chan, Dimitris Papailiopoulos, Aviad Rubinstein: "On the Approximability of Sparse PCA".
COLT 2016: 623-646. (arXiv)
- Yishay Mansour, Aviad Rubinstein, Moshe Tennenholtz: “Robust Bayesian Inference”
SODA 2015: 449-460.
- Aviad Rubinstein, Sahil Singla: "Combinatorial Prophet Inequalities".
SODA 2017: 1671-1687. (arXiv)
- Aviad Rubinstein: “Beyond matroids: secretary problem and prophet inequality with general constraints".
STOC 2016: 324-332. (arXiv)
Influence Maximization in Social Networks
- Ashwinkumar Badanidiyuru, Christos H. Papadimitriou, Aviad Rubinstein, Lior Seeman, Yaron Singer:
"Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions".
SODA 2016: 414-429. (arXiv)
Wei Chen, Fu Li, Tian Lin, Aviad Rubinstein: “Combining Traditional Marketing and Viral Marketing with Amphibious Influence Maximization”.
EC 2015, 779-796. (arXiv)
Aviad Rubinstein, Lior Seeman, Yaron Singer: “Adaptive Seeding with Knapsack Constraints”.
EC 2015, 797-814.
Everything else (Biology, Physics, Crypto, etc.)
- Adi Livnat, Christos Papadimitriou, Aviad Rubinstein, Gregory Valiant, Andrew Wan: "Satisfiability and Evolution"
FOCS 2014: 524-530. (arXiv)
- Nir Bitansky, Ran Canetti, Alessandro Chiesa, Shafi Goldwasser, Huijia Lin, Aviad Rubinstein, Eran Tromer: “The Hunting of the SNARK”
Journal of Cryptology, to appear. (ePrint)
- Muli Safra, Aviad Rubinstein: “Boolean functions whose Fourier transform is concentrated on pairwise disjoint subsets of the input”
Last updated 2/17