Determining Sets for the Discrete Laplacian. - Aviad Rubinstein; Jacob Rubinstein; Gershon Wolansky (SIAM Rev., 2007)

Delegation of Computation without Rejection Problem from Designated Verifier CS-Proofs. - Shafi Goldwasser; Huijia Lin; Aviad Rubinstein (IACR Cryptol. ePrint Arch., 2011)

Converting Online Algorithms to Local Computation Algorithms. - Yishay Mansour; Aviad Rubinstein; Shai Vardi; Ning Xie 002 (ICALP (1), 2012)

Satisfiability and Evolution. - Adi Livnat; Christos H. Papadimitriou; Aviad Rubinstein; Andrew Wan (CoRR, 2013)

Satisfiability and Evolution. - Adi Livnat; Christos H. Papadimitriou; Aviad Rubinstein; Gregory Valiant; Andrew Wan (FOCS, 2014)

On Simplex Pivoting Rules and Complexity Theory. - Ilan Adler; Christos H. Papadimitriou; Aviad Rubinstein (IPCO, 2014)

The Intractability of Dynamic Mechanism Design. - Christos H. Papadimitriou; George Pierrakos; Christos-Alexandros Psomas; Aviad Rubinstein (CoRR, 2014)

Computational Complexity of Approximate Nash Equilibrium in Large Games. - Aviad Rubinstein (CoRR, 2014)

Combining Traditional Marketing and Viral Marketing with Amphibious Influence Maximization. - Wei Chen 013; Fu Li; Tian Lin; Aviad Rubinstein (EC, 2015)

Approximability of Adaptive Seeding under Knapsack Constraints. - Aviad Rubinstein; Lior Seeman; Yaron Singer (EC, 2015)

Robust Probabilistic Inference. - Yishay Mansour; Aviad Rubinstein; Moshe Tennenholtz (SODA, 2015)

Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash. - Yakov Babichenko; Christos H. Papadimitriou; Aviad Rubinstein (CoRR, 2015)

ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness. - Mark Braverman; Young Kun-Ko; Aviad Rubinstein; Omri Weinstein (CoRR, 2015)

On the Worst-Case Approximability of Sparse PCA. - Siu On Chan; Dimitris S. Papailiopoulos; Aviad Rubinstein (CoRR, 2015)

ETH-Hardness for Signaling in Symmetric Zero-Sum Games. - Aviad Rubinstein (CoRR, 2015)

Simple Mechanisms for a Combinatorial Buyer and Applications to Revenue Monotonicity. - Aviad Rubinstein; S. Matthew Weinberg (CoRR, 2015)

ETH Hardness for Densest-k-Subgraph with Perfect Completeness. - Mark Braverman; Young Kun-Ko; Aviad Rubinstein; Omri Weinstein (Electron. Colloquium Comput. Complex., 2015)

The complexity of simplicity in mechanism design. - Aviad Rubinstein (SIGecom Exch., 2015)

On the Approximability of Sparse PCA. - Siu On Chan; Dimitris Papailliopoulos; Aviad Rubinstein (COLT, 2016)

Can Almost Everybody be Almost Happy? - Yakov Babichenko; Christos H. Papadimitriou; Aviad Rubinstein (ITCS, 2016)

On the Computational Complexity of Optimal Simple Mechanisms. - Aviad Rubinstein (ITCS, 2016)

The Power of Optimization from Samples. - Eric Balkanski; Aviad Rubinstein; Yaron Singer (NIPS, 2016)

Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions. - Ashwinkumar Badanidiyuru; Christos H. Papadimitriou; Aviad Rubinstein; Lior Seeman; Yaron Singer (SODA, 2016)

Beyond matroids: secretary problem and prophet inequality with general constraints. - Aviad Rubinstein (STOC, 2016)

The Complexity of Fairness Through Equilibrium. - Abraham Othman; Christos H. Papadimitriou; Aviad Rubinstein (ACM Trans. Economics and Comput., 2016)

Inapproximability of VC Dimension and Littlestone's Dimension. - Pasin Manurangsi; Aviad Rubinstein (COLT, 2017)

Distributed PCP Theorems for Hardness of Approximation in P. - Amir Abboud; Aviad Rubinstein; R. Ryan Williams (FOCS, 2017)

Honest Signaling in Zero-Sum Games Is Hard, and Lying Is Even Harder. - Aviad Rubinstein (ICALP, 2017)

Detecting communities is Hard (And Counting Them is Even Harder). - Aviad Rubinstein (ITCS, 2017)

Combinatorial Prophet Inequalities. - Aviad Rubinstein; Sahil Singla 001 (SODA, 2017)

Sorting from Noisier Samples. - Aviad Rubinstein; Shai Vardi (SODA, 2017)

Distributed PCP Theorems for Hardness of Approximation in P. - Amir Abboud; Aviad Rubinstein (CoRR, 2017)

