Edit Profile (opens in new tab) Rubinstein, Aviad Co-Author Distance Author ID: rubinstein.aviad Published as: Rubinstein, Aviad Homepage: https://cs.stanford.edu/~aviad/ External Links: dblp Documents Indexed: 42 Publications since 2007, including 1 Additional arXiv Preprint Co-Authors: 47 Co-Authors with 35 Joint Publications 1,386 Co-Co-Authors all top 5 Co-Authors 7 single-authored 7 Papadimitriou, Christos Harilaos 6 Singer, Yaron 5 Balkanski, Eric 4 Babichenko, Yakov 3 Weinberg, Seth Matthew 2 Goldwasser, Shafi 2 Göös, Mika 2 Mansour, Yishay 2 Pierrakos, George 2 Psomas, Christos-Alexandros 2 Vardi, Shai 2 Zhao, Junyao 1 Abboud, Amir 1 Adler, Ilan 1 Badanidiyuru, Ashwinkumar 1 Ban, Frank 1 Bitansky, Nir 1 Brakensiek, Joshua 1 Braverman, Mark 1 Canetti, Ran 1 Chen, Lijie 1 Chiesa, Alessandro 1 Etessami, Kousha 1 Goldenberg, Elazar 1 Haeupler, Bernhard 1 Kun-Ko, Young 1 Lin, Huijia 1 Lyu, Kaifeng 1 Psomas, Alexandros 1 Rothblum, Guy N. 1 Rubinstein, Jacob 1 Safra, Muli 1 Saha, Barna 1 Saxena, Raghuvansh R. 1 Schramm, Tselil 1 Seeman, Lior 1 Shahrasbi, Amirbehshad 1 Singla, Sahil 1 Song, Zhao 1 Tennenholtz, Moshe 1 Thomas, Clayton J. 1 Tromer, Eran 1 Wang, Jack Z. 1 Weinstein, Omri 1 Wolansky, Gershon 1 Xie, Ning 1 Yannakakis, Mihalis all top 5 Serials 3 SIAM Journal on Computing 2 Games and Economic Behavior 1 Information Processing Letters 1 Operations Research 1 Journal of Cryptology 1 SIAM Review 1 Journal of the ACM all top 5 Fields 36 Computer science (68-XX) 15 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 6 Operations research, mathematical programming (90-XX) 3 Combinatorics (05-XX) 1 Potential theory (31-XX) 1 Partial differential equations (35-XX) 1 Probability theory and stochastic processes (60-XX) 1 Numerical analysis (65-XX) 1 Information and communication theory, circuits (94-XX) Publications by Year all cited Publications top 5 cited Publications 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 cited Publications top 5 cited Publications 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 all top 5 Cited in 40 Serials 21 SIAM Journal on Computing 10 Theoretical Computer Science 9 Algorithmica 7 Mathematics of Operations Research 6 Journal of Computer and System Sciences 6 Games and Economic Behavior 5 Theory of Computing Systems 4 SIAM Journal on Discrete Mathematics 4 Journal of Cryptology 4 Journal of Combinatorial Optimization 3 Information Processing Letters 3 Information and Computation 2 Artificial Intelligence 2 Operations Research 2 Operations Research Letters 2 Asia-Pacific Journal of Operational Research 2 The Journal of Artificial Intelligence Research (JAIR) 2 Data Mining and Knowledge Discovery 1 Applied Mathematics and Computation 1 Applied Mathematics and Optimization 1 Journal of Economic Theory 1 Journal of Optimization Theory and Applications 1 Networks 1 Combinatorica 1 Random Structures & Algorithms 1 SIAM Journal on Optimization 1 Cybernetics and Systems Analysis 1 Journal of the ACM 1 Chaos 1 Journal of Machine Learning Research (JMLR) 1 Journal of Industrial and Management Optimization 1 Optimization Letters 1 Logical Methods in Computer Science 1 Algorithms 1 ACM Transactions on Algorithms 1 Games 1 SIAM Journal on Applied Algebra and Geometry 1 Prikladnaya Diskretnaya Matematika 1 SN Operations Research Forum 1 CGT. Computing in Geometry and Topology all top 5 Cited in 16 Fields 141 Computer science (68-XX) 55 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 48 Operations research, mathematical programming (90-XX) 39 Information and communication theory, circuits (94-XX) 25 Combinatorics (05-XX) 10 Probability theory and stochastic processes (60-XX) 7 Statistics (62-XX) 6 Convex and discrete geometry (52-XX) 2 Algebraic topology (55-XX) 1 Category theory; homological algebra (18-XX) 1 Measure and integration (28-XX) 1 Dynamical systems and ergodic theory (37-XX) 1 Geometry (51-XX) 1 Global analysis, analysis on manifolds (58-XX) 1 Numerical analysis (65-XX) 1 Systems theory; control (93-XX) Citations by Year