Aviad Rubinstein

According to our database1, Aviad Rubinstein authored at least 72 papers between 2007 and 2021.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2021
Budget-Smoothed Analysis for Submodular Maximization.
CoRR, 2021

The randomized communication complexity of randomized auctions.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Exponential communication separations between notions of selfishness.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Settling the complexity of Nash equilibrium in congestion games.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

The Strongish Planted Clique Hypothesis and Its Consequences.
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence.
Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020
Communication complexity of Nash equilibrium in potential games.
CoRR, 2020

A Simple Sublinear Algorithm for Gap Edit Distance.
CoRR, 2020

Streaming with Oracle: New Streaming Algorithms for Edit Distance and LCS.
CoRR, 2020

Does preprocessing help in fast sequence comparisons?
Proceedings of the Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Constant-factor approximation of near-linear edit distance in near-linear time.
Proceedings of the Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Reducing approximate Longest Common Subsequence to approximate Edit Distance.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Optimal Single-Choice Prophet Inequalities from Samples.
Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria.
Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Smoothed Complexity of 2-player Nash Equilibria.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Communication complexity of Nash equilibrium in potential games (extended abstract).
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019
SETH vs Approximation.
SIGACT News, 2019

Reductions in PPP.
Inf. Process. Lett., 2019

Near-linear time insertion-deletion codes and (1+<i>ε</i>)-approximating edit distance via indexing.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Fine-grained Complexity Meets IP = PSPACE.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Approximation Algorithms for LCS and LIS with Truly Improved Running Times.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Hardness of Approximation Between P and NP
ACM, ISBN: 978-1-94748-723-9, 2019

2018
Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity.
ACM Trans. Economics and Comput., 2018

Near-Linear Time Insertion-Deletion Codes and (1+ε)-Approximating Edit Distance via Indexing.
CoRR, 2018

Hardness of approximate nearest neighbor search.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

99% Revenue via Enhanced Competition.
Proceedings of the 2018 ACM Conference on Economics and Computation, 2018

Optimal Deterministic Mechanisms for an Additive Buyer.
Proceedings of the 2018 ACM Conference on Economics and Computation, 2018

Computing Exact Minimum Cuts Without Knowing the Graph.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017
Hardness of Approximation Between P and NP.
PhD thesis, 2017

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

The Hunting of the SNARK.
J. Cryptol., 2017

Distributed PCP Theorems for Hardness of Approximation in P.
CoRR, 2017

The limitations of optimization from samples.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Communication complexity of approximate Nash equilibria.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Sorting from Noisier Samples.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Combinatorial Prophet Inequalities.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Detecting communities is Hard (And Counting Them is Even Harder).
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Honest Signaling in Zero-Sum Games Is Hard, and Lying Is Even Harder.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Distributed PCP Theorems for Hardness of Approximation in P.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Inapproximability of VC Dimension and Littlestone's Dimension.
Proceedings of the 30th Conference on Learning Theory, 2017

2016
The Complexity of Fairness Through Equilibrium.
ACM Trans. Economics and Comput., 2016

Beyond matroids: secretary problem and prophet inequality with general constraints.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

On the Complexity of Dynamic Mechanism Design.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

The Power of Optimization from Samples.
Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

On the Computational Complexity of Optimal Simple Mechanisms.
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Can Almost Everybody be Almost Happy?
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

On the Approximability of Sparse PCA.
Proceedings of the 29th Conference on Learning Theory, 2016

2015
The complexity of simplicity in mechanism design.
SIGecom Exch., 2015

Inapproximability of Nash Equilibrium.
Electron. Colloquium Comput. Complex., 2015

ETH Hardness for Densest-<i>k</i>-Subgraph with Perfect Completeness.
Electron. Colloquium Comput. Complex., 2015

Simple Mechanisms for a Combinatorial Buyer and Applications to Revenue Monotonicity.
CoRR, 2015

ETH-Hardness for Signaling in Symmetric Zero-Sum Games.
CoRR, 2015

On the Worst-Case Approximability of Sparse PCA.
CoRR, 2015

ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness.
CoRR, 2015

Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash.
CoRR, 2015

Robust Probabilistic Inference.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Approximability of Adaptive Seeding under Knapsack Constraints.
Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

Combining Traditional Marketing and Viral Marketing with Amphibious Influence Maximization.
Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

2014
Computational Complexity of Approximate Nash Equilibrium in Large Games.
CoRR, 2014

The Intractability of Dynamic Mechanism Design.
CoRR, 2014

On Simplex Pivoting Rules and Complexity Theory.
Proceedings of the Integer Programming and Combinatorial Optimization, 2014

Satisfiability and Evolution.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013
Satisfiability and Evolution.
CoRR, 2013

2012
Converting Online Algorithms to Local Computation Algorithms.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011
Delegation of Computation without Rejection Problem from Designated Verifier CS-Proofs.
IACR Cryptol. ePrint Arch., 2011

2007
Determining Sets for the Discrete Laplacian.
SIAM Rev., 2007


  Loading...