Marek Elias

Research interests

I study algorithms for optimization problems with uncertainty. This includes online optimization problems with uncertainty about the future as well as problems in differential privacy with intentionally added uncertainty protecting sensitive data

Working papers

Antonios Antoniadis, Christian Coester, Adam Polak, and Bertrand Simon

Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds

NeurIPS 2021

Selected Publications

Bansal N.; Elias M.; Khan A.

Improved approximation for vector bin packing

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

Bansal N.; Elias M.; Koumoutsos G.

Weighted k-server bounds via combinatorial dichotomies

Annual Symposium on Foundations of Computer Science - Proceedings, 2017

Bansal, Nikhil; Eliáš, Marek; Jeż, łukasz; Koumoutsos, Grigorios

The (h,k)-server problem on bounded depth trees

ACM TRANSACTIONS ON ALGORITHMS, 2019

Bansal, Nikhil; Eliáš, Marek; Jeż, łukasz; Koumoutsos, Grigorios; Pruhs, Kirk

Tight bounds for Double Coverage against weak adversaries

THEORY OF COMPUTING SYSTEMS, 2018

Bun, Marc; Elias, Marek; Kulkarni, Janardhan

Differentially private correlation clustering

Differentially Private Correlation Clustering, 2021

Antoniadis, Antonios; Coester, Christian; Elias, Marek; Polak, Adam; Simon, Bertrand

Learning-augmented dynamic power management with multiple states via new ski rental bounds

Advances in Neural Information Processing Systems 34, 2021

Bansal, Nikhil; Bohm, Martin; Elias, Marek; Koumoutsos, Grigorios; Umboh, Seeun William

Nested Convex Bodies are chaseable

ALGORITHMICA, 2020

Bansa, Nikhil; Eliáš, Marek; Koumoutsos, Grigorios; Nederlof, Jesper

Competitive algorithms for generalized k-server in uniform metrics

Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018

Elias, Marek; Matousek, Jiří

Higher-order Erdos-Szekeres theorems

ADVANCES IN MATHEMATICS, 2013

Elias, Marek; Matousek, Jiri; Roldan-Pensado, Edgardo; Safernova Zuzana

Lower bounds on geometric Ramsey functions

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2014

Antonios Antoniadis; Joan Boyar; Marek Elias; Lene M. Favrholdt; Ruben Hoeksma; Kim S. Larsen; Adam Polak; Bertrand Simon

Paging with Succinct Predictions

2022

Antoniadis, Antonios; Coester, Christian; Elias, Marek; Polak, Adam; Simon, Bertrand

Online metric algorithms with untrusted predictions

ACM TRANSACTIONS ON ALGORITHMS, 2023

Antoniadis, Antonios; Coester, Christian; Elias, Marek; Polak, Adam; Simon, Bertrand

Mixing predictions for online metric algorithms

Proceedings of the 40th International Conference on Machine Learning, 2023

Teaching

20591

COMPUTER PROGRAMMING AND DATABASE SYSTEMS

30553

ADVANCED PROGRAMMING AND OPTIMIZATION ALGORITHMS