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.
Buddhima Gamlath, Xinrui Jia, Adam Polak, Ola Svensson
Nearly-Tight and Oblivious Algorithms for Explainable Clustering
Preprint on arXiv
Aaron Berger, William Kuszmaul, Adam Polak, Jonathan Tidor, Nicole Wein
Algorithms and Lower Bounds for the Worker-Task Assignment Problem
Preprint on arXiv
Jakub Chłędowski, Adam Polak, Bartosz Szabucki, Konrad Żołna
Robust Learning-Augmented Caching: An Experimental Study
RobustML Workshop@ICLR 2021,
Yuzhou Gu, Adam Polak, Virginia Vassilevska Williams, Yinzhan Xu
Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths
talk (by Yuzhou),
Adam Polak, Lars Rohwedder, Karol Węgrzycki
Knapsack and Subset Sum with Small Items
talk (by Karol),
Adam Polak, Adrian Siwiec, Michał Stobierski
Euler Meets GPU: Practical Graph Algorithms with Theoretical Guarantees
Antonios Antoniadis, Christian Coester, Marek Eliáš, Adam Polak, Bertrand Simon
Online metric algorithms with untrusted predictions
talk (by Christian),
HALG 2020 (short talk),
Joanna Chybowska-Sokół, Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Patryk Mikos, Adam Polak
Online Coloring of Short Intervals
talk (by Grzegorz),
Andrea Lincoln, Adam Polak, Virginia Vassilevska Williams
Monochromatic triangles, intermediate matrix products, and convolutions
HALG 2020 (short talk, slides),
Lech Duraj, Krzysztof Kleiner, Adam Polak, Virginia Vassilevska Williams
Equivalences between triangle and range query problems
Lech Duraj, Marvin Künnemann, Adam Polak
Tight Conditional Lower Bounds for Longest Common Increasing Subsequence
Why is it hard to beat O(n^2) for Longest Common Weakly Increasing Subsequence?
HALG 2017 (poster),
Grzegorz Guśpiel, Piotr Micek, Adam Polak
On an extremal problem for poset dimension
Adam Karczmarz, Jakub Łącki, Adam Polak, Jakub Radoszewski, Jakub Onufry Wojtaszczyk
Distributed Tasks: Introducing Distributed Computing to Programming Competitions
Olympiads in Informatics 2016
Counting Triangles in Large Graphs on GPU
Maciej Chociej, Adam Polak
Real Time Object Tracking on GPGPU
Teaching and community service
- Fine-Grained and Parameterized Complexity (1 semester)
- Jagiellonian University:
- Algorithms and Data Structures (6 semesters)
- Geometric Algorithms (1 semester)
- Numerical Algorithms (1 semester)
- Parallel Programming (1 semester)
- Algorithmics for high school students at 5th High School in Kraków (2014/15, 2015/16, 2016/17)
- Organizing biannual week-long algorithmics workshops for gifted high-school students (since 2009)
- Reviewing for APPROX, DM, ESA, FOCS, ICALP, IPL, ISAAC, ITCS, JCSS, SoCG, SODA, SOSA
During my high-school and undergraduate years I enjoyed competing in programming contests. My achievements include:
- 18th place at ACM ICPC World Finals, Warsaw, 2012
- 2nd place at ACM Central Europe Regional Contest, Prague, 2011
- Bronze medal at ACM ICPC World Finals, Orlando, 2011
- 2nd place at ACM Central Europe Regional Contest, Wrocław, 2010
- Gold medal at Baltic Olympiad in Informatics, Gdynia, 2008
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 fancy working on computer vision side projects. In particular, I developed and implemented algorithms for:
motion analysis and cancer detection in colonoscopy videos;
(2014-16, 30 months, R&D grant from National Centre for Research and Development)
automatic recognition of Flashy Shapes, optical security features based on moiré effect;
(2014, 3 months, research internship at École Polytechnique Fédérale de Lausanne)
detecting and tracking people in CCTV video streams in real-time using GPU.
(2011-12, 13 months, R&D grant from Polish Ministry of Science and Higher Education)
I also interned at Google:
- in New York in 2013 (4 months), where I analysed caching algorithms in a distributed file system;
- in Kraków in 2012 (5 months), where I improved data freshness in a low-latency monitoring of 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.
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: July 2021