HIGHLIGHTS OF ALGORITHMS

ETH Zurich, Aug 31 to Sept 2, 2020


All times are according to local time in Zurich, i.e., the Central European Summer Time.

Tuesday, September 1

Session I (10 papers)

09:45-09:48 Debarati Das, Tomasz Kociumaka, Marvin Kunnemann, Yannic Maus - Welcome and Technical Announcements.

09:49-09:52 Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann - Almost Optimal Distance Oracles for Planar Graphs. [paper] [arXiv]

09:53-09:56 Kshitij Gajjar, Jaikumar Radhakrishnan - Parametric Shortest Paths in Planar Graphs. [paper] [arXiv] [video]

09:57-10:00 Laurent Feuilloley, Pierre Fraigniaud, Ivan Rapaport, Ioan Todinca, Eric Remila, Pedro Montealegre - Compact Distributed Certification of Planar Graphs. [paper] [arXiv] [video]

10:01-10:04 Andrea Lincoln, Adam Polak, Virginia Vassilevska Williams - Monochromatic Triangles, Intermediate Matrix Products, and Convolutions. [paper] [video]

10:05-10:08 Karl Bringmann, Marvin Kunnemann, Karol Wegrzycki - Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max. [paper] [arXiv]

10:09-10:12 Amir Abboud, Robert Krauthgamer, Ohad Trabelsi - Cut-Equivalent Trees are Optimal for Min-Cut Queries. [paper]

10:13-10:16 Sagnik Mukhopadhyay, Danupon Nanongkai - Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms. [paper] [arXiv] [video]

10:17-10:20 Artur Czumaj, Peter Davies, Merav Parter - Simple, Deterministic, Constant-Round Coloring in the Congested Clique. [paper] [video]

10:21-10:24 Yannic Maus, Tigran Tonoyan - Local Conflict Coloring Revisited: Linial for Lists. [arXiv]

10:25-10:28 Keren Censor-Hillel, Mikael Rabie - Distributed Reconfiguration of Maximal Independent Sets. [paper] [arXiv]


Session II (11 papers)

10:45-10:48 Evangelos Kipouridis, Kostas Tsichlas - Longest Common Subsequence on Weighted Sequences. [paper] [arXiv] [video]

10:49-10:52 Panagiotis Charalampopoulos, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen, Wiktor Zuba - The Number of Repetitions in 2D-Strings. [paper] [arXiv] [video]

10:53-10:56 Thomas Kesselheim, Sahil Singla - Online Learning with Vector Costs and Bandits with Knapsacks. [paper] [video]

10:57-11:00 Domagoj Bradac, Anupam Gupta, Sahil Singla, Goran Zuzic - Robust Algorithms for the Secretary Problem. [paper] [arXiv]

11:01-11:04 Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, Bertrand Simon - Online metric algorithms with untrusted predictions. [paper] [arXiv] [video]

11:05-11:08 Aris Filos-Ratsikas, Yiannis Giannakopoulos, Philip Lazos - The Pareto Frontier of Inefficiency in Mechanism Design. [paper] [arXiv]

11:09-11:12 Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos, Paul Spirakis - Approximating the Existential Theory of the Reals. [paper] [arXiv] [video]

11:13-11:16 Haotian Jiang, Jian Li, Daogao Liu, Sahil Singla - Algorithms and Adaptivity Gaps for Stochastic k-TSP. [paper] [arXiv]

11:17-11:20 Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Philipp Loick - Optimal group testing. [paper] [arXiv] [video]

11:21-11:24 Sitan Chen, Jerry Li, Zhao Song - Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments. [paper] [arXiv] [video]

11:25-11:28 Jan van den Brand - A Deterministic Linear Program Solver in Current Matrix Multiplication Time. [paper] [arXiv]



Wednesday, September 2

Session III (12 papers)

09:45-09:48 Marcin Bienkowski, Jaroslaw Byrka, Christian Coester, Lukasz Jez - Unbounded Lower Bound for k-Server against Weak Adversaries. [paper] [arXiv] [video]

