Aviad Rubinstein

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Approximating Maximum Matching Requires Almost Quadratic Time.

[BibT_eX]

[DOI]

Soheil Behnezhad

Mohammad Roghani

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Parallel Sampling via Counting.

[BibT_eX]

[DOI]

Nima Anari

Ruiquan Gao

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Approximate Earth Mover's Distance in Truly-Subquadratic Time.

[BibT_eX]

[DOI]

Lorenzo Beretta

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Strategizing against No-Regret Learners in First-Price Auctions.

[BibT_eX]

[DOI]

Proceedings of the 25th ACM Conference on Economics and Computation, 2024

Sublinear Algorithms for TSP via Path Covers.

[BibT_eX]

[DOI]

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting.

[BibT_eX]

[DOI]

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

The complexity of approximate (coarse) correlated equilibrium for incomplete information games.

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

2023

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria.

[BibT_eX]

[DOI]

Mika Göös

SIAM J. Comput., December, 2023

Quantum Communication Complexity of Classical Auctions.

[BibT_eX]

[DOI]

Zixin Zhou

CoRR, 2023

Sublinear Time Algorithms and Complexity of Approximate Maximum Matching.

[BibT_eX]

[DOI]

Soheil Behnezhad

Mohammad Roghani

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window).

[BibT_eX]

[DOI]

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Beating Greedy Matching in Sublinear Time.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI).

[BibT_eX]

[DOI]

Proceedings of the 24th ACM Conference on Economics and Computation, 2023

Beyond Worst-Case Budget-Feasible Mechanism Design.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Near Optimal Memory-Regret Tradeoff for Online Learning.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Envy-Free Cake-Cutting for Four Agents.

[BibT_eX]

[DOI]

Alexandros Hollender

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Local Computation Algorithms for Maximum Matching: New Lower Bounds.

[BibT_eX]

[DOI]

Soheil Behnezhad

Mohammad Roghani

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

The Limitations of Optimization from Samples.

[BibT_eX]

[DOI]

J. ACM, 2022

An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model.

[BibT_eX]

[DOI]

Oper. Res., 2022

On the complexity of dynamic mechanism design.

[BibT_eX]

[DOI]

George Pierrakos

Alexandros Psomas

Games Econ. Behav., 2022

Communication complexity of approximate Nash equilibria.

[BibT_eX]

[DOI]

Games Econ. Behav., 2022

Budget-Smoothed Analysis for Submodular Maximization.

[BibT_eX]

[DOI]

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

The randomized communication complexity of revenue maximization.

[BibT_eX]

[DOI]

SIGecom Exch., 2021

The randomized communication complexity of randomized auctions.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Exponential communication separations between notions of selfishness.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Settling the complexity of Nash equilibrium in congestion games.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Cardinality constrained submodular maximization for random streams.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

The Strongish Planted Clique Hypothesis and Its Consequences.

[BibT_eX]

[DOI]

Pasin Manurangsi

Tselil Schramm

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence.

[BibT_eX]

[DOI]

Kuan Cheng

Alireza Farhadi

MohammadTaghi Hajiaghayi

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

Communication complexity of Nash equilibrium in potential games.

[BibT_eX]

[DOI]

CoRR, 2020

A Simple Sublinear Algorithm for Gap Edit Distance.

[BibT_eX]

[DOI]

Joshua Brakensiek

Moses Charikar

CoRR, 2020

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

[BibT_eX]

[DOI]

Alireza Farhadi

MohammadTaghi Hajiaghayi

Saeed Seddighin

CoRR, 2020

Does preprocessing help in fast sequence comparisons?

[BibT_eX]

[DOI]

Elazar Goldenberg

Barna Saha

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Constant-factor approximation of near-linear edit distance in near-linear time.

[BibT_eX]

[DOI]

Joshua Brakensiek

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Reducing approximate Longest Common Subsequence to approximate Edit Distance.

[BibT_eX]

[DOI]

Zhao Song

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Jack Z. Wang

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria.

[BibT_eX]

[DOI]

Kousha Etessami

Mihalis Yannakakis

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Smoothed Complexity of 2-player Nash Equilibria.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Communication complexity of Nash equilibrium in potential games (extended abstract).

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

SETH vs Approximation.

[BibT_eX]

[DOI]

Virginia Vassilevska Williams

SIGACT News, 2019

Reductions in PPP.

[BibT_eX]

[DOI]

Frank Ban

Kamal Jain

Christos-Alexandros Psomas

Inf. Process. Lett., 2019

Near-linear time insertion-deletion codes and (1+<i>ε</i>)-approximating edit distance via indexing.

[BibT_eX]

[DOI]

Bernhard Haeupler

Amirbehshad Shahrasbi

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Fine-grained Complexity Meets IP = PSPACE.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Approximation Algorithms for LCS and LIS with Truly Improved Running Times.

[BibT_eX]

[DOI]

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Hardness of Approximation Between P and NP

[BibT_eX]

[DOI]

ACM Books 24, ACM, ISBN: 978-1-94748-723-9, 2019

2018

Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity.

