| 2026 | SODA | When Contracts Get Complex: Information-Theoretic Barriers. | Paul Dtting, Michal Feldman, Yoav Gal Tzur, Aviad Rubinstein |
| 2026 | STOC | Approximating Gains-from-Trade in Matching Markets. | Moshe Babaioff, Aviad Rubinstein, Xizhi Tan, Kangning Wang |
| 2026 | STOC | Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time. | Xiao Mao, Aviad Rubinstein |
| 2026 | STOC | Secretary, Prophet, and Stochastic Probing via Big-Decisions-First. | Aviad Rubinstein, Sahil Singla |
| 2025 | FOCS | Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance. | Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein |
| 2025 | FOCS | High-to-Low Dimensional PPA-completeness: Borsuk-Ulam, Tucker, Consensus Halving, and Ham Sandwich. | Ruiquan Gao, Alexandros Hollender, Aviad Rubinstein |
| 2025 | ICML | A Near Linear Query Lower Bound for Submodular Maximization. | Binghui Peng, Aviad Rubinstein |
| 2024 | COLT | The complexity of approximate (coarse) correlated equilibrium for incomplete information games. | Binghui Peng, Aviad Rubinstein |
| 2024 | FOCS | Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting. | Ruiquan Gao, Mohammad Roghani, Aviad Rubinstein, Amin Saberi |
| 2024 | ICALP | Sublinear Algorithms for TSP via Path Covers. | Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi |
| 2024 | STOC | Approximate Earth Mover's Distance in Truly-Subquadratic Time. | Lorenzo Beretta, Aviad Rubinstein |
| 2024 | STOC | Parallel Sampling via Counting. | Nima Anari, Ruiquan Gao, Aviad Rubinstein |
| 2024 | STOC | Approximating Maximum Matching Requires Almost Quadratic Time. | Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein |
| 2024 | STOC | A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations. | Shahar Dobzinski, Wenzheng Li, Aviad Rubinstein, Jan Vondrk |
| 2024 | STOC | Fast Swap Regret Minimization and Applications to Approximate Correlated Equilibria. | Binghui Peng, Aviad Rubinstein |
| 2023 | FOCS | Local Computation Algorithms for Maximum Matching: New Lower Bounds. | Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein |
| 2023 | FOCS | Envy-Free Cake-Cutting for Four Agents. | Alexandros Hollender, Aviad Rubinstein |
| 2023 | FOCS | Near Optimal Memory-Regret Tradeoff for Online Learning. | Binghui Peng, Aviad Rubinstein |
| 2023 | SODA | Beating Greedy Matching in Sublinear Time. | Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, Amin Saberi |
| 2023 | STOC | Sublinear Time Algorithms and Complexity of Approximate Maximum Matching. | Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein |
| 2022 | ICALP | Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation. | Aviad Rubinstein, Junyao Zhao |
| 2021 | ICALP | Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence. | Kuan Cheng, Alireza Farhadi, MohammadTaghi Hajiaghayi, Zhengzhong Jin, Xin Li, Aviad Rubinstein, Saeed Seddighin, Yu Zheng |
| 2021 | STOC | Settling the complexity of Nash equilibrium in congestion games. | Yakov Babichenko, Aviad Rubinstein |
| 2021 | STOC | Exponential communication separations between notions of selfishness. | Aviad Rubinstein, Raghuvansh R. Saxena, Clayton Thomas, S. Matthew Weinberg, Junyao Zhao |
| 2021 | STOC | The randomized communication complexity of randomized auctions. | Aviad Rubinstein, Junyao Zhao |
| 2020 | FOCS | Communication complexity of Nash equilibrium in potential games (extended abstract). | Yakov Babichenko, Aviad Rubinstein |
| 2020 | FOCS | Smoothed Complexity of 2-player Nash Equilibria. | Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, Aviad Rubinstein |
| 2020 | SODA | Reducing approximate Longest Common Subsequence to approximate Edit Distance. | Aviad Rubinstein, Zhao Song |
| 2020 | STOC | Constant-factor approximation of near-linear edit distance in near-linear time. | Joshua Brakensiek, Aviad Rubinstein |
| 2020 | STOC | Does preprocessing help in fast sequence comparisons? | Elazar Goldenberg, Aviad Rubinstein, Barna Saha |
| 2019 | FOCS | Approximation Algorithms for LCS and LIS with Truly Improved Running Times. | Aviad Rubinstein, Saeed Seddighin, Zhao Song, Xiaorui Sun |
| 2019 | SODA | An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation. | Eric Balkanski, Aviad Rubinstein, Yaron Singer |
| 2019 | SODA | Fine-grained Complexity Meets IP = PSPACE. | Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, Aviad Rubinstein |
| 2019 | STOC | An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model. | Eric Balkanski, Aviad Rubinstein, Yaron Singer |
| 2019 | STOC | Near-linear time insertion-deletion codes and (1+ | Bernhard Haeupler, Aviad Rubinstein, Amirbehshad Shahrasbi |
| 2018 | FOCS | Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria. | Mika Gs, Aviad Rubinstein |
| 2018 | STOC | Hardness of approximate nearest neighbor search. | Aviad Rubinstein |
| 2017 | COLT | Inapproximability of VC Dimension and Littlestone's Dimension. | Pasin Manurangsi, Aviad Rubinstein |
| 2017 | FOCS | Distributed PCP Theorems for Hardness of Approximation in P. | Amir Abboud, Aviad Rubinstein, R. Ryan Williams |
| 2017 | ICALP | Honest Signaling in Zero-Sum Games Is Hard, and Lying Is Even Harder. | Aviad Rubinstein |
| 2017 | SODA | ETH Hardness for Densest- | Mark Braverman, Young Kun-Ko, Aviad Rubinstein, Omri Weinstein |
| 2017 | SODA | Combinatorial Prophet Inequalities. | Aviad Rubinstein, Sahil Singla |
| 2017 | SODA | Sorting from Noisier Samples. | Aviad Rubinstein, Shai Vardi |
| 2017 | STOC | Communication complexity of approximate Nash equilibria. | Yakov Babichenko, Aviad Rubinstein |
| 2017 | STOC | The limitations of optimization from samples. | Eric Balkanski, Aviad Rubinstein, Yaron Singer |
| 2016 | COLT | On the Approximability of Sparse PCA. | Siu On Chan, Dimitris Papailliopoulos, Aviad Rubinstein |
| 2016 | FOCS | Settling the Complexity of Computing Approximate Two-Player Nash Equilibria. | Aviad Rubinstein |
| 2016 | SODA | Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions. | Ashwinkumar Badanidiyuru, Christos H. Papadimitriou, Aviad Rubinstein, Lior Seeman, Yaron Singer |
| 2016 | SODA | On the Complexity of Dynamic Mechanism Design. | Christos H. Papadimitriou, George Pierrakos, Christos-Alexandros Psomas, Aviad Rubinstein |
| 2016 | STOC | Beyond matroids: secretary problem and prophet inequality with general constraints. | Aviad Rubinstein |
| 2015 | SODA | Robust Probabilistic Inference. | Yishay Mansour, Aviad Rubinstein, Moshe Tennenholtz |
| 2015 | STOC | Inapproximability of Nash Equilibrium. | Aviad Rubinstein |
| 2014 | FOCS | Satisfiability and Evolution. | Adi Livnat, Christos H. Papadimitriou, Aviad Rubinstein, Gregory Valiant, Andrew Wan |
| 2014 | IPCO | On Simplex Pivoting Rules and Complexity Theory. | Ilan Adler, Christos H. Papadimitriou, Aviad Rubinstein |
| 2012 | ICALP | Converting Online Algorithms to Local Computation Algorithms. | Yishay Mansour, Aviad Rubinstein, Shai Vardi, Ning Xie |