Adam Polak

I am a postdoctoral researcher in the Theoretical Computer Science group at EPFL, hosted by Friedrich Eisenbrand. My research interests include algorithms and fine-grained complexity.

In spring and summer 2019 I was at MIT, hosted by Virginia Vassilevska Williams, and funded by Etiuda fellowship of National Science Centre of Poland. I finished my PhD in 2019, in the Theoretical Computer Science group at Jagiellonian University, advised by Paweł Idziak.

You can reach me by email at: firstname dot lastname at epfl dot ch.


Aaron Berger, William Kuszmaul, Adam Polak, Jonathan Tidor, Nicole Wein
Algorithms and Lower Bounds for the Worker-Task Assignment Problem
Preprint on arXiv

Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, Bertrand Simon
Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds
NeurIPS 2021

Buddhima Gamlath, Xinrui Jia, Adam Polak, Ola Svensson
Nearly-Tight and Oblivious Algorithms for Explainable Clustering
NeurIPS 2021, arXiv

Jakub Chłędowski, Adam Polak, Bartosz Szabucki, Konrad Żołna
Robust Learning-Augmented Caching: An Experimental Study
ICML 2021, RobustML Workshop@ICLR 2021, arXiv

Yuzhou Gu, Adam Polak, Virginia Vassilevska Williams, Yinzhan Xu
Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths
ICALP 2021, talk (by Yuzhou), arXiv

Adam Polak, Lars Rohwedder, Karol Węgrzycki
Knapsack and Subset Sum with Small Items
ICALP 2021, talk (by Karol), arXiv

Adam Polak, Adrian Siwiec, Michał Stobierski
Euler Meets GPU: Practical Graph Algorithms with Theoretical Guarantees
IPDPS 2021, arXiv, slides

Antonios Antoniadis, Christian Coester, Marek Eliáš, Adam Polak, Bertrand Simon
Online metric algorithms with untrusted predictions
ICML 2020, talk (by Christian), HALG 2020 (short talk), arXiv

Joanna Chybowska-Sokół, Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Patryk Mikos, Adam Polak
Online Coloring of Short Intervals
APPROX 2020, talk (by Grzegorz), arXiv

Andrea Lincoln, Adam Polak, Virginia Vassilevska Williams
Monochromatic triangles, intermediate matrix products, and convolutions
ITCS 2020, slides, talk, HALG 2020 (short talk, slides), arXiv

Lech Duraj, Krzysztof Kleiner, Adam Polak, Virginia Vassilevska Williams
Equivalences between triangle and range query problems
SODA 2020, arXiv, slides

Lech Duraj, Marvin Künnemann, Adam Polak
Tight Conditional Lower Bounds for Longest Common Increasing Subsequence
Algorithmica 2019, IPEC 2017, arXiv, slides

Adam Polak
Why is it hard to beat O(n^2) for Longest Common Weakly Increasing Subsequence?
IPL 2018, HALG 2017 (poster), arXiv

Grzegorz Guśpiel, Piotr Micek, Adam Polak
On an extremal problem for poset dimension
Order 2018, arXiv

Adam Karczmarz, Jakub Łącki, Adam Polak, Jakub Radoszewski, Jakub Onufry Wojtaszczyk
Distributed Tasks: Introducing Distributed Computing to Programming Competitions
Olympiads in Informatics 2016

Adam Polak
Counting Triangles in Large Graphs on GPU
IPDPSW 2016, arXiv

Maciej Chociej, Adam Polak
Real Time Object Tracking on GPGPU

Teaching and community service

Competitive programming

During my high-school and undergraduate years I enjoyed competing in programming contests. My achievements include:

Since I retired, I've been preparing problems for various contests, including ACM CERC, Google Code Jam, Polish Collegiate Programming Contest (AMPPZ), and Polish Olympiad in Informatics.

Applied informatics

I fancy working on computer vision side projects. In particular, I developed and implemented algorithms for:

I also interned at Google:

While teaching algorithms courses, I developed tools for problem preparation and plagiarism detection in Satori, a system for automatic grading of programming assignments.

Together with Krzysztof Maziarz, we implemented FPT algorithms for Steiner tree with few terminals, and won 2nd place in PACE 2018 Challenge.

For a year and a half I collaborated on route planning algorithms with Teroplan, the company behind E-podróżnik (bus and train timetable) and Hoper (door-to-door intercity rides).

Last update: October 2021