The Hunting of the SNARK. - Nir Bitansky; Ran Canetti; Alessandro Chiesa; Shafi Goldwasser; Huijia Lin; Aviad Rubinstein; Eran Tromer (J. Cryptol., 2017)

Settling the complexity of computing approximate two-player Nash equilibria. - Aviad Rubinstein (SIGecom Exch., 2017)

Hardness of Approximation Between P and NP. - Aviad Rubinstein (2017)

Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds. - Amir Abboud; Aviad Rubinstein (ITCS, 2018)

Computing Exact Minimum Cuts Without Knowing the Graph. - Aviad Rubinstein; Tselil Schramm; S. Matthew Weinberg (ITCS, 2018)

Optimal Deterministic Mechanisms for an Additive Buyer. - Moshe Babaioff; Noam Nisan; Aviad Rubinstein (EC, 2018)

99% Revenue via Enhanced Competition. - Michal Feldman; Ophir Friedler; Aviad Rubinstein (EC, 2018)

Hardness of approximate nearest neighbor search. - Aviad Rubinstein (STOC, 2018)

Near-Linear Time Insertion-Deletion Codes and (1+ε)-Approximating Edit Distance via Indexing. - Bernhard Haeupler; Aviad Rubinstein; Amirbehshad Shahrasbi (CoRR, 2018)

Inapproximability of Nash Equilibrium. - Aviad Rubinstein (SIAM J. Comput., 2018)

Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity. - Aviad Rubinstein; S. Matthew Weinberg (ACM Trans. Economics and Comput., 2018)

Hardness of Approximation Between P and NP - Aviad Rubinstein (Hardness of Approximation Between P and NP, 2019)

Approximation Algorithms for LCS and LIS with Truly Improved Running Times. - Aviad Rubinstein; Saeed Seddighin; Zhao Song 002; Xiaorui Sun (FOCS, 2019)

An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation. - Eric Balkanski; Aviad Rubinstein; Yaron Singer (SODA, 2019)

Fine-grained Complexity Meets IP = PSPACE. - Lijie Chen 001; Shafi Goldwasser; Kaifeng Lyu; Guy N. Rothblum; Aviad Rubinstein (SODA, 2019)

Near-linear time insertion-deletion codes and (1+ε)-approximating edit distance via indexing. - Bernhard Haeupler; Aviad Rubinstein; Amirbehshad Shahrasbi (STOC, 2019)

Reductions in PPP. - Frank Ban; Kamal Jain; Christos H. Papadimitriou; Christos-Alexandros Psomas; Aviad Rubinstein (Inf. Process. Lett., 2019)

SETH vs Approximation. - Aviad Rubinstein; Virginia Vassilevska Williams (SIGACT News, 2019)

Communication complexity of Nash equilibrium in potential games (extended abstract). - Yakov Babichenko; Aviad Rubinstein (FOCS, 2020)

Smoothed Complexity of 2-player Nash Equilibria. - Shant Boodaghians; Joshua Brakensiek; Samuel B. Hopkins 001; Aviad Rubinstein (FOCS, 2020)

Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria. - Kousha Etessami; Christos H. Papadimitriou; Aviad Rubinstein; Mihalis Yannakakis (ITCS, 2020)

Optimal Single-Choice Prophet Inequalities from Samples. - Aviad Rubinstein; Jack Z. Wang; S. Matthew Weinberg (ITCS, 2020)

Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics. - Aranyak Mehta; Uri Nadav; Alexandros Psomas 001; Aviad Rubinstein (NeurIPS, 2020)

Reducing approximate Longest Common Subsequence to approximate Edit Distance. - Aviad Rubinstein; Zhao Song 002 (SODA, 2020)

Constant-factor approximation of near-linear edit distance in near-linear time. - Joshua Brakensiek; Aviad Rubinstein (STOC, 2020)

Does preprocessing help in fast sequence comparisons? - Elazar Goldenberg; Aviad Rubinstein; Barna Saha (STOC, 2020)

Streaming with Oracle: New Streaming Algorithms for Edit Distance and LCS. - Alireza Farhadi 001; MohammadTaghi Hajiaghayi; Aviad Rubinstein; Saeed Seddighin (CoRR, 2020)

A Simple Sublinear Algorithm for Gap Edit Distance. - Joshua Brakensiek; Moses Charikar; Aviad Rubinstein (CoRR, 2020)

Communication complexity of Nash equilibrium in potential games. - Yakov Babichenko; Aviad Rubinstein (CoRR, 2020)

Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence. - Kuan Cheng; Alireza Farhadi 001; MohammadTaghi Hajiaghayi; Zhengzhong Jin; Xin Li 006; Aviad Rubinstein; Saeed Seddighin; Yu Zheng 014 (ICALP, 2021)

The Strongish Planted Clique Hypothesis and Its Consequences. - Pasin Manurangsi; Aviad Rubinstein; Tselil Schramm (ITCS, 2021)

Cardinality constrained submodular maximization for random streams. - Paul Liu 001; Aviad Rubinstein; Jan Vondrák; Junyao Zhao 001 (NeurIPS, 2021)

