×
Author ID: rubinstein.aviad Recent zbMATH articles by "Rubinstein, Aviad"
Published as: Rubinstein, Aviad
Homepage: https://cs.stanford.edu/~aviad/
External Links: dblp

Publications by Year

Citations contained in zbMATH Open

30 Publications have been cited 240 times in 208 Documents Cited by Year
The hunting of the SNARK. Zbl 1386.94066
Bitansky, Nir; Canetti, Ran; Chiesa, Alessandro; Goldwasser, Shafi; Lin, Huijia; Rubinstein, Aviad; Tromer, Eran
38
2017
An exponential speedup in parallel running time for submodular maximization without loss in approximation. Zbl 1431.68144
Balkanski, Eric; Rubinstein, Aviad; Singer, Yaron
24
2019
Beyond matroids: secretary problem and prophet inequality with general constraints. Zbl 1373.68457
Rubinstein, Aviad
17
2016
Combinatorial prophet inequalities. Zbl 1417.91251
Rubinstein, Aviad; Singla, Sahil
16
2017
Communication complexity of approximate Nash equilibria. Zbl 1369.68213
Babichenko, Yakov; Rubinstein, Aviad
14
2017
Inapproximability of Nash equilibrium. Zbl 1396.68060
Rubinstein, Aviad
14
2018
Inapproximability of Nash equilibrium. Zbl 1321.68320
Rubinstein, Aviad
13
2015
Converting online algorithms to local computation algorithms. Zbl 1272.68471
Mansour, Yishay; Rubinstein, Aviad; Vardi, Shai; Xie, Ning
11
2012
On simplex pivoting rules and complexity theory. Zbl 1418.90145
Adler, Ilan; Papadimitriou, Christos; Rubinstein, Aviad
10
2014
Hardness of approximate nearest neighbor search. Zbl 1428.68167
Rubinstein, Aviad
9
2018
Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds. Zbl 1462.68239
Abboud, Amir; Rubinstein, Aviad
8
2018
ETH hardness for densest-\(k\)-subgraph with perfect completeness. Zbl 1409.68125
Braverman, Mark; Ko, Young Kun; Rubinstein, Aviad; Weinstein, Omri
8
2017
The limitations of optimization from samples. Zbl 1369.68275
Balkanski, Eric; Rubinstein, Aviad; Singer, Yaron
7
2017
Can almost everybody be almost happy? Zbl 1335.91021
Babichenko, Yakov; Papadimitriou, Christos; Rubinstein, Aviad
5
2016
Computing exact minimum cuts without knowing the graph. Zbl 1462.68146
Rubinstein, Aviad; Schramm, Tselil; Weinberg, S. Matthew
5
2018
An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model. Zbl 1433.68590
Balkanski, Eric; Rubinstein, Aviad; Singer, Yaron
5
2019
Locally adaptive optimization: adaptive seeding for monotone submodular functions. Zbl 1423.90157
Badanidiyuru, Ashwinkumar; Papadimitriou, Christos; Rubinstein, Aviad; Seeman, Lior; Singer, Yaron
5
2016
Settling the complexity of Nash equilibrium in congestion games. Zbl 07765259
Babichenko, Yakov; Rubinstein, Aviad
4
2021
Honest signaling in zero-sum games is hard, and lying is even harder. Zbl 1441.68080
Rubinstein, Aviad
4
2017
Constant-factor approximation of near-linear edit distance in near-linear time. Zbl 07298280
Brakensiek, Joshua; Rubinstein, Aviad
3
2020
Reducing approximate longest common subsequence to approximate edit distance. Zbl 07304121
Rubinstein, Aviad; Song, Zhao
3
2020
Optimal single-choice prophet inequalities from samples. Zbl 07650408
Rubinstein, Aviad; Wang, Jack Z.; Weinberg, S. Matthew
3
2020
On the complexity of dynamic mechanism design. Zbl 1417.91247
Papadimitriou, Christos; Pierrakos, George; Psomas, Christos-Alexandros; Rubinstein, Aviad
3
2016
Sorting from noisier samples. Zbl 1409.68081
Rubinstein, Aviad; Vardi, Shai
3
2017
On the computational complexity of optimal simple mechanisms. Zbl 1334.68104
Rubinstein, Aviad
2
2016
Near-linear time insertion-deletion codes and \((1+\varepsilon)\)-approximating edit distance via indexing. Zbl 1433.68131
Haeupler, Bernhard; Rubinstein, Aviad; Shahrasbi, Amirbehshad
2
2019
Detecting communities is hard (and counting them is even harder). Zbl 1402.68106
Rubinstein, Aviad
1
2017
Near-optimal communication lower bounds for approximate Nash equilibria. Zbl 07453415
Göös, Mika; Rubinstein, Aviad
1
2021
Fine-grained complexity meets \(\mathrm{IP} = \mathrm{PSPACE}\). Zbl 1431.68045
Chen, Lijie; Goldwasser, Shafi; Lyu, Kaifeng; Rothblum, Guy N.; Rubinstein, Aviad
1
2019
Reductions in PPP. Zbl 1446.68067
Ban, Frank; Jain, Kamal; Papadimitriou, Christos H.; Psomas, Christos-Alexandros; Rubinstein, Aviad
1
2019
Settling the complexity of Nash equilibrium in congestion games. Zbl 07765259
Babichenko, Yakov; Rubinstein, Aviad
4
2021
Near-optimal communication lower bounds for approximate Nash equilibria. Zbl 07453415
Göös, Mika; Rubinstein, Aviad
1
2021
Constant-factor approximation of near-linear edit distance in near-linear time. Zbl 07298280
Brakensiek, Joshua; Rubinstein, Aviad
3
2020
Reducing approximate longest common subsequence to approximate edit distance. Zbl 07304121
Rubinstein, Aviad; Song, Zhao
3
2020
Optimal single-choice prophet inequalities from samples. Zbl 07650408
Rubinstein, Aviad; Wang, Jack Z.; Weinberg, S. Matthew
3
2020
An exponential speedup in parallel running time for submodular maximization without loss in approximation. Zbl 1431.68144
Balkanski, Eric; Rubinstein, Aviad; Singer, Yaron
24
2019
An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model. Zbl 1433.68590
Balkanski, Eric; Rubinstein, Aviad; Singer, Yaron
5
2019
Near-linear time insertion-deletion codes and \((1+\varepsilon)\)-approximating edit distance via indexing. Zbl 1433.68131
Haeupler, Bernhard; Rubinstein, Aviad; Shahrasbi, Amirbehshad
2
2019
Fine-grained complexity meets \(\mathrm{IP} = \mathrm{PSPACE}\). Zbl 1431.68045
Chen, Lijie; Goldwasser, Shafi; Lyu, Kaifeng; Rothblum, Guy N.; Rubinstein, Aviad
1
2019
Reductions in PPP. Zbl 1446.68067
Ban, Frank; Jain, Kamal; Papadimitriou, Christos H.; Psomas, Christos-Alexandros; Rubinstein, Aviad
1
2019
Inapproximability of Nash equilibrium. Zbl 1396.68060
Rubinstein, Aviad
14
2018
Hardness of approximate nearest neighbor search. Zbl 1428.68167
Rubinstein, Aviad
9
2018
Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds. Zbl 1462.68239
Abboud, Amir; Rubinstein, Aviad
8
2018
Computing exact minimum cuts without knowing the graph. Zbl 1462.68146
Rubinstein, Aviad; Schramm, Tselil; Weinberg, S. Matthew
5
2018
The hunting of the SNARK. Zbl 1386.94066
Bitansky, Nir; Canetti, Ran; Chiesa, Alessandro; Goldwasser, Shafi; Lin, Huijia; Rubinstein, Aviad; Tromer, Eran
38
2017
Combinatorial prophet inequalities. Zbl 1417.91251
Rubinstein, Aviad; Singla, Sahil
16
2017
Communication complexity of approximate Nash equilibria. Zbl 1369.68213
Babichenko, Yakov; Rubinstein, Aviad
14
2017
ETH hardness for densest-\(k\)-subgraph with perfect completeness. Zbl 1409.68125
Braverman, Mark; Ko, Young Kun; Rubinstein, Aviad; Weinstein, Omri
8
2017
The limitations of optimization from samples. Zbl 1369.68275
Balkanski, Eric; Rubinstein, Aviad; Singer, Yaron
7
2017
Honest signaling in zero-sum games is hard, and lying is even harder. Zbl 1441.68080
Rubinstein, Aviad
4
2017
Sorting from noisier samples. Zbl 1409.68081
Rubinstein, Aviad; Vardi, Shai
3
2017
Detecting communities is hard (and counting them is even harder). Zbl 1402.68106
Rubinstein, Aviad
1
2017
Beyond matroids: secretary problem and prophet inequality with general constraints. Zbl 1373.68457
Rubinstein, Aviad
17
2016
Can almost everybody be almost happy? Zbl 1335.91021
Babichenko, Yakov; Papadimitriou, Christos; Rubinstein, Aviad
5
2016
Locally adaptive optimization: adaptive seeding for monotone submodular functions. Zbl 1423.90157
Badanidiyuru, Ashwinkumar; Papadimitriou, Christos; Rubinstein, Aviad; Seeman, Lior; Singer, Yaron
5
2016
On the complexity of dynamic mechanism design. Zbl 1417.91247
Papadimitriou, Christos; Pierrakos, George; Psomas, Christos-Alexandros; Rubinstein, Aviad
3
2016
On the computational complexity of optimal simple mechanisms. Zbl 1334.68104
Rubinstein, Aviad
2
2016
Inapproximability of Nash equilibrium. Zbl 1321.68320
Rubinstein, Aviad
13
2015
On simplex pivoting rules and complexity theory. Zbl 1418.90145
Adler, Ilan; Papadimitriou, Christos; Rubinstein, Aviad
10
2014
Converting online algorithms to local computation algorithms. Zbl 1272.68471
Mansour, Yishay; Rubinstein, Aviad; Vardi, Shai; Xie, Ning
11
2012
all top 5

