The hunting of the SNARK N Bitansky, R Canetti, A Chiesa, S Goldwasser, H Lin, A Rubinstein, ... Journal of Cryptology 30 (4), 989-1066, 2017 | 188 | 2017 |
Settling the complexity of computing approximate two-player Nash equilibria A Rubinstein ACM SIGecom Exchanges 15 (2), 45-49, 2017 | 151 | 2017 |
Simple mechanisms for a subadditive buyer and applications to revenue monotonicity A Rubinstein, SM Weinberg ACM Transactions on Economics and Computation (TEAC) 6 (3-4), 1-25, 2018 | 142 | 2018 |
Inapproximability of Nash equilibrium A Rubinstein Proceedings of the forty-seventh annual ACM symposium on Theory of computing …, 2015 | 134 | 2015 |
Beyond matroids: Secretary problem and prophet inequality with general constraints A Rubinstein Proceedings of the forty-eighth annual ACM symposium on Theory of Computing …, 2016 | 114 | 2016 |
Hardness of approximate nearest neighbor search A Rubinstein Proceedings of the 50th annual ACM SIGACT symposium on theory of computing …, 2018 | 108 | 2018 |
Distributed PCP theorems for hardness of approximation in P A Abboud, A Rubinstein, R Williams 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 25-36, 2017 | 103 | 2017 |
Delegation of computation without rejection problem from designated verifier CS-proofs S Goldwasser, H Lin, A Rubinstein Cryptology ePrint Archive, 2011 | 103 | 2011 |
Combinatorial prophet inequalities A Rubinstein, S Singla Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete …, 2017 | 100 | 2017 |
An exponential speedup in parallel running time for submodular maximization without loss in approximation E Balkanski, A Rubinstein, Y Singer Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete …, 2019 | 99 | 2019 |
Communication complexity of approximate Nash equilibria Y Babichenko, A Rubinstein Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing …, 2017 | 79 | 2017 |
Optimal single-choice prophet inequalities from samples A Rubinstein, JZ Wang, SM Weinberg arXiv preprint arXiv:1911.07945, 2019 | 76 | 2019 |
The complexity of fairness through equilibrium A Othman, C Papadimitriou, A Rubinstein ACM Transactions on Economics and Computation (TEAC) 4 (4), 1-19, 2016 | 73 | 2016 |
Converting online algorithms to local computation algorithms Y Mansour, A Rubinstein, S Vardi, N Xie Automata, Languages, and Programming: 39th International Colloquium, ICALP …, 2012 | 70 | 2012 |
The limitations of optimization from samples E Balkanski, A Rubinstein, Y Singer Proceedings of the 49th annual acm sigact symposium on theory of computing …, 2017 | 64 | 2017 |
Computing exact minimum cuts without knowing the graph A Rubinstein, T Schramm, SM Weinberg arXiv preprint arXiv:1711.03165, 2017 | 61 | 2017 |
ETH Hardness for Densest-k-Subgraph with Perfect Completeness M Braverman, YK Ko, A Rubinstein, O Weinstein Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete …, 2017 | 56 | 2017 |
On the complexity of dynamic mechanism design C Papadimitriou, G Pierrakos, CA Psomas, A Rubinstein Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete …, 2016 | 53 | 2016 |
Constant-factor approximation of near-linear edit distance in near-linear time J Brakensiek, A Rubinstein Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing …, 2020 | 51 | 2020 |
The power of optimization from samples E Balkanski, A Rubinstein, Y Singer Advances in Neural Information Processing Systems 29, 2016 | 49 | 2016 |