[online] Algorithms seminar

Scheduled talks

Talks so far

paper talk [24.02.2021] Krzysztof Potępa

"Faster Deterministic Modular Subset Sum"

links: paper

paper talk [17.02.2021] Krzysztof Kleiner

"Equivalences between triangle and range query problems." (a SODA 2020 paper) by Lech Duraj, Krzysztof Kleiner, Adam Polak, Virginia Vassilevska Williams

links: paper

paper talk [10.02.2021] Aida Mousavifar

"Spectral Clustering Oracles in Sublinear Time" (a SODA 2021 paper ) by Grzegorz Głuch, Michael Kapralov, Silvio Lattanzi, Aida Mousavifar, Christian Sohler

paper talk [27.01.2021] Patrick Lin

"How to morph graphs of the torus" (a SODA 2021 paper) by Erin Wolf Chambers, Jeff Erickson, Patrick Lin, Salman Parsa

links: paper , video

paper talk [20.01.2021] Nikos Parotsidis

"Dynamic Algorithms for the Massively Parallel Model" (a SPAA 2019 paper) by Giuseppe F. Italiano, Silvio Lattanzi, Vahab S. Mirrokni, Nikos Parotsidis

links: paper, recording

paper talk [06.01.2021] Wojciech Nadara

"Approximating pathwidth for graphs of small treewidth" (a SODA 2021 paper) by Carla Groenland, Gwenaël Joret, Wojciech Nadara, Bartosz Walczak

links: paper, recording

paper talk [16.12.2020] Wojciech Janczewski

"Shorter Labels for Routing in Trees" (a SODA 2021 paper) by Paweł Gawrychowski, Wojciech Janczewski, Jakub Łopuszański

links: paper

paper talk [09.12.2020] Adam Karczmarz

"A Deterministic Parallel APSP Algorithm and its Applications" (a SODA 2021 paper) by Adam Karczmarz, Piotr Sankowski

links: video

paper talk [18.11.2020] Slobodan Mitrović

"Walking Randomly, Massively, and Efficiently" (a STOC 2020 paper) by Jakub Łącki, Slobodan Mitrović, Krzysztof Onak, Piotr Sankowski

links: paper, video

paper talk [11.11.2020] Matan Kraus

"An O(log^3/2 n) Parallel Time Population Protocol for Majority with O(log n) States." (a PODC 2020 paper) by Stav Ben Nun, Tsvi Kopelowitz, Matan Kraus, Ely Porat

links: paper , video

paper talk [04.11.2020] Przemysław Uznański

"Cardinality estimation using Gumbel distribution." by Aleksander Łukasiewicz and Przemysław Uznański

links: paper, video

paper talk [07.10.2020] Karol Węgrzycki

"Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max." (a STOC 2019 paper) by Karl Bringmann, Marvin Künnemann, Karol Węgrzycki

links: paper, video

paper talk [30.09.2020] Aleksander Łukasiewicz

"All-Pairs LCA in DAGs: Breaking through the O(n^2.5) barrier" (a SODA 2021 paper) by Fabrizio Grandoni, Giuseppe F. Italiano, Aleksander Łukasiewicz, Nikos Parotsidis, Przemysław Uznański

links: paper , video

paper talk [23.09.2020] Michal Dory

"Exponentially Faster Shortest Paths in the Congested Clique." (a PODC 2020 best paper) by Michal Dory, Merav Parter

links: paper, video

paper talk [09.09.2020] Guido Tagliavini Ponce

"Optimal Maximum Load on Dynamic Balls-and-Bins Games" by Michael A. Bender, Abhishek Bhattacharjee, Alex Conway, Martin Farach-Colton, Rob Johnson, William Kuszmaul, Don Porter, Guido Tagliavini Ponce, Janet Vorobyeva

links: video

paper talk [22.07.2020] Guy Even

"On dynamic dictionaries, filters, counting filters, and perfect hashing" by Ioana Bercea and Guy Even

links: video

paper talk [15.07.2020] Jakub Tarnawski

"Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints." (A SODA 2020 paper) by Janardhan Kulkarni, Shi Li, Jakub Tarnawski, Minwei Ye

links: paper, video

paper talk [08.07.2020] Tomasz Kociumaka

"Approximating text-to-pattern Hamming distances" (A STOC 2020 paper) by Timothy Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat

links: paper, video

paper talk [01.07.2020] Jukka Suomela

"Lower Bounds for Maximal Matchings and Maximal Independent Sets" (a FOCS 2019 best paper) by Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela

links: paper, video

paper talk [24.06.2020] William Kuszmaul

"Flushing Without Cascades" (a SODA 2020 paper) by Michael A. Bender, Rathish Das, Martin Farach-Colton, Rob Johnson, William Kuszmaul

links: paper

paper talk [17.06.2020] George Giakkoupis

"Optimal Time and Space Leader Election in Population Protocols" (a STOC 2020 paper) by Petra Berenbrink, George Giakkoupis, Peter Kling

links: paper

paper talk [10.06.2020] Marek Adamczyk

"Random Order Contention Resolution Schemes" (a FOCS 2018 paper) by Marek Adamczyk, Michał Włodarczyk

link: paper

paper talk [03.06.2020] Bartłomiej Dudek

"All non-trivial variants of 3-LDT are equivalent" (a STOC 2020 paper) by Bartłomiej Dudek, Paweł Gawrychowski, Tatiana Starikovskaya

link: paper

paper talk [27.05.2020] Frederik Mallmann-Trenn

"Instance-Optimality in the Noisy Value-and Comparison-Model" (a SODA 2020 paper) by Vincent Cohen-Addad, Frederik Mallmann-Trenn, Claire Mathieu

link: paper

paper talk [20.05.2020] Christian Coester

"Unbounded lower bound for k-server against weak adversaries" (a STOC 2020 paper) by Marcin Bieńkowski, Jarosław Byrka, Christian Coester, Łukasz Jeż

link: paper