[BibT_eX]

[DOI]

ACM Trans. Economics and Comput., 2018

Inapproximability of Nash Equilibrium.

[BibT_eX]

[DOI]

SIAM J. Comput., 2018

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

[BibT_eX]

[DOI]

Bernhard Haeupler

Amirbehshad Shahrasbi

CoRR, 2018

Hardness of approximate nearest neighbor search.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

99% Revenue via Enhanced Competition.

[BibT_eX]

[DOI]

Michal Feldman

Ophir Friedler

Proceedings of the 2018 ACM Conference on Economics and Computation, 2018

Optimal Deterministic Mechanisms for an Additive Buyer.

[BibT_eX]

[DOI]

Moshe Babaioff

Noam Nisan

Proceedings of the 2018 ACM Conference on Economics and Computation, 2018

Computing Exact Minimum Cuts Without Knowing the Graph.

[BibT_eX]

[DOI]

Tselil Schramm

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.

[BibT_eX]

[DOI]

Amir Abboud

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017

Hardness of Approximation Between P and NP.

[BibT_eX]

[DOI]

PhD thesis, 2017

Settling the complexity of computing approximate two-player Nash equilibria.

[BibT_eX]

[DOI]

SIGecom Exch., 2017

The Hunting of the SNARK.

[BibT_eX]

[DOI]

J. Cryptol., 2017

Distributed PCP Theorems for Hardness of Approximation in P.

[BibT_eX]

[DOI]

Amir Abboud

CoRR, 2017

Sorting from Noisier Samples.

[BibT_eX]

[DOI]

Shai Vardi

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Combinatorial Prophet Inequalities.

[BibT_eX]

[DOI]

Sahil Singla

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Detecting communities is Hard (And Counting Them is Even Harder).

[BibT_eX]

[DOI]

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Honest Signaling in Zero-Sum Games Is Hard, and Lying Is Even Harder.

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Distributed PCP Theorems for Hardness of Approximation in P.

[BibT_eX]

[DOI]

Amir Abboud

R. Ryan Williams

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Inapproximability of VC Dimension and Littlestone's Dimension.

[BibT_eX]

[DOI]

Pasin Manurangsi

Proceedings of the 30th Conference on Learning Theory, 2017

2016

The Complexity of Fairness Through Equilibrium.

[BibT_eX]

[DOI]

Abraham Othman

ACM Trans. Economics and Comput., 2016

Beyond matroids: secretary problem and prophet inequality with general constraints.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions.

[BibT_eX]

[DOI]

Ashwinkumar Badanidiyuru

Lior Seeman

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

The Power of Optimization from Samples.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Can Almost Everybody be Almost Happy?

[BibT_eX]

[DOI]

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

On the Approximability of Sparse PCA.

[BibT_eX]

[DOI]

Siu On Chan

Dimitris Papailliopoulos

Proceedings of the 29th Conference on Learning Theory, 2016

2015

The complexity of simplicity in mechanism design.

[BibT_eX]

[DOI]

SIGecom Exch., 2015

ETH Hardness for Densest-<i>k</i>-Subgraph with Perfect Completeness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

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

[BibT_eX]

[DOI]

CoRR, 2015

ETH-Hardness for Signaling in Symmetric Zero-Sum Games.

[BibT_eX]

[DOI]

Dimitris S. Papailiopoulos

CoRR, 2015

On the Worst-Case Approximability of Sparse PCA.

[BibT_eX]

[DOI]

Siu On Chan

CoRR, 2015

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

[BibT_eX]

[DOI]

CoRR, 2015

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

[BibT_eX]

[DOI]

CoRR, 2015

Robust Probabilistic Inference.

[BibT_eX]

[DOI]

Yishay Mansour

Moshe Tennenholtz

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Approximability of Adaptive Seeding under Knapsack Constraints.

[BibT_eX]

[DOI]

Lior Seeman

Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

Combining Traditional Marketing and Viral Marketing with Amphibious Influence Maximization.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

2014

Computational Complexity of Approximate Nash Equilibrium in Large Games.

[BibT_eX]

[DOI]

CoRR, 2014

The Intractability of Dynamic Mechanism Design.

[BibT_eX]

[DOI]

Christos-Alexandros Psomas

George Pierrakos

CoRR, 2014

On Simplex Pivoting Rules and Complexity Theory.

[BibT_eX]

[DOI]

Ilan Adler

Proceedings of the Integer Programming and Combinatorial Optimization, 2014

Satisfiability and Evolution.

[BibT_eX]

[DOI]

Adi Livnat

Gregory Valiant

Andrew Wan

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Satisfiability and Evolution.

[BibT_eX]

[DOI]

Adi Livnat

Andrew Wan

CoRR, 2013

2012

Converting Online Algorithms to Local Computation Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

Delegation of Computation without Rejection Problem from Designated Verifier CS-Proofs.

[BibT_eX]

[DOI]

Shafi Goldwasser

Huijia Lin

IACR Cryptol. ePrint Arch., 2011

2007

Determining Sets for the Discrete Laplacian.

[BibT_eX]

[DOI]