default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDAviad Rubinstein
Person information
- affiliation: Stanford University
- affiliation: Harvard University
- affiliation (PhD): University of California at Berkeley
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
Books and Theses
- 2019
[b2]Aviad Rubinstein:
Hardness of Approximation Between P and NP. ACM Books 24, ACM 2019, ISBN 978-1-94748-723-9, pp. 1-320- 2017
- [b1]Aviad Rubinstein:
Hardness of Approximation Between P and NP. University of California at Berkeley, USA, 2017
Journal Articles
- 2023
- [j15]Mika Göös, Aviad Rubinstein:
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria. SIAM J. Comput. 52(6): S18-316 (2023) - 2022
- [j14]Yakov Babichenko
, Aviad Rubinstein:
Communication complexity of approximate Nash equilibria. Games Econ. Behav. 134: 376-398 (2022) - [j13]Christos H. Papadimitriou, George Pierrakos, Alexandros Psomas, Aviad Rubinstein:
On the complexity of dynamic mechanism design. Games Econ. Behav. 134: 399-427 (2022) - [j12]Eric Balkanski, Aviad Rubinstein, Yaron Singer:
An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model. Oper. Res. 70(5): 2967-2981 (2022) - [j11]Eric Balkanski, Aviad Rubinstein, Yaron Singer:
The Limitations of Optimization from Samples. J. ACM 69(3): 21:1-21:33 (2022) - 2021
- [j10]Aviad Rubinstein, Junyao Zhao:
The randomized communication complexity of revenue maximization. SIGecom Exch. 19(2): 75-83 (2021) - 2019
- [j9]Frank Ban, Kamal Jain, Christos H. Papadimitriou, Christos-Alexandros Psomas, Aviad Rubinstein:
Reductions in PPP. Inf. Process. Lett. 145: 48-52 (2019) - [j8]Aviad Rubinstein, Virginia Vassilevska Williams:
SETH vs Approximation. SIGACT News 50(4): 57-76 (2019) - 2018
- [j7]Aviad Rubinstein:
Inapproximability of Nash Equilibrium. SIAM J. Comput. 47(3): 917-959 (2018) - [j6]Aviad Rubinstein, S. Matthew Weinberg:
Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity. ACM Trans. Economics and Comput. 6(3-4): 19:1-19:25 (2018) - 2017
- [j5]Nir Bitansky, Ran Canetti, Alessandro Chiesa, Shafi Goldwasser, Huijia Lin, Aviad Rubinstein, Eran Tromer:
The Hunting of the SNARK. J. Cryptol. 30(4): 989-1066 (2017) - [j4]Aviad Rubinstein:
Settling the complexity of computing approximate two-player Nash equilibria. SIGecom Exch. 15(2): 45-49 (2017) - 2016
- [j3]Abraham Othman, Christos H. Papadimitriou, Aviad Rubinstein:
The Complexity of Fairness Through Equilibrium. ACM Trans. Economics and Comput. 4(4): 20:1-20:19 (2016) - 2015
- [j2]Aviad Rubinstein:
The complexity of simplicity in mechanism design. SIGecom Exch. 14(2): 41-43 (2015) - 2007
- [j1]Aviad Rubinstein, Jacob Rubinstein, Gershon Wolansky:
Determining Sets for the Discrete Laplacian. SIAM Rev. 49(2): 315-324 (2007)
Conference and Workshop Papers
- 2024
- [c68]Binghui Peng, Aviad Rubinstein:
The complexity of approximate (coarse) correlated equilibrium for incomplete information games. COLT 2024: 4158-4184 - [c67]Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi:
Sublinear Algorithms for TSP via Path Covers. ICALP 2024: 19:1-19:16 - [c66]Lorenzo Beretta, Aviad Rubinstein:
Approximate Earth Mover's Distance in Truly-Subquadratic Time. STOC 2024: 47-58 - [c65]Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein:
Approximating Maximum Matching Requires Almost Quadratic Time. STOC 2024: 444-454 - [c64]Shahar Dobzinski, Wenzheng Li, Aviad Rubinstein, Jan Vondrák:
A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations. STOC 2024: 467-478 - [c63]Nima Anari, Ruiquan Gao, Aviad Rubinstein:
Parallel Sampling via Counting. STOC 2024: 537-548 - [c62]Binghui Peng, Aviad Rubinstein:
Fast Swap Regret Minimization and Applications to Approximate Correlated Equilibria. STOC 2024: 1223-1234 - 2023
- [c61]Alexandros Hollender, Aviad Rubinstein:
Envy-Free Cake-Cutting for Four Agents. FOCS 2023: 113-122 - [c60]Binghui Peng, Aviad Rubinstein:
Near Optimal Memory-Regret Tradeoff for Online Learning. FOCS 2023: 1171-1194 - [c59]Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein:
Local Computation Algorithms for Maximum Matching: New Lower Bounds. FOCS 2023: 2322-2335 - [c58]Aviad Rubinstein, Junyao Zhao:
Beyond Worst-Case Budget-Feasible Mechanism Design. ITCS 2023: 93:1-93:22 - [c57]Eric Budish, Ruiquan Gao, Abraham Othman, Aviad Rubinstein, Qianfan Zhang:
Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI). EC 2023: 337-368 - [c56]Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi:
Beating Greedy Matching in Sublinear Time. SODA 2023: 3900-3945 - [c55]Binghui Peng, Aviad Rubinstein:
Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window). SOSA 2023: 261-271 - [c54]Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein:
Sublinear Time Algorithms and Complexity of Approximate Maximum Matching. STOC 2023: 267-280 - 2022
- [c53]Aviad Rubinstein, Junyao Zhao:
Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation. ICALP 2022: 106:1-106:17 - [c52]Aviad Rubinstein, Junyao Zhao:
Budget-Smoothed Analysis for Submodular Maximization. ITCS 2022: 113:1-113:23 - 2021
- [c51]Kuan Cheng, Alireza Farhadi, MohammadTaghi Hajiaghayi, Zhengzhong Jin, Xin Li, Aviad Rubinstein, Saeed Seddighin, Yu Zheng:
Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence. ICALP 2021: 54:1-54:20 - [c50]Pasin Manurangsi, Aviad Rubinstein, Tselil Schramm:
The Strongish Planted Clique Hypothesis and Its Consequences. ITCS 2021: 10:1-10:21 - [c49]Paul Liu, Aviad Rubinstein, Jan Vondrák, Junyao Zhao:
Cardinality constrained submodular maximization for random streams. NeurIPS 2021: 6491-6502 - [c48]Aviad Rubinstein, Junyao Zhao:
The randomized communication complexity of randomized auctions. STOC 2021: 882-895 - [c47]Aviad Rubinstein, Raghuvansh R. Saxena, Clayton Thomas, S. Matthew Weinberg, Junyao Zhao:
Exponential communication separations between notions of selfishness. STOC 2021: 947-960 - [c46]Yakov Babichenko, Aviad Rubinstein:
Settling the complexity of Nash equilibrium in congestion games. STOC 2021: 1426-1437 - 2020
- [c45]Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, Aviad Rubinstein:
Smoothed Complexity of 2-player Nash Equilibria. FOCS 2020: 271-282 - [c44]Yakov Babichenko, Aviad Rubinstein:
Communication complexity of Nash equilibrium in potential games (extended abstract). FOCS 2020: 1439-1445 - [c43]Kousha Etessami, Christos H. Papadimitriou, Aviad Rubinstein, Mihalis Yannakakis:
Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria. ITCS 2020: 18:1-18:19 - [c42]Aviad Rubinstein, Jack Z. Wang, S. Matthew Weinberg:
Optimal Single-Choice Prophet Inequalities from Samples. ITCS 2020: 60:1-60:10 - [c41]Aranyak Mehta, Uri Nadav, Alexandros Psomas, Aviad Rubinstein:
Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics. NeurIPS 2020 - [c40]Aviad Rubinstein, Zhao Song:
Reducing approximate Longest Common Subsequence to approximate Edit Distance. SODA 2020: 1591-1600 - [c39]Elazar Goldenberg, Aviad Rubinstein, Barna Saha:
Does preprocessing help in fast sequence comparisons? STOC 2020: 657-670 - [c38]Joshua Brakensiek, Aviad Rubinstein:
Constant-factor approximation of near-linear edit distance in near-linear time. STOC 2020: 685-698 - 2019
- [c37]Aviad Rubinstein, Saeed Seddighin, Zhao Song, Xiaorui Sun:
Approximation Algorithms for LCS and LIS with Truly Improved Running Times. FOCS 2019: 1121-1145 - [c36]Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, Aviad Rubinstein:
Fine-grained Complexity Meets IP = PSPACE. SODA 2019: 1-20 - [c35]Eric Balkanski, Aviad Rubinstein, Yaron Singer:
An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation. SODA 2019: 283-302 - [c34]Eric Balkanski, Aviad Rubinstein, Yaron Singer:
An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model. STOC 2019: 66-77 - [c33]Bernhard Haeupler, Aviad Rubinstein, Amirbehshad Shahrasbi:
Near-linear time insertion-deletion codes and (1+ε)-approximating edit distance via indexing. STOC 2019: 697-708 - 2018
- [c32]Mika Göös, Aviad Rubinstein:
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria. FOCS 2018: 397-403 - [c31]Amir Abboud, Aviad Rubinstein:
Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds. ITCS 2018: 35:1-35:14 - [c30]Aviad Rubinstein, Tselil Schramm, S. Matthew Weinberg:
Computing Exact Minimum Cuts Without Knowing the Graph. ITCS 2018: 39:1-39:16 - [c29]Moshe Babaioff, Noam Nisan, Aviad Rubinstein:
Optimal Deterministic Mechanisms for an Additive Buyer. EC 2018: 429 - [c28]Michal Feldman, Ophir Friedler, Aviad Rubinstein:
99% Revenue via Enhanced Competition. EC 2018: 443-460 - [c27]Aviad Rubinstein:
Hardness of approximate nearest neighbor search. STOC 2018: 1260-1268 - 2017
- [c26]Pasin Manurangsi, Aviad Rubinstein:
Inapproximability of VC Dimension and Littlestone's Dimension. COLT 2017: 1432-1460 - [c25]Amir Abboud, Aviad Rubinstein, R. Ryan Williams:
Distributed PCP Theorems for Hardness of Approximation in P. FOCS 2017: 25-36 - [c24]Aviad Rubinstein:
Honest Signaling in Zero-Sum Games Is Hard, and Lying Is Even Harder. ICALP 2017: 77:1-77:13 - [c23]Aviad Rubinstein:
Detecting communities is Hard (And Counting Them is Even Harder). ITCS 2017: 42:1-42:13 - [c22]Aviad Rubinstein, Shai Vardi:
Sorting from Noisier Samples. SODA 2017: 960-972 - [c21]Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein:
ETH Hardness for Densest-k-Subgraph with Perfect Completeness. SODA 2017: 1326-1341 - [c20]Aviad Rubinstein, Sahil Singla:
Combinatorial Prophet Inequalities. SODA 2017: 1671-1687 - [c19]Yakov Babichenko, Aviad Rubinstein:
Communication complexity of approximate Nash equilibria. STOC 2017: 878-889 - [c18]Eric Balkanski, Aviad Rubinstein, Yaron Singer:
The limitations of optimization from samples. STOC 2017: 1016-1027 - 2016
- [c17]Siu On Chan, Dimitris Papailliopoulos, Aviad Rubinstein:
On the Approximability of Sparse PCA. COLT 2016: 623-646 - [c16]Aviad Rubinstein:
Settling the Complexity of Computing Approximate Two-Player Nash Equilibria. FOCS 2016: 258-265 - [c15]Yakov Babichenko, Christos H. Papadimitriou, Aviad Rubinstein:
Can Almost Everybody be Almost Happy? ITCS 2016: 1-9 - [c14]Aviad Rubinstein:
On the Computational Complexity of Optimal Simple Mechanisms. ITCS 2016: 21-28 - [c13]Eric Balkanski, Aviad Rubinstein, Yaron Singer:
The Power of Optimization from Samples. NIPS 2016: 4017-4025 - [c12]Ashwinkumar Badanidiyuru, Christos H. Papadimitriou, Aviad Rubinstein, Lior Seeman, Yaron Singer:
Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions. SODA 2016: 414-429 - [c11]Christos H. Papadimitriou, George Pierrakos, Christos-Alexandros Psomas, Aviad Rubinstein:
On the Complexity of Dynamic Mechanism Design. SODA 2016: 1458-1475 - [c10]Aviad Rubinstein:
Beyond matroids: secretary problem and prophet inequality with general constraints. STOC 2016: 324-332 - 2015
- [c9]Aviad Rubinstein, S. Matthew Weinberg:
Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity. EC 2015: 377-394 - [c8]Wei Chen, Fu Li, Tian Lin, Aviad Rubinstein:
Combining Traditional Marketing and Viral Marketing with Amphibious Influence Maximization. EC 2015: 779-796 - [c7]Aviad Rubinstein, Lior Seeman, Yaron Singer:
Approximability of Adaptive Seeding under Knapsack Constraints. EC 2015: 797-814 - [c6]Yishay Mansour, Aviad Rubinstein, Moshe Tennenholtz:
Robust Probabilistic Inference. SODA 2015: 449-460 - [c5]Aviad Rubinstein:
Inapproximability of Nash Equilibrium. STOC 2015: 409-418 - 2014
- [c4]Adi Livnat, Christos H. Papadimitriou, Aviad Rubinstein, Gregory Valiant, Andrew Wan:
Satisfiability and Evolution. FOCS 2014: 524-530 - [c3]Ilan Adler, Christos H. Papadimitriou, Aviad Rubinstein:
On Simplex Pivoting Rules and Complexity Theory. IPCO 2014: 13-24 - [c2]Abraham Othman, Christos H. Papadimitriou, Aviad Rubinstein:
The complexity of fairness through equilibrium. EC 2014: 209-226 - 2012
- [c1]Yishay Mansour, Aviad Rubinstein, Shai Vardi, Ning Xie:
Converting Online Algorithms to Local Computation Algorithms. ICALP (1) 2012: 653-664
Informal and Other Publications
- 2024
- [i73]Aviad Rubinstein, Junyao Zhao:
Strategizing against No-Regret Learners in First-Price Auctions. CoRR abs/2402.08637 (2024) - [i72]Paul Dütting, Michal Feldman, Yoav Gal Tzur, Aviad Rubinstein:
The Query Complexity of Contracts. CoRR abs/2403.09794 (2024) - [i71]Binghui Peng, Aviad Rubinstein:
The complexity of approximate (coarse) correlated equilibrium for incomplete information games. CoRR abs/2406.02357 (2024) - [i70]Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein:
Approximating Maximum Matching Requires Almost Quadratic Time. CoRR abs/2406.08595 (2024) - [i69]Nima Anari, Ruiquan Gao, Aviad Rubinstein:
Parallel Sampling via Counting. CoRR abs/2408.09442 (2024) - [i68]Ruiquan Gao, Mohammad Roghani, Aviad Rubinstein, Amin Saberi:
Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting. CoRR abs/2409.15713 (2024) - 2023
- [i67]Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi:
Sublinear Algorithms for TSP via Path Covers. CoRR abs/2301.05350 (2023) - [i66]Binghui Peng, Aviad Rubinstein:
Near Optimal Memory-Regret Tradeoff for Online Learning. CoRR abs/2303.01673 (2023) - [i65]Eric Budish, Ruiquan Gao, Abraham Othman, Aviad Rubinstein, Qianfan Zhang:
Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI). CoRR abs/2305.11406 (2023) - [i64]Shahar Dobzinski, Wenzheng Li, Aviad Rubinstein, Jan Vondrák:
A constant factor approximation for Nash social welfare with subadditive valuations. CoRR abs/2309.04656 (2023) - [i63]Lorenzo Beretta, Aviad Rubinstein:
Approximate Earth Mover's Distance in Truly-Subquadratic Time. CoRR abs/2310.19514 (2023) - [i62]Binghui Peng, Aviad Rubinstein:
Fast swap regret minimization and applications to approximate correlated equilibria. CoRR abs/2310.19647 (2023) - [i61]Alexandros Hollender, Aviad Rubinstein:
Envy-Free Cake-Cutting for Four Agents. CoRR abs/2311.02075 (2023) - [i60]Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein:
Local Computation Algorithms for Maximum Matching: New Lower Bounds. CoRR abs/2311.09359 (2023) - [i59]Aviad Rubinstein, Zixin Zhou:
Quantum Communication Complexity of Classical Auctions. CoRR abs/2311.12444 (2023) - 2022
- [i58]Aviad Rubinstein, Junyao Zhao:
Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation. CoRR abs/2204.11149 (2022) - [i57]Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi:
Beating Greedy Matching in Sublinear Time. CoRR abs/2206.13057 (2022) - [i56]Binghui Peng, Aviad Rubinstein:
Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window). CoRR abs/2211.05178 (2022) - [i55]Aviad Rubinstein, Junyao Zhao:
Beyond Worst-Case Budget-Feasible Mechanism Design. CoRR abs/2211.08711 (2022) - [i54]Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein:
Sublinear Time Algorithms and Complexity of Approximate Maximum Matching. CoRR abs/2211.15843 (2022) - 2021
- [i53]Aviad Rubinstein, Junyao Zhao:
Budget-Smoothed Analysis for Submodular Maximization. CoRR abs/2102.05782 (2021) - [i52]Aviad Rubinstein, Junyao Zhao:
The Randomized Communication Complexity of Randomized Auctions. CoRR abs/2104.11275 (2021) - [i51]Elazar Goldenberg, Aviad Rubinstein, Barna Saha:
Does Preprocessing help in Fast Sequence Comparisons? CoRR abs/2108.09115 (2021) - [i50]Paul Liu, Aviad Rubinstein, Jan Vondrák, Junyao Zhao:
Cardinality constrained submodular maximization for random streams. CoRR abs/2111.07217 (2021) - [i49]Aviad Rubinstein, Saeed Seddighin, Zhao Song, Xiaorui Sun:
Approximation Algorithms for LCS and LIS with Truly Improved Running Times. CoRR abs/2111.10538 (2021) - 2020
- [i48]Alireza Farhadi, MohammadTaghi Hajiaghayi, Aviad Rubinstein, Saeed Seddighin:
Streaming with Oracle: New Streaming Algorithms for Edit Distance and LCS. CoRR abs/2002.11342 (2020) - [i47]Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, Aviad Rubinstein:
Smoothed Complexity of 2-player Nash Equilibria. CoRR abs/2007.10857 (2020) - [i46]Joshua Brakensiek, Moses Charikar, Aviad Rubinstein:
A Simple Sublinear Algorithm for Gap Edit Distance. CoRR abs/2007.14368 (2020) - [i45]Pasin Manurangsi, Aviad Rubinstein, Tselil Schramm:
The Strongish Planted Clique Hypothesis and Its Consequences. CoRR abs/2011.05555 (2020) - [i44]Yakov Babichenko, Aviad Rubinstein:
Communication complexity of Nash equilibrium in potential games. CoRR abs/2011.06660 (2020) - [i43]Yakov Babichenko, Aviad Rubinstein:
Settling the complexity of Nash equilibrium in congestion games. CoRR abs/2012.04327 (2020) - [i42]Aranyak Mehta, Uri Nadav, Alexandros Psomas, Aviad Rubinstein:
Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics. CoRR abs/2012.07935 (2020) - [i41]Aviad Rubinstein, Raghuvansh R. Saxena, Clayton Thomas, S. Matthew Weinberg, Junyao Zhao:
Exponential Communication Separations between Notions of Selfishness. CoRR abs/2012.14898 (2020) - 2019
- [i40]Joshua Brakensiek, Aviad Rubinstein:
Constant-factor approximation of near-linear edit distance in near-linear time. CoRR abs/1904.05390 (2019) - [i39]Aviad Rubinstein, Zhao Song:
Reducing approximate Longest Common Subsequence to approximate Edit Distance. CoRR abs/1904.05451 (2019) - [i38]Kousha Etessami, Christos H. Papadimitriou, Aviad Rubinstein, Mihalis Yannakakis:
Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria. CoRR abs/1909.03210 (2019) - [i37]Aviad Rubinstein, Jack Z. Wang, S. Matthew Weinberg:
Optimal Single-Choice Prophet Inequalities from Samples. CoRR abs/1911.07945 (2019) - 2018
- [i36]Michal Feldman, Ophir Friedler, Aviad Rubinstein:
99\% Revenue via Enhanced Competition. CoRR abs/1801.02908 (2018) - [i35]Aviad Rubinstein:
Hardness of Approximate Nearest Neighbor Search. CoRR abs/1803.00904 (2018) - [i34]Eric Balkanski, Aviad Rubinstein, Yaron Singer:
An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation. CoRR abs/1804.06355 (2018) - [i33]Moshe Babaioff, Noam Nisan, Aviad Rubinstein:
Optimal Deterministic Mechanisms for an Additive Buyer. CoRR abs/1804.06867 (2018) - [i32]Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, Aviad Rubinstein:
Fine-grained Complexity Meets IP = PSPACE. CoRR abs/1805.02351 (2018) - [i31]Mika Göös, Aviad Rubinstein:
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria. CoRR abs/1805.06387 (2018) - [i30]Bernhard Haeupler, Aviad Rubinstein, Amirbehshad Shahrasbi:
Near-Linear Time Insertion-Deletion Codes and (1+ε)-Approximating Edit Distance via Indexing. CoRR abs/1810.11863 (2018) - [i29]Eric Balkanski, Aviad Rubinstein, Yaron Singer:
An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model. CoRR abs/1811.03093 (2018) - 2017
- [i28]Pasin Manurangsi, Aviad Rubinstein:
Inapproximability of VC Dimension and Littlestone's Dimension. CoRR abs/1705.09517 (2017) - [i27]Amir Abboud, Aviad Rubinstein:
Distributed PCP Theorems for Hardness of Approximation in P. CoRR abs/1706.06407 (2017) - [i26]Aviad Rubinstein, Tselil Schramm, S. Matthew Weinberg:
Computing exact minimum cuts without knowing the graph. CoRR abs/1711.03165 (2017) - 2016
- [i25]Aviad Rubinstein:
Beyond matroids: Secretary Problem and Prophet Inequality with general constraints. CoRR abs/1604.00357 (2016) - [i24]Aviad Rubinstein:
Settling the complexity of computing approximate two-player Nash equilibria. CoRR abs/1606.04550 (2016) - [i23]Yakov Babichenko, Aviad Rubinstein:
Communication complexity of approximate Nash equilibria. CoRR abs/1608.06580 (2016) - [i22]Aviad Rubinstein, Sahil Singla:
Combinatorial Prophet Inequalities. CoRR abs/1611.00665 (2016) - [i21]Aviad Rubinstein:
Detecting communities is hard, and counting them is even harder. CoRR abs/1611.08326 (2016) - 2015
- [i20]Aviad Rubinstein, S. Matthew Weinberg:
Simple Mechanisms for a Combinatorial Buyer and Applications to Revenue Monotonicity. CoRR abs/1501.07637 (2015) - [i19]Yakov Babichenko, Christos H. Papadimitriou, Aviad Rubinstein:
Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash. CoRR abs/1504.02411 (2015) - [i18]Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein:
ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness. CoRR abs/1504.08352 (2015) - [i17]Ashwinkumar Badanidiyuru, Christos H. Papadimitriou, Aviad Rubinstein, Lior Seeman, Yaron Singer:
Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions. CoRR abs/1507.02351 (2015) - [i16]Wei Chen, Fu Li, Tian Lin, Aviad Rubinstein:
Combining Traditional Marketing and Viral Marketing with Amphibious Influence Maximization. CoRR abs/1507.03328 (2015) - [i15]Siu On Chan, Dimitris S. Papailiopoulos, Aviad Rubinstein:
On the Worst-Case Approximability of Sparse PCA. CoRR abs/1507.05950 (2015) - [i14]Aviad Rubinstein:
ETH-Hardness for Signaling in Symmetric Zero-Sum Games. CoRR abs/1510.04991 (2015) - [i13]Aviad Rubinstein:
On the Computational Complexity of Optimal Simple Mechanisms. CoRR abs/1511.04741 (2015) - [i12]Eric Balkanski, Aviad Rubinstein, Yaron Singer:
The Limitations of Optimization from Samples. CoRR abs/1512.06238 (2015) - [i11]Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein:
ETH Hardness for Densest-k-Subgraph with Perfect Completeness. Electron. Colloquium Comput. Complex. TR15 (2015) - [i10]Aviad Rubinstein:
Inapproximability of Nash Equilibrium. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [i9]Ilan Adler, Christos H. Papadimitriou, Aviad Rubinstein:
On Simplex Pivoting Rules and Complexity Theory. CoRR abs/1404.3320 (2014) - [i8]Aviad Rubinstein:
Computational Complexity of Approximate Nash Equilibrium in Large Games. CoRR abs/1405.0524 (2014) - [i7]Aviad Rubinstein:
Inapproximability of Nash Equilibrium. CoRR abs/1405.3322 (2014) - [i6]Christos H. Papadimitriou, George Pierrakos, Christos-Alexandros Psomas, Aviad Rubinstein:
The Intractability of Dynamic Mechanism Design. CoRR abs/1407.5373 (2014) - [i5]Nir Bitansky, Ran Canetti, Alessandro Chiesa, Shafi Goldwasser, Huijia Lin, Aviad Rubinstein, Eran Tromer:
The Hunting of the SNARK. IACR Cryptol. ePrint Arch. 2014: 580 (2014) - 2013
- [i4]Adi Livnat, Christos H. Papadimitriou, Aviad Rubinstein, Andrew Wan:
Satisfiability and Evolution. CoRR abs/1312.1983 (2013) - [i3]Abraham Othman, Christos H. Papadimitriou, Aviad Rubinstein:
The Complexity of Fairness through Equilibrium. CoRR abs/1312.6249 (2013) - 2012
- [i2]Yishay Mansour, Aviad Rubinstein, Shai Vardi, Ning Xie:
Converting online algorithms to local computation algorithms. CoRR abs/1205.1312 (2012) - 2011
- [i1]Shafi Goldwasser, Huijia Lin, Aviad Rubinstein:
Delegation of Computation without Rejection Problem from Designated Verifier CS-Proofs. IACR Cryptol. ePrint Arch. 2011: 456 (2011)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-17 21:33 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
