Manolis Zampetakis

CoRR, 2024

On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games.

[BibT_eX]

[DOI]

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

Consensus-Halving: Does It Ever Get Easier?

[BibT_eX]

[DOI]

SIAM J. Comput., April, 2023

First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems.

[BibT_eX]

[DOI]

Tianyi Lin

J. Mach. Learn. Res., 2023

Tree of Attacks: Jailbreaking Black-Box LLMs Automatically.

[BibT_eX]

[DOI]

CoRR, 2023

Sorting from Crowdsourced Comparisons using Expert Verifications.

[BibT_eX]

[DOI]

Ellen Vitercik

David Zhang

CoRR, 2023

Algorithmic Contract Design for Crowdsourced Ranking.

[BibT_eX]

[DOI]

CoRR, 2023

What Makes a Good Fisherman? Linear Regression under Self-Selection Bias.

[BibT_eX]

[DOI]

Yeshwanth Cherapanamjeri

Andrew Ilyas

Christos H. Papadimitriou

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

The Computational Complexity of Multi-player Concave Games and Kakutani Fixed Points.

[BibT_eX]

[DOI]

Emmanouil-Vasileios Vlatakis-Gkaragkounis

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

Smoothed Analysis of Online Non-parametric Auctions.

[BibT_eX]

[DOI]

Naveen Durvasula

Nika Haghtalab

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

Learning Exponential Families from Truncated Samples.

[BibT_eX]

[DOI]

Jane Lee

Andre Wibisono

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Deterministic Nonsmooth Nonconvex Optimization.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

The Computational Complexity of Finding Stationary Points in Non-Convex Optimization.

[BibT_eX]

[DOI]

Alexandros Hollender

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games.

[BibT_eX]

[DOI]

Noah Golowich

Stratis Skoulakis

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Bayesian Strategy-Proof Facility Location via Robust Estimation.

[BibT_eX]

[DOI]

Fred Zhang

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2023

2022

Analyzing data with systematic bias.

[BibT_eX]

[DOI]

SIGecom Exch., July, 2022

On the Complexity of Deterministic Nonsmooth and Nonconvex Optimization.

[BibT_eX]

[DOI]

Tianyi Lin

CoRR, 2022

Estimation of Standard Auction Models.

[BibT_eX]

[DOI]

Yeshwanth Cherapanamjeri

Andrew Ilyas

Konstantinos Stavropoulos

Proceedings of the EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11, 2022

Learning and Covering Sums of Independent Random Variables with Unbounded Support.

[BibT_eX]

[DOI]

Alkis Kalavasis

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

2021

Last-Iterate Convergence of Saddle Point Optimizers via High-Resolution Differential Equations.

[BibT_eX]

[DOI]

Tatjana Chavdarova

CoRR, 2021

The complexity of constrained min-max optimization.

[BibT_eX]

[DOI]

Stratis Skoulakis

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

A Topological Characterization of Modulo-<i>p</i> Arguments and Implications for Necklace Splitting.

[BibT_eX]

[DOI]

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

Robust Learning of Optimal Auctions.

[BibT_eX]

[DOI]

Wenshuo Guo

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

Efficient Truncated Linear Regression with Unknown Noise Variance.

[BibT_eX]

[DOI]

Patroklos Stefanou

Rui Yao

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

Private and Non-private Uniformity Testing for Ranking Data.

[BibT_eX]

[DOI]

Róbert Busa-Fekete

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

Identity testing for Mallows model.

[BibT_eX]

[DOI]

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

A Statistical Taylor Theorem and Extrapolation of Truncated Densities.

[BibT_eX]

[DOI]

Vasilis Kontonis

Proceedings of the Conference on Learning Theory, 2021

2020

A Topological Characterization of Modulo-p Arguments and Implications for Necklace Splitting.

[BibT_eX]

[DOI]

CoRR, 2020

More Revenue from Two Samples via Factor Revealing SDPs.

[BibT_eX]

[DOI]

Proceedings of the EC '20: The 21st ACM Conference on Economics and Computation, 2020

Optimal Approximation - Smoothness Tradeoffs for Soft-Max Functions.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Constant-Expansion Suffices for Compressed Sensing with Generative Priors.

[BibT_eX]

[DOI]

Dhruv Rohatgi

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Truncated Linear Regression in High Dimensions.

[BibT_eX]

[DOI]

Dhruv Rohatgi

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Estimation and Inference with Trees and Forests in High Dimensions.

[BibT_eX]

[DOI]

Vasilis Syrgkanis

Proceedings of the Conference on Learning Theory, 2020

On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem.

[BibT_eX]

[DOI]

Proceedings of the 35th Computational Complexity Conference, 2020

A Theoretical and Practical Framework for Regression and Classification from Truncated Samples.

[BibT_eX]

[DOI]

Andrew Ilyas

Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

2019

Efficient Truncated Statistics with Unknown Truncation.

[BibT_eX]

[DOI]

Vasilis Kontonis

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

Computationally and Statistically Efficient Truncated Regression.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

Optimal Learning of Mallows Block Model.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

2018

PPP-Completeness with Connections to Cryptography.

[BibT_eX]

[DOI]

Katerina Sotiraki

Giorgos Zirdelis

IACR Cryptol. ePrint Arch., 2018

A converse to Banach's fixed point theorem and its CLS-completeness.

[BibT_eX]

[DOI]

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

Efficient Statistics, in High Dimensions, from Truncated Samples.

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Certified Computation from Unreliable Datasets.

[BibT_eX]

[DOI]

Proceedings of the Conference On Learning Theory, 2018

Bootstrapping EM via Power EM and Convergence in the Naive Bayes Model.

[BibT_eX]

[DOI]

Costis Daskalakis

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2018

2017

Certified Computation in Crowdsourcing.

[BibT_eX]

[DOI]

CoRR, 2017

Faster Sublinear Algorithms using Conditional Sampling.

[BibT_eX]

[DOI]

Themistoklis Gouleakis

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

Ten Steps of EM Suffice for Mixtures of Two Gaussians.

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Learning Theory, 2017

2016

Efficient Money Burning in General Domains.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2016

Mechanism Design with Selective Verification.

[BibT_eX]

[DOI]

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

2015

Truthfulness Flooded Domains and the Power of Verification for Mechanism Design.

[BibT_eX]

[DOI]

ACM Trans. Economics and Comput., 2015

Who to Trust for Truthfully Maximizing Welfare?

[BibT_eX]

[DOI]

CoRR, 2015

Scheduling MapReduce Jobs and Data Shuffle on Unrelated Processors.

[BibT_eX]

[DOI]

Ioannis Milis

Orestis Papadigenopoulos