Cited by 406 Authors

8 Goldberg, Paul W.
7 Fearnley, John
7 Manurangsi, Pasin
7 Rubinstein, Aviad
7 Xu, Dachuan
7 Zhou, Yang
6 Deligkas, Argyrios
6 Göös, Mika
6 Guo, Longkun
6 Paneth, Omer
6 Tan, Jingjing
5 Bitansky, Nir
5 Ishai, Yuval
5 Li, Min
5 Rubinfeld, Ronitt
4 Canetti, Ran
4 Feldman, Michal
4 Hoefer, Martin
4 Hollender, Alexandros
4 Holmgren, Justin
4 Karthik, C. S.
4 Levi, Reut
4 Liu, Qian
4 Savani, Rahul
4 Tang, Shaojie
4 Vaikuntanathan, Vinod
4 Wu, David J.
3 Bishnu, Arijit
3 Boyle, Elette
3 D’Angelo, Gianlorenzo
3 De Loera, Jesús A.
3 Dütting, Paul
3 Filos-Ratsikas, Aris
3 Ghosh, Arijit
3 Huang, Chien-Chung
3 Jain, Abhishek
3 Kakimura, Naonori
3 Kiyoshima, Susumu
3 Laekhanukit, Bundit
3 Leucci, Stefano
3 Liu, Chih-Hung
3 Mishra, Gopinath
3 Ostrovsky, Rafail
3 Pass, Rafael
3 Patt-Shamir, Boaz
3 Ron, Dana
3 Smorodinsky, Rann
3 Spirakis, Paul G.
3 Tang, Zhihao Gavin
3 Vardi, Shai
3 Waters, Brent
3 Watson, Thomas
2 Babichenko, Yakov
2 Bajpai, Swapnam
2 Balkanski, Eric
2 Barman, Siddharth
2 Bringmann, Karl
2 Castiglioni, Matteo
2 Celli, Andrea
2 Cellinese, Francesco
2 Correa, José R.
2 Cui, Min
2 David, Roee
2 Devanur, Nikhil R.
2 Fasoulakis, Michail
2 Feige, Uriel
2 Freitag, Cody R.
2 Garg, Sanjam
2 Gatti, Nicola
2 Geissmann, Barbara
2 Goel, Aarushi
2 Gravin, Nick
2 Hahn, Niklas
2 Kalai, Yael T.
2 Karlin, Anna R.
2 Katzman, Matthew J.
2 Keßelheim, Thomas
2 Khurana, Dakshita
2 Kolay, Sudeshna
2 Krishan, Vaibhav
2 Kush, Deepanshu
2 Lazos, Philip
2 Li, Meixia
2 Limaye, Nutan
2 Liu, Bin
2 Lucier, Brendan
2 Marmolejo Cossío, Francisco J.
2 Melissourgos, Themistoklis
2 Monaco, Gianpiero
2 Nanongkai, Danupon
2 Penna, Paolo
2 Pitassi, Toniann
2 Saurabh, Saket
2 Singer, Yaron
2 Singla, Sahil
2 Sivan, Balasubramanian
2 Srinivasan, Srikanth
2 Talgam-Cohen, Inbal
2 Velaj, Yllka
2 Verdugo, Víctor
...and 306 more Authors

Citations by Year