Settling the complexity of Nash equilibrium in congestion games. - Yakov Babichenko; Aviad Rubinstein (STOC, 2021)

Exponential communication separations between notions of selfishness. - Aviad Rubinstein; Raghuvansh R. Saxena; Clayton Thomas; S. Matthew Weinberg; Junyao Zhao 001 (STOC, 2021)

The randomized communication complexity of randomized auctions. - Aviad Rubinstein; Junyao Zhao 001 (STOC, 2021)

The randomized communication complexity of revenue maximization. - Aviad Rubinstein; Junyao Zhao 001 (SIGecom Exch., 2021)

Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation. - Aviad Rubinstein; Junyao Zhao 001 (ICALP, 2022)

Budget-Smoothed Analysis for Submodular Maximization. - Aviad Rubinstein; Junyao Zhao 001 (ITCS, 2022)

Communication complexity of approximate Nash equilibria. - Yakov Babichenko; Aviad Rubinstein (Games Econ. Behav., 2022)

On the complexity of dynamic mechanism design. - Christos H. Papadimitriou; George Pierrakos; Alexandros Psomas 001; Aviad Rubinstein (Games Econ. Behav., 2022)

An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model. - Eric Balkanski; Aviad Rubinstein; Yaron Singer (Oper. Res., 2022)

The Limitations of Optimization from Samples. - Eric Balkanski; Aviad Rubinstein; Yaron Singer (J. ACM, 2022)

Local Computation Algorithms for Maximum Matching: New Lower Bounds. - Soheil Behnezhad; Mohammad Roghani; Aviad Rubinstein (FOCS, 2023)

Envy-Free Cake-Cutting for Four Agents. - Alexandros Hollender; Aviad Rubinstein (FOCS, 2023)

Near Optimal Memory-Regret Tradeoff for Online Learning. - Binghui Peng; Aviad Rubinstein (FOCS, 2023)

Beyond Worst-Case Budget-Feasible Mechanism Design. - Aviad Rubinstein; Junyao Zhao 001 (ITCS, 2023)

Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI). - Eric Budish; Ruiquan Gao 001; Abraham Othman; Aviad Rubinstein; Qianfan Zhang 002 (EC, 2023)

Beating Greedy Matching in Sublinear Time. - Soheil Behnezhad; Mohammad Roghani; Aviad Rubinstein; Amin Saberi (SODA, 2023)

Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window). - Binghui Peng; Aviad Rubinstein (SOSA, 2023)

Sublinear Time Algorithms and Complexity of Approximate Maximum Matching. - Soheil Behnezhad; Mohammad Roghani; Aviad Rubinstein (STOC, 2023)

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria. - Mika Göös; Aviad Rubinstein (SIAM J. Comput., 2023)

The complexity of approximate (coarse) correlated equilibrium for incomplete information games. - Binghui Peng; Aviad Rubinstein (COLT, 2024)

Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting. - Ruiquan Gao 001; Mohammad Roghani; Aviad Rubinstein; Amin Saberi (FOCS, 2024)

Sublinear Algorithms for TSP via Path Covers. - Soheil Behnezhad; Mohammad Roghani; Aviad Rubinstein; Amin Saberi (ICALP, 2024)

Strategizing against No-Regret Learners in First-Price Auctions. - Aviad Rubinstein; Junyao Zhao 001 (EC, 2024)

Approximate Earth Mover's Distance in Truly-Subquadratic Time. - Lorenzo Beretta 001; Aviad Rubinstein (STOC, 2024)

Parallel Sampling via Counting. - Nima Anari; Ruiquan Gao 001; Aviad Rubinstein (STOC, 2024)

Approximating Maximum Matching Requires Almost Quadratic Time. - Soheil Behnezhad; Mohammad Roghani; Aviad Rubinstein (STOC, 2024)

A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations. - Shahar Dobzinski; Wenzheng Li; Aviad Rubinstein; Jan Vondrák (STOC, 2024)

Fast Swap Regret Minimization and Applications to Approximate Correlated Equilibria. - Binghui Peng; Aviad Rubinstein (STOC, 2024)

The Query Complexity of Contracts. - Paul Dütting; Michal Feldman; Yoav Gal Tzur; Aviad Rubinstein (CoRR, 2024)

A Bicriterion Concentration Inequality and Prophet Inequalities for k-Fold Matroid Unions. - Noga Alon; Nick Gravin; Tristan Pollner; Aviad Rubinstein; Hongao Wang; S. Matthew Weinberg; Qianfan Zhang 002 (CoRR, 2024)

A Bicriterion Concentration Inequality and Prophet Inequalities for k-Fold Matroid Unions. - Noga Alon; Nick Gravin; Tristan Pollner; Aviad Rubinstein; Hongao Wang; S. Matthew Weinberg; Qianfan Zhang 002 (ITCS, 2025)

Quantum Communication Complexity of Classical Auctions. - Aviad Rubinstein; Zixin Zhou (ITCS, 2025)