Aviad Rubinstein

According to our database1, Aviad Rubinstein authored at least 43 papers between 2007 and 2019.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

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

Near-linear time insertion-deletion codes and (1+ε)-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

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

The Hunting of the SNARK.
J. Cryptology, 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

ETH Hardness for Densest-k-Subgraph with Perfect Completeness.
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
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

Settling the Complexity of Computing Approximate Two-Player Nash Equilibria.
Proceedings of the IEEE 57th Annual Symposium on Foundations of 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 Exchanges, 2015

Inapproximability of Nash Equilibrium.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

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

Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity.
Proceedings of the Sixteenth ACM Conference on Economics and Computation, 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
The Hunting of the SNARK.
IACR Cryptology ePrint Archive, 2014

The complexity of fairness through equilibrium.
Proceedings of the ACM Conference on Economics and Computation, 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

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 Cryptology ePrint Archive, 2011

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


  Loading...