Adam Polak

I work as an assistant professor in the Department of Computing Sciences at Bocconi University. My research interests include algorithms and fine-grained complexity.

Prior to joining Bocconi, I worked as a postdoctoral researcher in the Algorithms and Complexity Department at the Max Planck Institute for Informatics, and in the theory group at EPFL. I finished my PhD in fall 2019, in the theory group at Jagiellonian University, advised by Paweł Idziak. In spring and summer of 2019 I was at MIT, hosted by Virginia Vassilevska Williams.

You can reach me by email at: adam dot polak at unibocconi dot it.

Publications

Jakob Nogler, Adam Polak, Barna Saha, Virginia Vassilevska Williams, Yinzhan Xu, Christopher Ye
Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
Preprint on arXiv

Bingbing Hu, Adam Polak
Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems
Preprint on arXiv

Shashwat Kasliwal, Adam Polak, Pratyush Sharma
3SUM in Preprocessed Universes: Faster and Simpler
SOSA 2025, arXiv

Karl Bringmann, Anita Dürr, Adam Polak
Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
ESA 2024 (best paper award), arXiv

Bingbing Hu, Evangelos Kosinas, Adam Polak
Connectivity Oracles for Predictable Vertex Failures
ESA 2024, slides, arXiv

Adam Polak, Maksym Zub
Learning-Augmented Maximum Flow
IPL 2024, arXiv

Nick Fischer, Piotr Kaliciak, Adam Polak
Deterministic 3SUM-Hardness
ITCS 2024, talk (by Nick), arXiv

Jan van den Brand, Sebastian Forster, Yasamin Nazari, Adam Polak
On Dynamic Graph Algorithms with Predictions
SODA 2024, arXiv

Jana Cslovjecsek, Martin Koutecký, Alexandra Lassota, Michał Pilipczuk, Adam Polak
Parameterized algorithms for block-structured integer programs with large entries
SODA 2024, arXiv

Tomasz Kociumaka, Adam Polak
Bellman-Ford is optimal for shortest hop-bounded paths
ESA 2023, slides, arXiv

Antonios Antoniadis, Christian Coester, Marek Eliáš, Adam Polak, Bertrand Simon
Mixing predictions for online metric algorithms
ICML 2023, poster, arXiv

Antonios Antoniadis, Joan Boyar, Marek Eliáš, Lene M. Favrholdt, Ruben Hoeksma, Kim S. Larsen, Adam Polak, Bertrand Simon
Paging with Succinct Predictions
ICML 2023, poster, arXiv

Kim-Manuel Klein, Adam Polak, Lars Rohwedder
On Minimizing Tardy Processing Time, Max-Min Skewed Convolution, and Triangular Structured ILPs
SODA 2023, arXiv

Alexandra Lassota, Aleksander Łukasiewicz, Adam Polak
Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs
ICALP 2022, HALG 2023 (short talk, poster), arXiv

Aaron Berger, William Kuszmaul, Adam Polak, Jonathan Tidor, Nicole Wein
Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost
ICALP 2022, slides, arXiv

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

Buddhima Gamlath, Xinrui Jia, Adam Polak, Ola Svensson
Nearly-Tight and Oblivious Algorithms for Explainable Clustering
NeurIPS 2021, poster, talk (at HIM in Bonn), arXiv

Jakub Chłędowski, Adam Polak, Bartosz Szabucki, Konrad Żołna
Robust Learning-Augmented Caching: An Experimental Study
ICML 2021, talk (by Jakub), RobustML@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), talk (at HIM in Bonn), HALG 2022 (short talk, slides, poster), arXiv

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

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), TALG 2023, arXiv

Joanna Chybowska-Sokół, Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Patryk Mikos, Adam Polak
Online Coloring of Short Intervals
APPROX 2020, talk (by Grzegorz), Eur. J. Comb. 2024, 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, slides, arXiv

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

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
VISAPP 2012

Teaching and community service

Bocconi:
- Algorithms and Data Structures (3 semesters)
MPI:
- Foundations of Machine Learning Seminar (1 semester)
EPFL:
- Fine-Grained and Parameterized Complexity (1 semester)
- Advanced Linear Algebra (1 semester)
Jagiellonian University:
- Algorithms and Data Structures (6 semesters)
- Geometric Algorithms (1 semester)
- Numerical Algorithms (1 semester)
- Parallel Programming (1 semester)
5th High School in Kraków:
- Algorithmics (6 semesters)

In May 2022 I co-organized Workshop on Algorithms with Predictions (ALPS) in Lausanne.

From 2009 to 2020 I used to organize biannual week-long algorithmics workshops for high-school students.

I served as a PC member of ESA 2023 and ICALP 2024.

I've been reviewing for Algorithmica, APPROX, DM, ESA, FOCS, ICALP, ICLR, IPCO, IPL, ISAAC, ITCS, JCSS, LATIN, MFCS, NeurIPS, Order, SoCG, SODA, SOSA, SWAT, TCS.

Programming

During my high-school and undergraduate years I enjoyed competing in programming contests. Together with Robert Obryk and Maciej Wawro we won a bronze medal at ACM ICPC World Finals in Orlando in 2011, and scored 18th place a year later in Warsaw.

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.

I used to work on computer vision side projects. In particular, I developed and implemented algorithms for:

motion analysis and cancer detection in colonoscopy videos;
automatic recognition of Flashy Shapes, optical security features based on moiré effect;
detecting and tracking people in CCTV video streams in real-time using GPU.

I also interned at Google:

in New York in 2013 (4 months), where I analysed caching algorithms in a low-level distributed file system;
in Kraków in 2012 (5 months), where I improved data freshness in a low-latency system for monitoring cluster resource utilization.

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.

I worked 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: November 2024