## Conference Proceedings

Only publications in peer reviewed conferences are included.

- STOC 2023
A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning

I. Diakonikolas, D. Kane and C. Tzamos

55th Annual ACM Symposium on Theory of Computing, 2023 - NeurIPS 2022
Linear Label Ranking with Bounded Noise

D. Fotakis, A. Kalavasis, V. Kontonis and C. Tzamos

36th Annual Conference on Neural Information Processing Systems, 2022**Selected for Oral** - NeurIPS 2022
Perfect Sampling from Pairwise Comparisons

D. Fotakis, A. Kalavasis and C. Tzamos

36th Annual Conference on Neural Information Processing Systems, 2022 - ICML 2022
Online Learning for Min Sum Set Cover and Pandora’s Box

E. Gergatsouli and C. Tzamos

39th International Conference on Machine Learning, 2022 - ICML 2022
Learning General Halfspaces with Adversarial Label Noise via Online Gradient Descent

I. Diakonikolas, V. Kontonis, C. Tzamos and N. Zarifis

39th International Conference on Machine Learning, 2022 - COLT 2022
Learning a Single Neuron with Adversarial Label Noise via Gradient Descent

I. Diakonikolas, V. Kontonis, C. Tzamos and N. Zarifis

35th Annual Conference on Learning Theory, 2022 - COLT 2022
Clustering with Queries under Semi-Random Noise

A. Del Pia, M. Ma and C. Tzamos

35th Annual Conference on Learning Theory, 2022 - STOC 2022
Pricing Ordered Items

S. Chawla, R. Rezvan, Y. Teng and C. Tzamos

54th Annual ACM Symposium on Theory of Computing, 2022 - STOC 2022
Learning General Halfspaces with General Massart Noise under the Gaussian Distribution

I. Diakonikolas, D. Kane, V. Kontonis, C. Tzamos and N. Zarifis

54th Annual ACM Symposium on Theory of Computing, 2022 - NeurIPS 2021
Forster Decomposition and Learning Halfspaces with Noise

I. Diakonikolas, D. Kane and C. Tzamos

35th Annual Conference on Neural Information Processing Systems, 2021**Selected for Spotlight Presentation** - NeurIPS 2021
ReLU Regression with Massart Noise

I. Diakonikolas, J. Park and C. Tzamos

35th Annual Conference on Neural Information Processing Systems, 2021 - COLT 2021
Agnostic Proper Learning of Halfspaces under Gaussian Marginals

I. Diakonikolas, D. Kane, V. Kontonis, C. Tzamos and N. Zarifis

34th Annual Conference on Learning Theory, 2021 - COLT 2021
Efficient Algorithms for Learning from Coarse Labels

D. Fotakis, A. Kalavasis, V. Kontonis and C. Tzamos

34th Annual Conference on Learning Theory, 2021 - COLT 2021
A Statistical Taylor Theorem and Extrapolation of Truncated Densities

C. Daskalakis, V. Kontonis, C. Tzamos and M. Zampetakis

34th Annual Conference on Learning Theory, 2021 - COLT 2021
Boosting in the Presence of Massart Noise

I. Diakonikolas, R. Impagliazzo, D. Kane, R. Lei, J. Sorrell and C. Tzamos

34th Annual Conference on Learning Theory, 2021 - ICML 2021
On Robust Mean Estimation under Coordinate-level Corruption

Z. Liu, J. Park, T. Rekatsinas and C. Tzamos

38th International Conference on Machine Learning, 2021 - ICML 2021
Learning Online Algorithms with Distributional Advice

I. Diakonikolas, V. Kontonis, C. Tzamos, A. Vakilian and N. Zarifis

38th International Conference on Machine Learning, 2021 - STOC 2021
A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise

I. Diakonikolas, D. Kane, V. Kontonis, C. Tzamos and N. Zarifis

53rd Annual ACM Symposium on Theory of Computing, 2021 - STOC 2021
Learning Halfspaces with Tsybakov Noise

I. Diakonikolas, V. Kontonis, C. Tzamos and N. Zarifis

53rd Annual ACM Symposium on Theory of Computing, 2021

(Conference version merged with paper above.) - SOSA 2021
Fast and Simple Modular Subset Sum

K. Axiotis, A. Backurs, K. Bringmann, C. Jin, V. Nakos, C. Tzamos and H. Wu

4th Symposium on Simplicity in Algorithms, 2021 - NeurIPS 2020
Optimal Private Median Estimation under Minimal Distributional Assumptions

C. Tzamos, E. Vlatakis and I. Zadik

34th Annual Conference on Neural Information Processing Systems, 2020**Selected for Spotlight Presentation** - NeurIPS 2020
Non-Convex SGD Learns Halfspaces with Adversarial Label Noise

I. Diakonikolas, V. Kontonis, C. Tzamos and N. Zarifis

34th Annual Conference on Neural Information Processing Systems, 2020 - FOCS 2020
Pandora's Box with Correlations: Learning and Approximation

