If you wish to send in your presentation to be included in the list, please email us at:

Invited Speakers - Prize Winners - Track A - Track B - Track C

Invited Speakers

Model checking and strategy synthesis for mobile autonomy from theory to practice
Marta Kwiatkowska
Computing Choice
Devavrat Shah

Prize Winners

EATCS award - Borel Coalgebra and Non-Wellfounded Logic
Dexter Kozen

Track A: Algorithms, Complexity and Games

Voronoi Choice Games New!
Meena Boppana, Rani Hod, Michael Mitzenmacher and Tom Morgan
Constant Approximation for Capacitated k-Median with (1+epsilon)-Capacity Violation New!
Gökalp Demirci and Shi Li
All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing
Christian Sommer
Subexponential Time Algorithms for Embedding H-Minor Free Graphs
Hans L. Bodlaender, Jesper Nederlof and Tom van der Zanden
Improved Reduction from the Bounded Distance Decoding Problem to the Unique Shortest Vector Problem in Lattices
Shi Bai, Damien Stehle and Weiqiang Wen
The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems
Andreas Emil Feldmann and Dániel Marx
Approximate Span Programs
Tsuyoshi Ito and Stacey Jeffery
Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost
Alexandr Andoni, Assaf Naor and Ofer Neiman
Robust Assignments via Ear Decompositions and Randomized Rounding
David Adjiashvili, Viktor Bindewald and Dennis Michaels
Relating Graph Thickness to Planar Layers and Bend Complexity
Stephane Durocher and Debajyoti Mondal
Tight Hardness Results for Maximum Weight Rectangles
Arturs Backurs, Nishanth Dikkala and Christos Tzamos
Online Semidefinite Programming
Noa Elad, Satyen Kale and Joseph Naor
Total space in resolution is at least width squared
Ilario Bonacina
Rényi Information Complexity and an Information Theoretic Characterization of the Partition Bound
Manoj Prabhakaran and Vinod M Prabhakaran
Incremental 2-Edge-Connectivity in Directed Graphs
Loukas Georgiadis, Giuseppe F. Italiano and Nikos Parotsidis
Tight Hardness Results for Maximum Weight Rectangles
Arturs Backurs, Nishanth Dikkala and Christos Tzamos
On the Sensitivity Conjecture
Avishay Tal
Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers
Sara Ahmadian and Chaitanya Swamy
Linear time algorithm for quantum 2SAT
Itai Arad, Miklos Santha, Aarthi Sundaram and Shengyu Zhang
Deterministic Time-Space Tradeoffs for k-SUM
Andrea Lincoln, Virginia Vassilevska Williams, Joshua Wang and Ryan Williams
Approximation via Correlation Decay when Strong Spatial Mixing Fails
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo and Daniel Štefankovič

Track B: Logic, Semantics, Automata and Theory of Programming

On Restricted Nonnegative Matrix Factorization New!
Dmitry Chistikov, Stefan Kiefer, Ines Marušic, Mahsa Shirmohammadi and James Worrell
Polynomial Time corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length.
Olivier Bournez, Daniel Graça and Amaury Pouly
On the Complexity of Grammar-Based Compression over Fixed Alphabets
Katrin Casel, Henning Fernau, Serge Gaspers, Benjamin Gras and Markus L. Schmid
Deciding topological complexity of Buchi languages
Michał Skrzypczak and Igor Walukiewicz
Characterizing classes of regular languages using prefix codes of bounded synchronization delay
Volker Diekert and Tobias Walter
Deciding Piecewise Testable Separability for Regular Tree Languages
Jean Goubault-Larrecq and Sylvain Schmitz
Nesting Depth of Operators in Graph Database Queries: Expressiveness Vs. Evaluation Complexity
M. Praveen and B Srivathsan
On Word and Frontier Languages of Unsafe Higher-Order Grammars
Kazuyuki Asada and Naoki Kobayashi
Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness
Hubie Chen
A Linear Acceleration Theorem for 2D Cellular Automata on all Complete Neighborhoods
Victor Poupet and Anaël Grandjean
Past, Present, and Infinite Future
Thomas Wilke
Solutions of Word Equations over Partially Commutative Structures
Volker Diekert, Artur Jeż and Manfred Kufleitner
The Complexity of Rational Synthesis
Rodica Condurache, Emmanuel Filiot, Raffaella Gentilini and Jean-Francois Raskin
The Bridge Between Regular Cost Functions and Omega-Regular Languages
Thomas Colcombet and Nathanaël Fijalkow
The Schützenberger product for Syntactic Spaces
Mai Gehrke, Daniela Petrisan and Luca Reggio

Track C: Foundations of Networked Computation: Models, Algorithms and Information Management

Partition bound is quadratically tight for product distributions
Prahladh Harsha, Rahul Jain and Jaikumar Radhakrishnan
Sublinear-Space Bounded-Delay Enumeration for Massive Network Analytics: Maximal Cliques
Alessio Conte, Roberto Grossi, Andrea Marino and Luca Versari
On the Resiliency of Randomized Routing Against Multiple Edge Failures
Marco Chiesa, Andrei Gurtov, Aleksander Madry, Slobodan Mitrovic, Ilya Nikolaevskiy, Michael Schapira and Scott Shenker
Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
Yun Kuen Cheung, Gramoz Goranci and Monika Henzinger
On the Size and the Approximability of Minimum Temporally Connected Subgraphs
Kyriakos Axiotis and Dimitris Fotakis