09:49-09:52 Susanne Albers, Arindam Khan, Leon Ladewig - Online Knapsack and Related Problems in the Random Order Model. [paper]

09:53-09:56 Susanne Albers, Maximilian Janke - Scheduling in the Random-Order Model. [paper] [arXiv] [video]

09:57-10:00 Franziska Eberle, Nicole Megow, Kevin Schewior - Optimally handling commitment issues in online throughput maximization. [paper] [video]

10:01-10:04 David Adjiashvili, Felix Hommelsheim, Moritz Muehlenthaler - Flexible Graph Connectivity: Approximating Network Design Problems Between 1- and 2-connectivity. [paper] [arXiv] [video]

10:05-10:08 Alexander Goke, Daniel Marx, Matthias Mnich - Hitting long directed cycles is fixed-parameter tractable. [paper] [arXiv] [video]

10:09-10:12 Marco Bressan - Faster algorithms for counting subgraphs in sparse graphs. [paper] [arXiv]

10:13-10:16 Sandor Kisfaludi-Bak - Hyperbolic intersection graphs and (quasi)-polynomial time. [paper] [arXiv]

10:17-10:20 Amer Krivosija, Alexander Munteanu - Probabilistic smallest enclosing ball in high dimensions. [paper] [arXiv] [video]

10:21-10:24 Karl Bringmann, Marvin Kunnemann, Andre Nusser - When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Frechet Distance under Translation. [paper] [arXiv]

10:25-10:28 Arpitha P. Bharathi, Monaldo Mastrolilli - Ideal Membership Problem and a Majority Polymorphism Over the Ternary Domain. [paper] [video]

10:29-10:32 Shant Boodaghians, Federico Fusco, Philip Lazos, Stefano Leonardi - Pandora's Box Problem with Order Constraints. [paper] [arXiv]


Session IV (11 papers)

10:45-10:48 Prosenjit Bose, Jean Cardinal, John Iacono, Grigorios Koumoutsos, Stefan Langerman - Competitive Online Search Trees on Trees. [paper] [arXiv] [video]

10:49-10:52 Nicole Megow, Lukas Nolke - Online Minimum Cost Matching with Recourse on the Line. [paper] [arXiv] [video]

10:53-10:56 Dimitris Fotakis, Loukas Kavouras, Grigoris Koumoutsos, Stratis Skoulakis , Manolis Vardas - The Online Min-Sum Set Cover Problem. [paper] [arXiv] [video]

10:57-11:00 Nikhil Bansal, Haotian Jiang, Sahil Singla, Makrand Sinha - Online Vector Balancing and Geometric Discrepancy. [paper] [arXiv] [video]

11:01-11:04 Jakub Lacki, Slobodan Mitrovic, Krzysztof Onak, Piotr Sankowski - Walking Randomly, Massively, and Efficiently. [paper] [arXiv] [video]

11:05-11:08 Shay Kutten, William K. Moses Jr., Gopal Pandurangan, David Peleg - Singularly Optimal Randomized Leader Election. [arXiv]

11:09-11:12 Fabien Dufoulon, Janna Burman, Joffroy Beauquier - Can Uncoordinated Beeps tell Stories?. [paper] [video]

11:13-11:16 Vincent Cohen-Addad, Andreas Emil Feldmann, David Saulpic - Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics. [paper] [arXiv] [video]

11:17-11:20 Xinrui Jia, Kshiteej Sheth, Ola Svensson - Fair Colorful k-Center Clustering. [paper] [arXiv] [video]

11:21-11:24 Georg Anegg, Rico Zenklusen, Haris Angelidakis, Adam Kurpisz - A Technique for Obtaining True Approximations for k-Center with Covering Constraints. [paper] [arXiv] [video]

11:25-11:28 Monika Henzinger, Sagar Kale - Fully-Dynamic Coresets. [paper] [arXiv] [video]