Aviad Rubinstein

171 papers A* 60A 12B 1Journal 93Unranked 3

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time. CoRR Xiao Mao, Aviad Rubinstein
2026	A*	`conf`	When Contracts Get Complex: Information-Theoretic Barriers. SODA Paul Dütting, Michal Feldman, Yoav Gal Tzur, Aviad Rubinstein
2025	A	`conf`	A Bicriterion Concentration Inequality and Prophet Inequalities for k-Fold Matroid Unions. ITCS Noga Alon, Nick Gravin, Tristan Pollner, Aviad Rubinstein, Hongao Wang, S. Matthew Weinberg, Qianfan Zhang
2025	A*	`conf`	A Near Linear Query Lower Bound for Submodular Maximization. ICML Binghui Peng, Aviad Rubinstein
2025	J	`jnl`	Approximation Algorithms for LCS and LIS with Truly Improved Running Times. SIAM J. Comput. Aviad Rubinstein, Saeed Seddighin, Zhao Song, Xiaorui Sun
2025	J	`jnl`	Envy-Free Cake-Cutting for Four Agents. J. ACM Alexandros Hollender, Aviad Rubinstein
2025	A*	`conf`	High-to-Low Dimensional PPA-completeness: Borsuk-Ulam, Tucker, Consensus Halving, and Ham Sandwich. FOCS Ruiquan Gao, Alexandros Hollender, Aviad Rubinstein
2025	A	`conf`	Quantum Communication Complexity of Classical Auctions. ITCS Aviad Rubinstein, Zixin Zhou
2025	A*	`conf`	Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance. FOCS Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
2025	J	`jnl`	Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance. CoRR Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
2024	J	`jnl`	A Bicriterion Concentration Inequality and Prophet Inequalities for CoRR Noga Alon, Nick Gravin, Tristan Pollner, Aviad Rubinstein, Hongao Wang, S. Matthew Weinberg, Qianfan Zhang
2024	A*	`conf`	A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations. STOC Shahar Dobzinski, Wenzheng Li, Aviad Rubinstein, Jan Vondrák
2024	A*	`conf`	Approximate Earth Mover's Distance in Truly-Subquadratic Time. STOC Lorenzo Beretta, Aviad Rubinstein
2024	A*	`conf`	Approximating Maximum Matching Requires Almost Quadratic Time. STOC Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
2024	J	`jnl`	Approximating Maximum Matching Requires Almost Quadratic Time. CoRR Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
2024	A*	`conf`	Fast Swap Regret Minimization and Applications to Approximate Correlated Equilibria. STOC Binghui Peng, Aviad Rubinstein
2024	A*	`conf`	Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting. FOCS Ruiquan Gao, Mohammad Roghani, Aviad Rubinstein, Amin Saberi
2024	J	`jnl`	Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting. CoRR Ruiquan Gao, Mohammad Roghani, Aviad Rubinstein, Amin Saberi
2024	A*	`conf`	Parallel Sampling via Counting. STOC Nima Anari, Ruiquan Gao, Aviad Rubinstein
2024	J	`jnl`	Parallel Sampling via Counting. CoRR Nima Anari, Ruiquan Gao, Aviad Rubinstein
2024	A*	`conf`	Strategizing against No-Regret Learners in First-Price Auctions. EC Aviad Rubinstein, Junyao Zhao
2024	J	`jnl`	Strategizing against No-Regret Learners in First-Price Auctions. CoRR Aviad Rubinstein, Junyao Zhao
2024	A*	`conf`	Sublinear Algorithms for TSP via Path Covers. ICALP Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi
2024	J	`jnl`	The Query Complexity of Contracts. CoRR Paul Dütting, Michal Feldman, Yoav Gal Tzur, Aviad Rubinstein
2024	A*	`conf`	The complexity of approximate (coarse) correlated equilibrium for incomplete information games. COLT Binghui Peng, Aviad Rubinstein
2024	J	`jnl`	The complexity of approximate (coarse) correlated equilibrium for incomplete information games. CoRR Binghui Peng, Aviad Rubinstein
2023	J	`jnl`	A constant factor approximation for Nash social welfare with subadditive valuations. CoRR Shahar Dobzinski, Wenzheng Li, Aviad Rubinstein, Jan Vondrák
2023	J	`jnl`	Approximate Earth Mover's Distance in Truly-Subquadratic Time. CoRR Lorenzo Beretta, Aviad Rubinstein
2023	A*	`conf`	Beating Greedy Matching in Sublinear Time. SODA Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi
2023	A	`conf`	Beyond Worst-Case Budget-Feasible Mechanism Design. ITCS Aviad Rubinstein, Junyao Zhao
2023	A*	`conf`	Envy-Free Cake-Cutting for Four Agents. FOCS Alexandros Hollender, Aviad Rubinstein
2023	J	`jnl`	Envy-Free Cake-Cutting for Four Agents. CoRR Alexandros Hollender, Aviad Rubinstein
2023	J	`jnl`	Fast swap regret minimization and applications to approximate correlated equilibria. CoRR Binghui Peng, Aviad Rubinstein
2023	—	`conf`	Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window). SOSA Binghui Peng, Aviad Rubinstein
2023	A*	`conf`	Local Computation Algorithms for Maximum Matching: New Lower Bounds. FOCS Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
2023	J	`jnl`	Local Computation Algorithms for Maximum Matching: New Lower Bounds. CoRR Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
2023	A*	`conf`	Near Optimal Memory-Regret Tradeoff for Online Learning. FOCS Binghui Peng, Aviad Rubinstein
2023	J	`jnl`	Near Optimal Memory-Regret Tradeoff for Online Learning. CoRR Binghui Peng, Aviad Rubinstein
2023	J	`jnl`	Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria. SIAM J. Comput. Mika Göös, Aviad Rubinstein
2023	A*	`conf`	Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI). EC Eric Budish, Ruiquan Gao, Abraham Othman, Aviad Rubinstein, Qianfan Zhang
2023	J	`jnl`	Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI). CoRR Eric Budish, Ruiquan Gao, Abraham Othman, Aviad Rubinstein, Qianfan Zhang
2023	J	`jnl`	Quantum Communication Complexity of Classical Auctions. CoRR Aviad Rubinstein, Zixin Zhou
2023	J	`jnl`	Sublinear Algorithms for TSP via Path Covers. CoRR Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi
2023	A*	`conf`	Sublinear Time Algorithms and Complexity of Approximate Maximum Matching. STOC Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
2022	J	`jnl`	An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model. Oper. Res. Eric Balkanski, Aviad Rubinstein, Yaron Singer
2022	J	`jnl`	Beating Greedy Matching in Sublinear Time. CoRR Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi
2022	J	`jnl`	Beyond Worst-Case Budget-Feasible Mechanism Design. CoRR Aviad Rubinstein, Junyao Zhao
2022	A	`conf`	Budget-Smoothed Analysis for Submodular Maximization. ITCS Aviad Rubinstein, Junyao Zhao
2022	J	`jnl`	Communication complexity of approximate Nash equilibria. Games Econ. Behav. Yakov Babichenko, Aviad Rubinstein
2022	J	`jnl`	Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window). CoRR Binghui Peng, Aviad Rubinstein
2022	A*	`conf`	Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation. ICALP Aviad Rubinstein, Junyao Zhao
2022	J	`jnl`	Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation. CoRR Aviad Rubinstein, Junyao Zhao
2022	J	`jnl`	On the complexity of dynamic mechanism design. Games Econ. Behav. Christos H. Papadimitriou, George Pierrakos, Alexandros Psomas, Aviad Rubinstein
2022	J	`jnl`	Sublinear Time Algorithms and Complexity of Approximate Maximum Matching. CoRR Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
2022	J	`jnl`	The Limitations of Optimization from Samples. J. ACM Eric Balkanski, Aviad Rubinstein, Yaron Singer
2021	J	`jnl`	Approximation Algorithms for LCS and LIS with Truly Improved Running Times. CoRR Aviad Rubinstein, Saeed Seddighin, Zhao Song, Xiaorui Sun
2021	J	`jnl`	Budget-Smoothed Analysis for Submodular Maximization. CoRR Aviad Rubinstein, Junyao Zhao
2021	A*	`conf`	Cardinality constrained submodular maximization for random streams. NeurIPS Paul Liu, Aviad Rubinstein, Jan Vondrák, Junyao Zhao
2021	J	`jnl`	Cardinality constrained submodular maximization for random streams. CoRR Paul Liu, Aviad Rubinstein, Jan Vondrák, Junyao Zhao
2021	J	`jnl`	Does Preprocessing help in Fast Sequence Comparisons? CoRR Elazar Goldenberg, Aviad Rubinstein, Barna Saha
2021	A*	`conf`	Exponential communication separations between notions of selfishness. STOC Aviad Rubinstein, Raghuvansh R. Saxena, Clayton Thomas, S. Matthew Weinberg, Junyao Zhao
2021	A*	`conf`	Settling the complexity of Nash equilibrium in congestion games. STOC Yakov Babichenko, Aviad Rubinstein
2021	A*	`conf`	Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence. ICALP Kuan Cheng, Alireza Farhadi, MohammadTaghi Hajiaghayi, Zhengzhong Jin, Xin Li, Aviad Rubinstein, Saeed Seddighin, Yu Zheng
2021	J	`jnl`	The Randomized Communication Complexity of Randomized Auctions. CoRR Aviad Rubinstein, Junyao Zhao
2021	A	`conf`	The Strongish Planted Clique Hypothesis and Its Consequences. ITCS Pasin Manurangsi, Aviad Rubinstein, Tselil Schramm
2021	A*	`conf`	The randomized communication complexity of randomized auctions. STOC Aviad Rubinstein, Junyao Zhao
2021	J	`jnl`	The randomized communication complexity of revenue maximization. SIGecom Exch. Aviad Rubinstein, Junyao Zhao
2020	J	`jnl`	A Simple Sublinear Algorithm for Gap Edit Distance. CoRR Joshua Brakensiek, Moses Charikar, Aviad Rubinstein
2020	A*	`conf`	Communication complexity of Nash equilibrium in potential games (extended abstract). FOCS Yakov Babichenko, Aviad Rubinstein
2020	J	`jnl`	Communication complexity of Nash equilibrium in potential games. CoRR Yakov Babichenko, Aviad Rubinstein
2020	A*	`conf`	Constant-factor approximation of near-linear edit distance in near-linear time. STOC Joshua Brakensiek, Aviad Rubinstein
2020	A*	`conf`	Does preprocessing help in fast sequence comparisons? STOC Elazar Goldenberg, Aviad Rubinstein, Barna Saha
2020	J	`jnl`	Exponential Communication Separations between Notions of Selfishness. CoRR Aviad Rubinstein, Raghuvansh R. Saxena, Clayton Thomas, S. Matthew Weinberg, Junyao Zhao
2020	A*	`conf`	Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics. NeurIPS Aranyak Mehta, Uri Nadav, Alexandros Psomas, Aviad Rubinstein
2020	J	`jnl`	Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics. CoRR Aranyak Mehta, Uri Nadav, Alexandros Psomas, Aviad Rubinstein
2020	A	`conf`	Optimal Single-Choice Prophet Inequalities from Samples. ITCS Aviad Rubinstein, Jack Z. Wang, S. Matthew Weinberg
2020	A*	`conf`	Reducing approximate Longest Common Subsequence to approximate Edit Distance. SODA Aviad Rubinstein, Zhao Song
2020	J	`jnl`	Settling the complexity of Nash equilibrium in congestion games. CoRR Yakov Babichenko, Aviad Rubinstein
2020	A*	`conf`	Smoothed Complexity of 2-player Nash Equilibria. FOCS Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, Aviad Rubinstein
2020	J	`jnl`	Smoothed Complexity of 2-player Nash Equilibria. CoRR Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, Aviad Rubinstein
2020	J	`jnl`	Streaming with Oracle: New Streaming Algorithms for Edit Distance and LCS. CoRR Alireza Farhadi, MohammadTaghi Hajiaghayi, Aviad Rubinstein, Saeed Seddighin
2020	A	`conf`	Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria. ITCS Kousha Etessami, Christos H. Papadimitriou, Aviad Rubinstein, Mihalis Yannakakis
2020	J	`jnl`	The Strongish Planted Clique Hypothesis and Its Consequences. CoRR Pasin Manurangsi, Aviad Rubinstein, Tselil Schramm
2019	A*	`conf`	An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation. SODA Eric Balkanski, Aviad Rubinstein, Yaron Singer
2019	A*	`conf`	An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model. STOC Eric Balkanski, Aviad Rubinstein, Yaron Singer
2019	A*	`conf`	Approximation Algorithms for LCS and LIS with Truly Improved Running Times. FOCS Aviad Rubinstein, Saeed Seddighin, Zhao Song, Xiaorui Sun
2019	J	`jnl`	Constant-factor approximation of near-linear edit distance in near-linear time. CoRR Joshua Brakensiek, Aviad Rubinstein
2019	A*	`conf`	Fine-grained Complexity Meets IP = PSPACE. SODA Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, Aviad Rubinstein
2019	—	`book`	Hardness of Approximation Between P and NP Hardness of Approximation Between P and NP Aviad Rubinstein
2019	A*	`conf`	Near-linear time insertion-deletion codes and (1+ STOC Bernhard Haeupler, Aviad Rubinstein, Amirbehshad Shahrasbi
2019	J	`jnl`	Optimal Single-Choice Prophet Inequalities from Samples. CoRR Aviad Rubinstein, Jack Z. Wang, S. Matthew Weinberg
2019	J	`jnl`	Reducing approximate Longest Common Subsequence to approximate Edit Distance. CoRR Aviad Rubinstein, Zhao Song
2019	J	`jnl`	Reductions in PPP. Inf. Process. Lett. Frank Ban, Kamal Jain, Christos H. Papadimitriou, Christos-Alexandros Psomas, Aviad Rubinstein
2019	J	`jnl`	SETH vs Approximation. SIGACT News Aviad Rubinstein, Virginia Vassilevska Williams
2019	J	`jnl`	Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria. CoRR Kousha Etessami, Christos H. Papadimitriou, Aviad Rubinstein, Mihalis Yannakakis
2018	A*	`conf`	99% Revenue via Enhanced Competition. EC Michal Feldman, Ophir Friedler, Aviad Rubinstein
2018	J	`jnl`	99\% Revenue via Enhanced Competition. CoRR Michal Feldman, Ophir Friedler, Aviad Rubinstein
2018	J	`jnl`	An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation. CoRR Eric Balkanski, Aviad Rubinstein, Yaron Singer
2018	J	`jnl`	An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model. CoRR Eric Balkanski, Aviad Rubinstein, Yaron Singer
2018	A	`conf`	Computing Exact Minimum Cuts Without Knowing the Graph. ITCS Aviad Rubinstein, Tselil Schramm, S. Matthew Weinberg
2018	A	`conf`	Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds. ITCS Amir Abboud, Aviad Rubinstein
2018	J	`jnl`	Fine-grained Complexity Meets IP = PSPACE. CoRR Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, Aviad Rubinstein
2018	J	`jnl`	Hardness of Approximate Nearest Neighbor Search. CoRR Aviad Rubinstein
2018	A*	`conf`	Hardness of approximate nearest neighbor search. STOC Aviad Rubinstein
2018	J	`jnl`	Inapproximability of Nash Equilibrium. SIAM J. Comput. Aviad Rubinstein
2018	J	`jnl`	Near-Linear Time Insertion-Deletion Codes and (1+ε)-Approximating Edit Distance via Indexing. CoRR Bernhard Haeupler, Aviad Rubinstein, Amirbehshad Shahrasbi
2018	A*	`conf`	Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria. FOCS Mika Göös, Aviad Rubinstein
2018	J	`jnl`	Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria. CoRR Mika Göös, Aviad Rubinstein
2018	A*	`conf`	Optimal Deterministic Mechanisms for an Additive Buyer. EC Moshe Babaioff, Noam Nisan, Aviad Rubinstein
2018	J	`jnl`	Optimal Deterministic Mechanisms for an Additive Buyer. CoRR Moshe Babaioff, Noam Nisan, Aviad Rubinstein
2018	J	`jnl`	Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity. ACM Trans. Economics and Comput. Aviad Rubinstein, S. Matthew Weinberg
2017	A*	`conf`	Combinatorial Prophet Inequalities. SODA Aviad Rubinstein, Sahil Singla
2017	A*	`conf`	Communication complexity of approximate Nash equilibria. STOC Yakov Babichenko, Aviad Rubinstein
2017	J	`jnl`	Computing exact minimum cuts without knowing the graph. CoRR Aviad Rubinstein, Tselil Schramm, S. Matthew Weinberg
2017	A	`conf`	Detecting communities is Hard (And Counting Them is Even Harder). ITCS Aviad Rubinstein
2017	A*	`conf`	Distributed PCP Theorems for Hardness of Approximation in P. FOCS Amir Abboud, Aviad Rubinstein, R. Ryan Williams
2017	J	`jnl`	Distributed PCP Theorems for Hardness of Approximation in P. CoRR Amir Abboud, Aviad Rubinstein
2017	A*	`conf`	ETH Hardness for Densest- SODA Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein
2017	—	`—`	Hardness of Approximation Between P and NP. Aviad Rubinstein
2017	A*	`conf`	Honest Signaling in Zero-Sum Games Is Hard, and Lying Is Even Harder. ICALP Aviad Rubinstein
2017	A*	`conf`	Inapproximability of VC Dimension and Littlestone's Dimension. COLT Pasin Manurangsi, Aviad Rubinstein
2017	J	`jnl`	Inapproximability of VC Dimension and Littlestone's Dimension. CoRR Pasin Manurangsi, Aviad Rubinstein
2017	J	`jnl`	Settling the complexity of computing approximate two-player Nash equilibria. SIGecom Exch. Aviad Rubinstein
2017	A*	`conf`	Sorting from Noisier Samples. SODA Aviad Rubinstein, Shai Vardi
2017	J	`jnl`	The Hunting of the SNARK. J. Cryptol. Nir Bitansky, Ran Canetti, Alessandro Chiesa, Shafi Goldwasser, Huijia Lin, Aviad Rubinstein, Eran Tromer
2017	A*	`conf`	The limitations of optimization from samples. STOC Eric Balkanski, Aviad Rubinstein, Yaron Singer
2016	J	`jnl`	Beyond matroids: Secretary Problem and Prophet Inequality with general constraints. CoRR Aviad Rubinstein
2016	A*	`conf`	Beyond matroids: secretary problem and prophet inequality with general constraints. STOC Aviad Rubinstein
2016	A	`conf`	Can Almost Everybody be Almost Happy? ITCS Yakov Babichenko, Christos H. Papadimitriou, Aviad Rubinstein
2016	J	`jnl`	Combinatorial Prophet Inequalities. CoRR Aviad Rubinstein, Sahil Singla
2016	J	`jnl`	Communication complexity of approximate Nash equilibria. CoRR Yakov Babichenko, Aviad Rubinstein
2016	J	`jnl`	Detecting communities is hard, and counting them is even harder. CoRR Aviad Rubinstein
2016	A*	`conf`	Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions. SODA Ashwinkumar Badanidiyuru, Christos H. Papadimitriou, Aviad Rubinstein, Lior Seeman, Yaron Singer
2016	A*	`conf`	On the Approximability of Sparse PCA. COLT Siu On Chan, Dimitris Papailliopoulos, Aviad Rubinstein
2016	A*	`conf`	On the Complexity of Dynamic Mechanism Design. SODA Christos H. Papadimitriou, George Pierrakos, Christos-Alexandros Psomas, Aviad Rubinstein
2016	A	`conf`	On the Computational Complexity of Optimal Simple Mechanisms. ITCS Aviad Rubinstein
2016	A*	`conf`	Settling the Complexity of Computing Approximate Two-Player Nash Equilibria. FOCS Aviad Rubinstein
2016	J	`jnl`	Settling the complexity of computing approximate two-player Nash equilibria. CoRR Aviad Rubinstein
2016	J	`jnl`	The Complexity of Fairness Through Equilibrium. ACM Trans. Economics and Comput. Abraham Othman, Christos H. Papadimitriou, Aviad Rubinstein
2016	—	`conf`	The Power of Optimization from Samples. NIPS Eric Balkanski, Aviad Rubinstein, Yaron Singer
2015	A*	`conf`	Approximability of Adaptive Seeding under Knapsack Constraints. EC Aviad Rubinstein, Lior Seeman, Yaron Singer
2015	J	`jnl`	Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash. CoRR Yakov Babichenko, Christos H. Papadimitriou, Aviad Rubinstein
2015	A*	`conf`	Combining Traditional Marketing and Viral Marketing with Amphibious Influence Maximization. EC Wei Chen, Fu Li, Tian Lin, Aviad Rubinstein
2015	J	`jnl`	Combining Traditional Marketing and Viral Marketing with Amphibious Influence Maximization. CoRR Wei Chen, Fu Li, Tian Lin, Aviad Rubinstein
2015	J	`jnl`	ETH Hardness for Densest- Electron. Colloquium Comput. Complex. Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein
2015	J	`jnl`	ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness. CoRR Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein
2015	J	`jnl`	ETH-Hardness for Signaling in Symmetric Zero-Sum Games. CoRR Aviad Rubinstein
2015	A*	`conf`	Inapproximability of Nash Equilibrium. STOC Aviad Rubinstein
2015	J	`jnl`	Inapproximability of Nash Equilibrium. Electron. Colloquium Comput. Complex. Aviad Rubinstein
2015	J	`jnl`	Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions. CoRR Ashwinkumar Badanidiyuru, Christos H. Papadimitriou, Aviad Rubinstein, Lior Seeman, Yaron Singer
2015	J	`jnl`	On the Computational Complexity of Optimal Simple Mechanisms. CoRR Aviad Rubinstein
2015	J	`jnl`	On the Worst-Case Approximability of Sparse PCA. CoRR Siu On Chan, Dimitris S. Papailiopoulos, Aviad Rubinstein
2015	A*	`conf`	Robust Probabilistic Inference. SODA Yishay Mansour, Aviad Rubinstein, Moshe Tennenholtz
2015	J	`jnl`	Simple Mechanisms for a Combinatorial Buyer and Applications to Revenue Monotonicity. CoRR Aviad Rubinstein, S. Matthew Weinberg
2015	A*	`conf`	Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity. EC Aviad Rubinstein, S. Matthew Weinberg
2015	J	`jnl`	The Limitations of Optimization from Samples. CoRR Eric Balkanski, Aviad Rubinstein, Yaron Singer
2015	J	`jnl`	The complexity of simplicity in mechanism design. SIGecom Exch. Aviad Rubinstein
2014	J	`jnl`	Computational Complexity of Approximate Nash Equilibrium in Large Games. CoRR Aviad Rubinstein
2014	J	`jnl`	Inapproximability of Nash Equilibrium. CoRR Aviad Rubinstein
2014	B	`conf`	On Simplex Pivoting Rules and Complexity Theory. IPCO Ilan Adler, Christos H. Papadimitriou, Aviad Rubinstein
2014	J	`jnl`	On Simplex Pivoting Rules and Complexity Theory. CoRR Ilan Adler, Christos H. Papadimitriou, Aviad Rubinstein
2014	A*	`conf`	Satisfiability and Evolution. FOCS Adi Livnat, Christos H. Papadimitriou, Aviad Rubinstein, Gregory Valiant, Andrew Wan
2014	J	`jnl`	The Hunting of the SNARK. IACR Cryptol. ePrint Arch. Nir Bitansky, Ran Canetti, Alessandro Chiesa, Shafi Goldwasser, Huijia Lin, Aviad Rubinstein, Eran Tromer
2014	J	`jnl`	The Intractability of Dynamic Mechanism Design. CoRR Christos H. Papadimitriou, George Pierrakos, Christos-Alexandros Psomas, Aviad Rubinstein
2014	A*	`conf`	The complexity of fairness through equilibrium. EC Abraham Othman, Christos H. Papadimitriou, Aviad Rubinstein
2013	J	`jnl`	Satisfiability and Evolution. CoRR Adi Livnat, Christos H. Papadimitriou, Aviad Rubinstein, Andrew Wan
2013	J	`jnl`	The Complexity of Fairness through Equilibrium. CoRR Abraham Othman, Christos H. Papadimitriou, Aviad Rubinstein
2012	—	`conf`	Converting Online Algorithms to Local Computation Algorithms. ICALP (1) Yishay Mansour, Aviad Rubinstein, Shai Vardi, Ning Xie
2012	J	`jnl`	Converting online algorithms to local computation algorithms CoRR Yishay Mansour, Aviad Rubinstein, Shai Vardi, Ning Xie
2011	J	`jnl`	Delegation of Computation without Rejection Problem from Designated Verifier CS-Proofs. IACR Cryptol. ePrint Arch. Shafi Goldwasser, Huijia Lin, Aviad Rubinstein
2007	J	`jnl`	Determining Sets for the Discrete Laplacian. SIAM Rev. Aviad Rubinstein, Jacob Rubinstein, Gershon Wolansky