S. Chawla, E. Gergatsouli, Y. Teng, C. Tzamos and R. Zhang

61st Annual IEEE Symposium on Foundations of Computer Science, 2020 - EC 2020
Menu-size Complexity and Revenue Continuity of Buy-many Mechanisms

S. Chawla, Y. Teng and C. Tzamos

21st ACM Conference on Economics and Computation, 2020 - COLT 2020
Efficient Parameter Estimation of Truncated Boolean Product Distributions

D. Fotakis, A. Kalavasis and C. Tzamos

33rd Annual Conference on Learning Theory, 2020 - COLT 2020
Learning Halfspaces with Massart Noise Under Structured Distributions

I. Diakonikolas, V. Kontonis, C. Tzamos and N. Zarifis

33rd Annual Conference on Learning Theory, 2020 - ICML 2020
Black-box Methods for Restoring Monotonicity

E. Gergatsouli, B. Lucier and C. Tzamos

37th International Conference on Machine Learning, 2020 - NeurIPS 2019
Distribution-Independent PAC Learning of Halfspaces with Massart Noise

I. Diakonikolas, T. Gouleakis and C. Tzamos

33rd Annual Conference on Neural Information Processing Systems, 2019**Outstanding Paper Award** - FOCS 2019
Efficient Truncated Statistics with Unknown Truncation

V. Kontonis, C. Tzamos and M. Zampetakis

60th Annual IEEE Symposium on Foundations of Computer Science, 2019 - EC 2019
Buy-Many Mechanisms are Not Much Better than Item Pricing

S. Chawla, Y. Teng and C. Tzamos

20th ACM Conference on Economics and Computation, 2019 - EC 2019
The Complexity of Black-Box Mechanism Design with Priors

E. Gergatsouli, B. Lucier and C. Tzamos

20th ACM Conference on Economics and Computation, 2019 - COLT 2019
Computationally and Statistically Efficient Truncated Regression

C. Daskalakis, T. Gouleakis, C. Tzamos and M. Zampetakis

32nd Annual Conference on Learning Theory, 2019 - COLT 2019
Learning to Prune: Speeding up Repeated Computations

D. Alabi, A. Kalai, K. Ligett, C. Musco, C. Tzamos and E. Vitercik

32nd Annual Conference on Learning Theory, 2019 - ICALP 2019
Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms

K. Axiotis and C. Tzamos

46th Int'l Colloquium on Automata, Languages and Programming, 2019 - WebConf 2019
Diversity and Exploration in Social Learning

N. Immorlica, J. Mao and C. Tzamos

Web Conference on World Wide Web (WWW), 2019 - SODA 2019
Anaconda: A Non-Adaptive Conditional Sampling Algorithm

G. Kamath and C. Tzamos

30th ACM-SIAM Symposium on Discrete Algorithms, 2019 - SODA 2019
Fast Modular Subset Sum using Linear Sketching

K. Axiotis, A. Backurs, C. Jin, C. Tzamos and H. Wu

30th ACM-SIAM Symposium on Discrete Algorithms, 2019 - WINE 2018
Combinatorial Assortment Optimization

N. Immorlica, B. Lucier, J. Mao, V. Syrgkanis and C. Tzamos

14th Conference on Web and Internet Economics, 2018 - FOCS 2018
Efficient Statistics, in High Dimensions, from Truncated Samples

C. Daskalakis, T. Gouleakis, C. Tzamos and M. Zampetakis

59th Annual IEEE Symposium on Foundations of Computer Science, 2018 - COLT 2018
Actively Avoiding Nonsense in Generative Models

S. Hanneke, A. Kalai, G. Kamath and C. Tzamos

31st Annual Conference on Learning Theory, 2018 - COLT 2018
Computing with Unreliable Datasets

T. Gouleakis, C. Tzamos and M. Zampetakis

31st Annual Conference on Learning Theory, 2018 - STOC 2018
A Converse to Banach’s Fixed Point Theorem and its CLS Completeness

C. Daskalakis, C. Tzamos and M. Zampetakis

50th Annual ACM Symposium on Theory of Computing, 2018 - AISTATS 2018
Bootstrapping EM via Power EM and Convergence in the Naive Bayes Model

C. Daskalakis, C. Tzamos and M. Zampetakis

21st International Conference on Artificial Intelligence and Statistics, 2018 - COLT 2017
Ten Steps of EM Suffice for Mixtures of Two Gaussians

C. Daskalakis, C. Tzamos and M. Zampetakis

30th Annual Conference on Learning Theory, 2017

Preliminary version in NIPS 2016 Workshop on Non-Convex Optimization for Machine Learning. - ICML 2017
Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms

A. Backurs and C. Tzamos

34th International Conference on Machine Learning, 2017 - SODA 2017
Faster Sublinear Algorithms using Conditional Sampling

T. Gouleakis, C. Tzamos and M. Zampetakis

28th ACM-SIAM Symposium on Discrete Algorithms, 2017 - EC 2016
Does Information Revelation Improve Revenue?

