Aviad Rubinstein

ORCID

Publication Activity (10 Years)

Years Active: 2007-2024
Publications (10 Years): 130

Top Venues

University of California at Berkeley, USA (PHD)

Education History

University of California at Berkeley, USA

PHD

Publications

Aviad Rubinstein, Junyao Zhao
Strategizing against No-Regret Learners in First-Price Auctions. CoRR (2024)
Shahar Dobzinski, Wenzheng Li, Aviad Rubinstein, Jan Vondrák
A constant factor approximation for Nash social welfare with subadditive valuations. CoRR (2023)
Binghui Peng, Aviad Rubinstein
Fast swap regret minimization and applications to approximate correlated equilibria. CoRR (2023)
Binghui Peng, Aviad Rubinstein
Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window). SOSA (2023)
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
Sublinear Time Algorithms and Complexity of Approximate Maximum Matching. STOC (2023)
Aviad Rubinstein, Junyao Zhao
Beyond Worst-Case Budget-Feasible Mechanism Design. ITCS (2023)
Mika Göös, Aviad Rubinstein
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria. SIAM J. Comput. 52 (6) (2023)
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi
Sublinear Algorithms for TSP via Path Covers. CoRR (2023)
Lorenzo Beretta, Aviad Rubinstein
Approximate Earth Mover's Distance in Truly-Subquadratic Time. CoRR (2023)
Aviad Rubinstein, Zixin Zhou
Quantum Communication Complexity of Classical Auctions. CoRR (2023)
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)
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi
Beating Greedy Matching in Sublinear Time. SODA (2023)
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
Local Computation Algorithms for Maximum Matching: New Lower Bounds. CoRR (2023)
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
Local Computation Algorithms for Maximum Matching: New Lower Bounds. FOCS (2023)
Alexandros Hollender, Aviad Rubinstein
Envy-Free Cake-Cutting for Four Agents. CoRR (2023)
Alexandros Hollender, Aviad Rubinstein
Envy-Free Cake-Cutting for Four Agents. FOCS (2023)
Binghui Peng, Aviad Rubinstein
Near Optimal Memory-Regret Tradeoff for Online Learning. FOCS (2023)
Eric Budish, Ruiquan Gao, Abraham Othman, Aviad Rubinstein, Qianfan Zhang
Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI). CoRR (2023)
Binghui Peng, Aviad Rubinstein
Near Optimal Memory-Regret Tradeoff for Online Learning. CoRR (2023)
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi
Beating Greedy Matching in Sublinear Time. CoRR (2022)
Aviad Rubinstein, Junyao Zhao
Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation. ICALP (2022)
Aviad Rubinstein, Junyao Zhao
Budget-Smoothed Analysis for Submodular Maximization. ITCS (2022)
Aviad Rubinstein, Junyao Zhao
Beyond Worst-Case Budget-Feasible Mechanism Design. CoRR (2022)
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
Sublinear Time Algorithms and Complexity of Approximate Maximum Matching. CoRR (2022)
Aviad Rubinstein, Junyao Zhao
Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation. CoRR (2022)
Eric Balkanski, Aviad Rubinstein, Yaron Singer
The Limitations of Optimization from Samples. J. ACM 69 (3) (2022)
Yakov Babichenko, Aviad Rubinstein
Communication complexity of approximate Nash equilibria. Games Econ. Behav. 134 (2022)
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) (2022)
Christos H. Papadimitriou, George Pierrakos, Alexandros Psomas, Aviad Rubinstein
On the complexity of dynamic mechanism design. Games Econ. Behav. 134 (2022)
Binghui Peng, Aviad Rubinstein
Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window). CoRR (2022)
Yakov Babichenko, Aviad Rubinstein
Settling the complexity of Nash equilibrium in congestion games. STOC (2021)
Aviad Rubinstein, Junyao Zhao
The randomized communication complexity of randomized auctions. STOC (2021)
Paul Liu, Aviad Rubinstein, Jan Vondrák, Junyao Zhao
Cardinality constrained submodular maximization for random streams. CoRR (2021)
Aviad Rubinstein, Junyao Zhao
The Randomized Communication Complexity of Randomized Auctions. CoRR (2021)
Paul Liu, Aviad Rubinstein, Jan Vondrák, Junyao Zhao
Cardinality constrained submodular maximization for random streams. NeurIPS (2021)
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)
Aviad Rubinstein, Junyao Zhao
Budget-Smoothed Analysis for Submodular Maximization. CoRR (2021)
Aviad Rubinstein, Raghuvansh R. Saxena, Clayton Thomas, S. Matthew Weinberg, Junyao Zhao
Exponential communication separations between notions of selfishness. STOC (2021)
Elazar Goldenberg, Aviad Rubinstein, Barna Saha
Does Preprocessing help in Fast Sequence Comparisons? CoRR (2021)
Aviad Rubinstein, Junyao Zhao
The randomized communication complexity of revenue maximization. SIGecom Exch. 19 (2) (2021)
Pasin Manurangsi, Aviad Rubinstein, Tselil Schramm
The Strongish Planted Clique Hypothesis and Its Consequences. ITCS (2021)
Aviad Rubinstein, Saeed Seddighin, Zhao Song, Xiaorui Sun
Approximation Algorithms for LCS and LIS with Truly Improved Running Times. CoRR (2021)
Kousha Etessami, Christos H. Papadimitriou, Aviad Rubinstein, Mihalis Yannakakis
Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria. ITCS (2020)
Aranyak Mehta, Uri Nadav, Alexandros Psomas, Aviad Rubinstein
Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics. CoRR (2020)
Joshua Brakensiek, Moses Charikar, Aviad Rubinstein
A Simple Sublinear Algorithm for Gap Edit Distance. CoRR (2020)
Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, Aviad Rubinstein
Smoothed Complexity of 2-player Nash Equilibria. FOCS (2020)
Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, Aviad Rubinstein
Smoothed Complexity of 2-player Nash Equilibria. CoRR (2020)
Yakov Babichenko, Aviad Rubinstein
Settling the complexity of Nash equilibrium in congestion games. CoRR (2020)
Aranyak Mehta, Uri Nadav, Alexandros Psomas, Aviad Rubinstein
Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics. NeurIPS (2020)
Alireza Farhadi, MohammadTaghi Hajiaghayi, Aviad Rubinstein, Saeed Seddighin
Streaming with Oracle: New Streaming Algorithms for Edit Distance and LCS. CoRR (2020)
Elazar Goldenberg, Aviad Rubinstein, Barna Saha
Does preprocessing help in fast sequence comparisons? STOC (2020)
Aviad Rubinstein, Raghuvansh R. Saxena, Clayton Thomas, S. Matthew Weinberg, Junyao Zhao
Exponential Communication Separations between Notions of Selfishness. CoRR (2020)
Yakov Babichenko, Aviad Rubinstein
Communication complexity of Nash equilibrium in potential games (extended abstract). FOCS (2020)
Pasin Manurangsi, Aviad Rubinstein, Tselil Schramm
The Strongish Planted Clique Hypothesis and Its Consequences. CoRR (2020)
Aviad Rubinstein, Jack Z. Wang, S. Matthew Weinberg
Optimal Single-Choice Prophet Inequalities from Samples. ITCS (2020)
Yakov Babichenko, Aviad Rubinstein
Communication complexity of Nash equilibrium in potential games. CoRR (2020)
Joshua Brakensiek, Aviad Rubinstein
Constant-factor approximation of near-linear edit distance in near-linear time. STOC (2020)
Aviad Rubinstein, Zhao Song
Reducing approximate Longest Common Subsequence to approximate Edit Distance. SODA (2020)
Eric Balkanski, Aviad Rubinstein, Yaron Singer
An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation. SODA (2019)
Aviad Rubinstein, Jack Z. Wang, S. Matthew Weinberg
Optimal Single-Choice Prophet Inequalities from Samples. CoRR (2019)
Aviad Rubinstein, Saeed Seddighin, Zhao Song, Xiaorui Sun
Approximation Algorithms for LCS and LIS with Truly Improved Running Times. FOCS (2019)
Frank Ban, Kamal Jain, Christos H. Papadimitriou, Christos-Alexandros Psomas, Aviad Rubinstein
Reductions in PPP. Inf. Process. Lett. 145 (2019)
Bernhard Haeupler, Aviad Rubinstein, Amirbehshad Shahrasbi
)-approximating edit distance via indexing. STOC (2019)
Kousha Etessami, Christos H. Papadimitriou, Aviad Rubinstein, Mihalis Yannakakis
Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria. CoRR (2019)
Joshua Brakensiek, Aviad Rubinstein
Constant-factor approximation of near-linear edit distance in near-linear time. CoRR (2019)
Aviad Rubinstein, Virginia Vassilevska Williams
SETH vs Approximation. SIGACT News 50 (4) (2019)
Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, Aviad Rubinstein
Fine-grained Complexity Meets IP = PSPACE. SODA (2019)
Aviad Rubinstein, Zhao Song
Reducing approximate Longest Common Subsequence to approximate Edit Distance. CoRR (2019)
Eric Balkanski, Aviad Rubinstein, Yaron Singer
An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model. STOC (2019)
Moshe Babaioff, Noam Nisan, Aviad Rubinstein
Optimal Deterministic Mechanisms for an Additive Buyer. EC (2018)
Mika Göös, Aviad Rubinstein
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria. CoRR (2018)
Michal Feldman, Ophir Friedler, Aviad Rubinstein
99\% Revenue via Enhanced Competition. CoRR (2018)
Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, Aviad Rubinstein
Fine-grained Complexity Meets IP = PSPACE. CoRR (2018)
Eric Balkanski, Aviad Rubinstein, Yaron Singer
An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation. CoRR (2018)
Michal Feldman, Ophir Friedler, Aviad Rubinstein
99% Revenue via Enhanced Competition. EC (2018)
Aviad Rubinstein
Hardness of Approximate Nearest Neighbor Search. CoRR (2018)
Amir Abboud, Aviad Rubinstein
Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds. ITCS (2018)
Aviad Rubinstein
Inapproximability of Nash Equilibrium. SIAM J. Comput. 47 (3) (2018)
Aviad Rubinstein
Hardness of approximate nearest neighbor search. STOC (2018)
Eric Balkanski, Aviad Rubinstein, Yaron Singer
An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model. CoRR (2018)
Moshe Babaioff, Noam Nisan, Aviad Rubinstein
Optimal Deterministic Mechanisms for an Additive Buyer. CoRR (2018)
Aviad Rubinstein, Tselil Schramm, S. Matthew Weinberg
Computing Exact Minimum Cuts Without Knowing the Graph. ITCS (2018)
Aviad Rubinstein, S. Matthew Weinberg
Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity. ACM Trans. Economics and Comput. 6 (3-4) (2018)
Mika Göös, Aviad Rubinstein
Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria. FOCS (2018)
Bernhard Haeupler, Aviad Rubinstein, Amirbehshad Shahrasbi
Near-Linear Time Insertion-Deletion Codes and (1+ε)-Approximating Edit Distance via Indexing. CoRR (2018)
Eric Balkanski, Aviad Rubinstein, Yaron Singer
The limitations of optimization from samples. STOC (2017)
Aviad Rubinstein, Tselil Schramm, S. Matthew Weinberg
Computing exact minimum cuts without knowing the graph. CoRR (2017)
Yakov Babichenko, Aviad Rubinstein
Communication complexity of approximate Nash equilibria. STOC (2017)
Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein
-Subgraph with Perfect Completeness. SODA (2017)
Nir Bitansky, Ran Canetti, Alessandro Chiesa, Shafi Goldwasser, Huijia Lin, Aviad Rubinstein, Eran Tromer
The Hunting of the SNARK. J. Cryptol. 30 (4) (2017)
Aviad Rubinstein, Shai Vardi
Sorting from Noisier Samples. SODA (2017)
Aviad Rubinstein
Settling the complexity of computing approximate two-player Nash equilibria. SIGecom Exch. 15 (2) (2017)
Amir Abboud, Aviad Rubinstein, R. Ryan Williams
Distributed PCP Theorems for Hardness of Approximation in P. FOCS (2017)
Pasin Manurangsi, Aviad Rubinstein
Inapproximability of VC Dimension and Littlestone's Dimension. COLT (2017)
Aviad Rubinstein, Sahil Singla
Combinatorial Prophet Inequalities. SODA (2017)
Aviad Rubinstein
Honest Signaling in Zero-Sum Games Is Hard, and Lying Is Even Harder. ICALP (2017)
Pasin Manurangsi, Aviad Rubinstein
Inapproximability of VC Dimension and Littlestone's Dimension. CoRR (2017)
Amir Abboud, Aviad Rubinstein
Distributed PCP Theorems for Hardness of Approximation in P. CoRR (2017)
Aviad Rubinstein
Detecting communities is Hard (And Counting Them is Even Harder). ITCS (2017)
Ashwinkumar Badanidiyuru, Christos H. Papadimitriou, Aviad Rubinstein, Lior Seeman, Yaron Singer
Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions. SODA (2016)

Aviad Rubinstein.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Aviad Rubinstein