Aviad Rubinstein
According to our database^{1},
Aviad Rubinstein
authored at least 43 papers
between 2007 and 2019.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at dl.acm.org
On csauthors.net:
Bibliography
2019
Reductions in PPP.
Inf. Process. Lett., 2019
Nearlinear time insertiondeletion 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
Finegrained Complexity Meets IP = PSPACE.
Proceedings of the Thirtieth Annual ACMSIAM Symposium on Discrete Algorithms, 2019
An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation.
Proceedings of the Thirtieth Annual ACMSIAM 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
NearOptimal 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 TwentyEighth Annual ACMSIAM Symposium on Discrete Algorithms, 2017
Combinatorial Prophet Inequalities.
Proceedings of the TwentyEighth Annual ACMSIAM Symposium on Discrete Algorithms, 2017
ETH Hardness for DensestkSubgraph with Perfect Completeness.
Proceedings of the TwentyEighth Annual ACMSIAM 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 ZeroSum 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 TwentySeventh Annual ACMSIAM Symposium on Discrete Algorithms, 2016
Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions.
Proceedings of the TwentySeventh Annual ACMSIAM 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 TwoPlayer 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 FortySeventh Annual ACM on Symposium on Theory of Computing, 2015
Robust Probabilistic Inference.
Proceedings of the TwentySixth Annual ACMSIAM 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 CSProofs.
IACR Cryptology ePrint Archive, 2011
2007
Determining Sets for the Discrete Laplacian.
SIAM Review, 2007