C. Daskalakis, C. Papadimitriou and C. Tzamos

17th ACM Conference on Economics and Computation, 2016 - EC 2016
Mechanism Design with Selective Verification

D. Fotakis, C. Tzamos and M. Zampetakis

17th ACM Conference on Economics and Computation, 2016 - ICALP 2016
Tight Hardness Results for Maximum Weight Rectangles

A. Backurs, N. Dikkala and C. Tzamos

43rd Int'l Colloquium on Automata, Languages and Programming, 2016 - WINE 2016
Anonymous Auctions Maximizing Revenue

C. Tzamos and C. A. Wilkens

12th Conference on Web and Internet Economics, 2016 - STOC 2016
A Size-Free CLT for Poisson Multinomials and its Applications

C. Daskalakis, A. De, G. Kamath and C. Tzamos

48th Annual ACM Symposium on Theory of Computing, 2016 - FOCS 2015
On the Structure, Covering, and Learning of Poisson Multinomial Distributions

C. Daskalakis, G. Kamath and C. Tzamos

56th Annual IEEE Symposium on Foundations of Computer Science, 2015 - EC 2015
Strong Duality for a Multiple-Good Monopolist

C. Daskalakis, A. Deckelbaum and C. Tzamos

16th ACM Conference on Economics and Computation, 2015 - L@S 2015
Game Theory based Peer Grading Mechanisms for MOOCs

C. Daskalakis, N. Kaashoek, C. Tzamos, M. Weinberg and W. Wu

2nd ACM Conference on Learning at Scale, 2015 - SAGT 2015
Efficient Money Burning in General Domains

D. Fotakis, D. Tsipras, C. Tzamos and M. Zampetakis

8th International Symposium on Algorithmic Game Theory, 2015 - SODA 2014
The Complexity of Optimal Mechanism Design

C. Daskalakis, A. Deckelbaum and C. Tzamos

25th ACM-SIAM Symposium on Discrete Algorithms, 2014 - EC 2013
Mechanism Design via Optimal Transport

C. Daskalakis, A. Deckelbaum and C. Tzamos

14th ACM Conference on Economics and Computation, 2013**Best Paper and Best Student Paper Award** - EC 2013
Strategyproof Facility Location for Concave Cost Functions

D. Fotakis and C. Tzamos

14th ACM Conference on Economics and Computation, 2013 - ICALP 2013
On the Power of Deterministic Mechanisms for Facility Location Games

D. Fotakis and C. Tzamos

40th Int'l Colloquium on Automata, Languages and Programming, 2013 - WINE 2012
Optimal Pricing is Hard

C. Daskalakis, A. Deckelbaum and C. Tzamos

8th Conference on Web and Internet Economics, 2012 - WINE 2010
Winner-Imposing Strategyproof Mechanisms for Multiple Facility Location Games

D. Fotakis and C. Tzamos

6th Conference on Web and Internet Economics, 2010

## Journal Articles

- Algorithmica 2022
Efficient Parameter Estimation of Truncated Boolean Product Distributions

D. Fotakis, A. Kalavasis and C. Tzamos

Algorithmica 84(1): 2186–2221, 2022 - TEAC 2021
Combinatorial Assortment Optimization

N. Immorlica, B. Lucier, J. Mao, V. Syrgkanis and C. Tzamos

ACM Transactions on Economics and Computation 9(1): 5:1-5:34, 2021 - TEAC 2020
The Complexity of Black-Box Mechanism Design with Priors

E. Gergatsouli, B. Lucier and C. Tzamos

ACM Transactions on Economics and Computation 8(4): 20:1-20:19, 2020 - SIGecom 2020
Buy-many mechanisms: what are they and why should you care?

S. Chawla, Y. Teng and C. Tzamos

SIGecom Exchanges 18(1): 12-18, 2020 - MS 2019
Design and Dynamic Pricing of Vertically Differentiated Inventories

I. Stamatopoulos and C. Tzamos

Management Science, 2019 - Econometrica 2017
Strong Duality for a Multiple-Good Monopolist

C. Daskalakis, A. Deckelbaum and C. Tzamos

Econometrica 85(3): 735-767, 2017 - Algorithmica 2016
Strategyproof Facility Location for Concave Cost Functions

D. Fotakis and C. Tzamos

Algorithmica 76(1): 143-167, 2016 - ToCS 2016
Efficient Money Burning in General Domains

D. Fotakis, D. Tsipras, C. Tzamos and M. Zampetakis

Theory of Computing Systems 59(4): 619-640, 2016**Special Issue for SAGT 2015. Invited.** - TEAC 2014
On the Power of Deterministic Mechanisms for Facility Location Games

D. Fotakis and C. Tzamos

ACM Transactions on Economics and Computation 2(4): 15:1-15:37, 2014 - TCS 2013
Winner-Imposing Strategyproof Mechanisms for Multiple Facility Location Games

D. Fotakis and C. Tzamos

Theoretical Computer Science 472: 90-103, 2013