Schedule

Scheduleupdated July 07, 2020 (16:34)

Workshops

Workshop	Stream	Slido
PRiML MON, 06.07.2020, 9:30-16:00 UTC+2
LCC MON, 06.07.2020, 8:45-18:00 UTC+2
LMW MON, 06.07.2020, 10:00-18:15 UTC+2
AATG TUE, 07.07.2020, 9:30-17:25 UTC+2
INFINITY TUE, 07.07.2020, 10:00-18:10 UTC+2

Plenaries

Session	DOI	Stream	Slack	Session Chair(s)
Invited Talk (LICS/ICALP) Andrew Chi-Chih Yao WED, 08.7.2020, 12:00-13:00 UTC+2				Artur Czumaj
Opening Ceremony (LICS/ICALP) and Best Video Awards WED, 08.7.2020, 13:00-13:30 UTC+2				Lijun Zhang Xiaotie Deng
Invited Talk (ICALP-A) Virginia Vassilevska Williams WED, 08.7.2020, 15:30-16:30 UTC+2				Daniel Marx
Social Meeting WED, 08.7.2020, 18:00-19:00 UTC+2				Holger Hermanns
Invited Talk (LICS/ICALP) Jérôme Leroux THU, 09.7.2020, 12:30-13:30 UTC+2				Joel Ouaknine
Tutorial (LICS/ICALP) Erich Grädel THU, 09.7.2020, 14:00-15:00 UTC+2				James Worrell
EATCS Award (ICALP) and Best Paper Announcement THU, 09.7.2020, 18:00-19:00 UTC+2				Paul Spirakis
Invited Talk (ICALP-B) Stefan Kiefer FRI, 10.7.2020, 12:30-13:30 UTC+2				Anuj Dawar
Award Session (LICS/ICALP) Presburger Award, Gödel Prize, Test of Time (LICS) FRI, 10.7.2020, 14:00-15:00 UTC+2				Anca Muscholl
Tutorial (LICS) Brigitte Pientka FRI, 10.7.2020, 17:00-18:00 UTC+2				Supratik Chakraborty
Invited Talk (LICS) Mariangiola Dezani-Ciancaglini SAT, 11.7.2020, 12:30-13:30 UTC+2				Naoki Kobayashi
Invited Talk (ICALP-A) Robert Krauthgamer SAT, 11.7.2020, 15:30-16:30 UTC+2				Kurt Mehlhorn
LICS Business Meeting SAT, 11.7.2020, 17:00 18:00 UTC+2				Dale Miller
EATCS General Assembly SAT, 11.7.2020, 17:00 18:00 UTC+2				Paul Spirakis

Q/A Sessions

Q/A Session A

WED, 08.07.2020, 14:00-15:00 UTC+2
when is this in my timezone?

Q/A Slot A1 — ICALP-A

Join via: Slack | YouTube Playlist Session chair(s): John Iacono

Paper ID	Title	Authors	Video Presenter
A1.A	Kinetic Geodesic Voronoi Diagrams in a Simple Polygon	Matias Korman, André van Renssen, Marcel Roeloffzen, Frank Staals	Frank Staals
A1.B	Scattering and Sparse Partitions, and their Applications	Arnold Filtser	Arnold Filtser
A1.C	Extending Partial 1-Planar Drawings	Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute, Martin Nöllenburg	Thekla Hamm
A1.D	Fréchet Distance for Uncertain Curves	Kevin Buchin, Chenglin Fan, Maarten Löffler, Aleksandr Popov, Benjamin Raichel and Marcel Roeloffzen	Aleksandr Popov
A1.E	Approximate Nearest Neighbor for Curves --- Simple, Efficient, and Deterministic	Arnold Filtser, Omrit Filtser, Matthew Katz	Omrit Filtser
A1.F	A Simple Dynamization of Trapezoidal Point Location in Planar Subdivisions	Milutin Brankovic, Nikola Grujic, André van Renssen, Martin P. Seybold	Martin Seybold

Q/A Slot A2 — ICALP-A

Join via: Slack | YouTube Playlist Session chair(s): Keren Censor-Hillel

Paper ID	Title	Authors	Video Presenter
A2.A	A Water-Filling Primal-Dual Algorithm for Approximating Non-Linear Covering Problems	Andres Fielbaum, Ignacio Morales, Jose Verschae	Andres Fielbaum
A2.B	An Optimal Algorithm for Online Multiple Knapsack	Marcin Bienkowski, Maciej Pacut, Krzysztof Piecuch	Maciej Pacut
A2.C	On Solving (Non)commutative Weighted Edmonds' Problem	Taihei Oki	Taihei Oki
A2.D	Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints	Naor Alaluf, Alina Ene, Moran Feldman, Huy Nguyen and Andrew Suh	Andrew Suh
A2.E	Scheduling Lower Bounds via AND Subset Sum	Amir Abboud, Karl Bringmann, Danny Hermelin and Dvir Shabtay	Danny Hermelin
A2.F	Linearly Representable Submodular Functions: An Algebraic Algorithm for Minimization	Rohit Gurjar and Rajat Rathi	Rohit Gurjar

Q/A Slot A3 — ICALP-A

Join via: Slack | YouTube Playlist Session chair(s): Eric Vigoda

Paper ID	Title	Authors	Video Presenter
A3.A	Counting solutions to random CNF formulas	Andreas Galanis, Leslie Ann Goldberg, Heng Guo and Kuan Yang	Kuan Yang
A3.B	On the central levels problem	Petr Gregor, Ondřej Mička, Torsten Mütze	Torsten Mütze
A3.C	The complexity of promise SAT on non-Boolean domains	Alex Brandts, Marcin Wrochna, Stanislav Živný	Marcin Wrochna
A3.D	Conditionally optimal approximation algorithms for the girth of a directed graph	Mina Dalirrooyfard, Virginia Vassilevska Williams	Mina Dalirrooyfard
A3.E	Medians in median graphs and their cube complexes in linear time	Laurine Bénéteau, Jérémie Chalopin, Victor Chepoi, Yann Vaxès	Laurine Bénéteau
A3.F	d-to-1 Hardness of Coloring 3-colorable Graphs with O(1) colors	Venkatesan Guruswami, Sai Sandeep	Sai Sandeep

Q/A Slot A4 — ICALP-B

Join via: Slack | YouTube Playlist Session chair(s): Kousha Etessami

Paper ID	Title	Authors	Video Presenter
A4.A	On Skolem-hardness and saturation points in Markov decision processes	Jakob Piribauer and Christel Baier	Jakob Piribauer
A4.B	Bisimulation Equivalence of Pushdown Automata is Ackermann-Complete	Wenbo Zhang, Qiang Yin, Huan Long and Xian Xu	Wenbo Zhang
A4.C	On polynomial recursive sequences	Michaël Cadilhac, Filip Mazowiecki, Charles Paperman, Michał Pilipczuk and Géraud Sénizergues	Filip Mazowiecki
A4.D	On Decidability of Time-bounded Reachability in CTMDPs	Rupak Majumdar, Mahmoud Salamati, Sadegh Soudjani	Mahmoud Salamati
A4.E	On the Size of Finite Rational Matrix Semigroups	Georgina Bumpus, Christoph Haase, Stefan Kiefer, Paul-Ioan Stoienescu and Jonathan Tanner	Jonathan Tanner
A4.F	Invariants for Continuous Linear Dynamical Systems	Shaull Almagor, Edon Kelmendi, Joël Ouaknine and James Worrell	Shaull Almagor

Q/A Slot A5 — LICS

Join via: Slack | YouTube Playlist Session chair(s): Orna Kupferman

Paper ID	Title	Authors	Video Presenter
A5.A	Bisimulation Finiteness of Pushdown Systems Is Elementary	Stefan Göller and Pawel Parys	Stefan Göller
A5.B	The Complexity of Reachability in Affine Vector Addition Systems with States	Michael Blondin and Mikhail Raskin	Mikhail Raskin
A5.C	Efficient Analysis of VASS Termination Complexity	Antonín Kučera, Jérôme Leroux and Dominik Velan	Antonín Kučera
A5.D	An Approach to Regular Separability in Vector Addition Systems	Wojciech Czerwiński and Georg Zetzsche	Wojciech Czerwiński
A5.E	Complexity of controlled bad sequences over finite sets of $\mathbb{N}^d$	A. R. Balasubramanian	A. R. Balasubramanian

Q/A Slot A6 — LICS

Join via: Slack | YouTube Playlist Session chair(s): Pierre Clairambault

Paper ID	Title	Authors	Video Presenter
A6.A	Modal Intuitionistic Logics as Dialgebraic Logics	Jim de Groot and Dirk Pattinson	Dirk Pattinson
A6.B	Cones as a model of intuitionistic linear logic	Thomas Ehrhard	Thomas Ehrhard
A6.C	Concurrent separation logic meets template games	Paul-André Melliès and Léo Stefanesco	Léo Stefanesco
A6.D	Logic Beyond Formulas: A Proof System on Graphs	Matteo Acclavio, Ross Horne, and Lutz Straßburger	Ross Horne
A6.E	Modal Logics with Composition on Finite Forests: Expressivity and Complexity	Bartosz Bednarczyk, Stéphane Demri, Raul Fervari, Alessio Mansutti	Alessio Mansutti
A6.F	Extended Kripke lemma and decidability for hypersequent substructural logics	Revantha Ramanayake	Revantha Ramanayake

Q/A Session B

WED, 08.07.2020, 17:00-18:00 UTC+2
when is this in my timezone?

Q/A Slot B1 — ICALP-A

Join via: Slack | YouTube Playlist Session chair(s): Thomas Sauerwald

Paper ID	Title	Authors	Video Presenter
B1.A	A dichotomy for bounded degree graph homomorphisms with nonnegative weights	Artsiom Hovarau, Jin-Yi Cai, Martin Dyer	Artsiom Hovarau
B1.B	Counting perfect matchings and the eight-vertex model	Jin-Yi Cai and Tianyu Liu	Tianyu Liu
B1.C	Contraction: a Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems	Shuai Shao and Yuxin Sun	Shuai Shao
B1.D	Graph isomorphism in quasipolynomial time parameterized by treewidth	Daniel Wiebking	Daniel Wiebking
B1.E	Counting homomorphisms in plain exponential time	A.Bulatov, A. Dadsetan	Andrei Bulatov
B1.F	Hypergraph Isomorphism for Groups with Restricted Composition Factors	Daniel Neuen	Daniel Neuen

Q/A Slot B2 — ICALP-A

Join via: Slack | YouTube Playlist Session chair(s): Sepehr Assadi

Paper ID	Title	Authors	Video Presenter
B2.A	A Scaling Algorithm for Weighted f-Factors in General Graphs	Ran Duan, Haoqing He, Tianyi Zhang	Haoqing He
B2.B	Network-Aware Strategies in Financial Systems	Pál András Papp, Roger Wattenhofer	Pál András Papp
B2.C	Robust Algorithms for TSP and Steiner Tree	Arun Ganesh, Bruce M. Maggs, Debmalya Panigrahi	Arun Ganesh
B2.D	An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs	Anindya De, Sanjeev Khanna, Huan Li, Hesam Nikpey	Huan Li, Hesam Nikpey
B2.E	Online Two-dimensional Load Balancing	Ilan Cohen and Sungjin Im and Debmalya Panigrahi	Ilan Cohen
B2.F	The Iteration Number of Colour Refinement	Sandra Kiefer, Brendan D. McKay	Sandra Kiefer

Q/A Slot B3 — ICALP-A

Join via: Slack | YouTube Playlist Session chair(s): Andrej Bogdanov

Paper ID	Title	Authors	Video Presenter
B3.A	Faster Random k-CNF Satisfiability	Andrea Lincoln, Adam Yedidia.	Yedidia Adam
B3.B	Sparse Recovery for Orthogonal Polynomial Transforms	Anna Gilbert, Albert Gu, Christopher Re, Atri Rudra, Mary Wootters	Albert Gu
B3.C	Hard Problems on Random Graphs	Jan Dreier, Henri Lotze and Peter Rossmanith	Peter Rossmanith
B3.D	Dynamic Averaging Load Balancing on Cycles	Dan Alistarh, Giorgi Nadiradze, Amirmojtaba Sabour	Amirmojtaba Sabour
B3.E	A spectral bound on hypergraph discrepancy	Aditya Potukuchi	Aditya Potukuchi
B3.F	How to hide a clique?	Uriel Feige, Vadim Grinberg	Vadim Grinberg

Q/A Slot B4 — ICALP-B

Join via: Slack | YouTube Playlist Session chair(s): Manuel Bodirsky

Paper ID	Title	Authors	Video Presenter
B4.A	Sensitive instances of the Constraint Satisfaction Problem	Libor Barto, Marcin Kozik, Johnson Tan, Matt Valeriote	Libor Barto
B4.B	Hrushovski's encoding and ω-categorical CSP monsters	Pierre Gillibert, Julius Jonušas, Michael Kompatscher, Antoine Mottet, and Michael Pinsker	Michael Pinsker
B4.C	On the power of ordering in linear arithmetic theories	Dmitry Chistikov and Christoph Haase	Christoph Haase
B4.D	On Higher-Order Cryptography	Boaz Barak, Raphaëlle Crubillé and Ugo Dal Lago	Ugo Dal Lago
B4.E	Implicit automata in typed λ-calculi I: aperiodicity in a non-commutative logic	Lê Thành Dũng Nguyễn and Pierre Pradic	Pierre Pradic
B4.F	Decision Problems in Information Theory	Mahmoud Abo Khamis, Phokion Kolaitis, Hung Ngo and Dan Suciu	Dan Suciu

Q/A Slot B5 — LICS

Join via: Slack | YouTube Playlist Session chair(s): Steve Awodey

Paper ID	Title	Authors	Video Presenter
B5.A	Multimodal Dependent Type Theory	Daniel Gratzer, G.A. Kavvos, Andreas Nuyts, Lars Birkedal	Daniel Gratzer
B5.B	Russian Constructivism in a Prefascist Theory	Pierre-Marie Pédrot	Pierre-Marie Pédrot
B5.C	A Higher Structure Identity Principle	Benedikt Ahrens, Paige Randall North, Michael Shulman, Dimitris Tsementzis	Paige North
B5.D	Sequential Colimits in Homotopy Type Theory	Kristina Sojakova, Floris van Doorn, Egbert Rijke	Kristina Sojakova
B5.E	Constructing Higher Inductive Types as Groupoid Quotients	Niels van der Weide	Niels van der Weide
B5.F	Linear Dependent Type Theory for Quantum Programming Languages	Peng Fu, Kohei Kishida, Peter Selinger	Peter Selinger, Peng Fu, Kohei Kishida

Q/A Slot B6 — LICS

Join via: Slack | YouTube Playlist Session chair(s): Christine Tasson

Paper ID	Title	Authors	Video Presenter
B6.A	Universal equivalence and majority of probabilistic programs over finite fields	Gilles Barthe, Charlie Jacomme and Steve Kremer	Charlie Jacomme
B6.B	Combining probabilistic and non-deterministic choice via weak distributive laws	Alexandre Goy, Daniela Petrisan	Alexandre Goy
B6.C	Approximating Values of Generalized-Reachability Stochastic Games	Pranav Ashok, Krishnendu Chatterjee, Jan Kretinsky, Maximilian Weininger, Tobias Winkler	Maximilian Weininger
B6.D	Mixing Probabilistic and non-Probabilistic Objectives in Markov Decision Processes	Raphaël Berthon, Shibashis Guha, Jean-François Raskin	Raphaël Berthon
B6.E	The Benefit of Being Non-Lazy in Probabilistic λ-calculus: Applicative Bisimulation is Fully Abstract for Non-Lazy Probabilistic Call-by-Name	Gianluca Curzi, Michele Pagani	Gianluca Curzi
B6.F	A characterisation of ordered abstract probabilities	Abraham Westerbaan, Bas Westerbaan, John van de Wetering	Bas Westerbaan

Q/A Session C

THU, 09.07.2020, 15:30-16:30 UTC+2
when is this in my timezone?

Q/A Slot C1 — ICALP-A

Join via: Slack | YouTube Playlist Session chair(s): Keren Censor-Hillel

Paper ID	Title	Authors	Video Presenter
C1.A	Simplifying and Unifying Replacement Paths Algorithms in Weighted Directed Graphs	Shiri Chechik & Moran Nechushtan	Moran Nechushtan
C1.B	On Packing Low-Diameter Spanning Trees	Julia Chuzhoy, Merav Parter, Zihan Tan	Zihan Tan
C1.C	Minimum cut in O(m log² n) time	Pawel Gawrychowski, Shay Mozes and Oren Weimann	Pawel Gawrychowski
C1.D	Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models	Suman Kalyan Bera, Amit Chakrabarti, Prantar Ghosh	Prantar Ghosh
C1.E	Proportionally Fair Clustering Revisited	Evi Micha, Nisarg Shah	Evi Micha
C1.F	Roundtrip Spanners with (2k-1) Stretch	Ruoxu Cen, Ran Duan and Yong Gu	Ran Duan

Q/A Slot C2 — ICALP-A

Join via: Slack | YouTube Playlist Session chair(s): Andrej Bogdanov

Paper ID	Title	Authors	Video Presenter
C2.A	Symmetric Arithmetic Circuits	Anuj Dawar and Gregory Wilsenach	Gregory Wilsenach
C2.B	Hardness of equations over finite solvable groups under the exponential time hypothesis	Armin Weiß	Armin Weiß
C2.C	Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity	Toniann Pitassi, Morgan Shirley, Thomas Watson	Morgan Shirley
C2.D	Can Verifiable Delay Functions be Based on Random Oracles?	Mohammad Mahmoody, Caleb Smith, David J. Wu	David J. Wu
C2.E	Feasible Interpolation for Polynomial Calculus and Sums-of-Squares	Tuomas Hakoniemi	Tuomas Hakoniemi
C2.F	On the Degree of Boolean Functions as Polynomials over ℤ_m	Xiaoming Sun, Yuan Sun, Jiaheng Wang, Kewen Wu, Zhiyu Xia, Yufan Zheng	Jiaheng Wang

Q/A Slot C3 — ICALP-A

Join via: Slack | YouTube Playlist Session chair(s): John Iacono

Paper ID	Title	Authors	Video Presenter
C3.A	Active Learning a Convex Body in Low Dimensions	Sariel Har-Peled, Mitchell Jones, Saladi Rahul	Mitchell Jones
C3.B	Polytopes, lattices, and spherical codes for the nearest neighbor problem	Thijs Laarhoven	Thijs Laarhoven
C3.C	On the two-dimensional knapsack problem for convex polygons	Arturo Merino, Andreas Wiese	Arturo Merino
C3.D	Near-optimal Algorithm for Constructing Greedy Consensus Tree	Hongxun Wu	Hongxun Wu
C3.E	Computational Complexity of the α-Ham-Sandwich Problem	Man-Kwun Chiu, Aruni Choudhary, Wolfgang Mulzer	Aruni Choudhary
C3.F	Succinct Filters for Sets of Unknown Sizes	Mingmou Liu, Yitong Yin, Huacheng Yu	Mingmou Liu

Q/A Slot C4 — ICALP-B

Join via: Slack | YouTube Playlist Session chair(s): Peter Selinger

Paper ID	Title	Authors	Video Presenter
C4.A	A Recipe for Quantum Graphical Languages	Titouan Carette and Emmanuel Jeandel	Titouan Carette
C4.B	The Strahler Number of a Parity Game	Laure Daviaud, Marcin Jurdzinski, K. S. Thejaswini	K. S. Thejaswini
C4.C	Two variable logic with ultimately periodic counting	Michael Benedikt, Egor V. Kostylev, Tony Tan	Egor Kostylev
C4.D	The Power of a Single Qubit: Two-way Quantum Finite Automata and the Word Problem	Zachary Remscrim	Zachary Remscrim
C4.E	The Adversarial Stackelberg Value in Quantitative Games	Emmanuel Filiot, Raffaella Gentilini and Jean-Francois Raskin	Jean-Francois Raskin
C4.F	Descriptive complexity on non-Polish spaces II	Mathieu Hoyrup	Mathieu Hoyrup

Q/A Slot C5 — LICS

Join via: Slack | YouTube Playlist Session chair(s): Igor Walukiewicz

Paper ID	Title	Authors	Video Presenter
C5.A	An Efficient Normalisation Procedure for Linear Temporal Logic and Very Weak Alternating Automata	Salomon Sickert and Javier Esparza	Salomon Sickert
C5.B	One-Clock Priced Timed Games are PSPACE-hard	John Fearnley, Rasmus Ibsen-Jensen and Rahul Savani	Rasmus Ibsen-Jensen
C5.C	Extensions of ω-Regular Languages	Bojańczyk, Kelmendi, Stefański, Zetzsche	Mikołaj Bojańczyk
C5.D	Register Automata with Extrema Constraints, and an Application to Two-Variable Logic	Szymon Toruńczyk and Thomas Zeume	Szymon Toruńczyk
C5.E	First-order tree-to-tree functions	Mikołaj Bojańczyk and Amina Doumane	Amina Doumane
C5.F	Space-efficient Query Evaluation over Probabilistic Event Streams	Rajeev Alur, Yu Chen, Kishor Jothimurugan, Sanjeev Khanna	Kishor Jothimurugan, Yu Chen

Q/A Slot C6 — LICS

Join via: Slack | YouTube Playlist Session chair(s): Radu Mardare

Paper ID	Title	Authors	Video Presenter
C6.A	On the computational content of Zorn's lemma	Thomas Powell	Thomas Powell
C6.B	Resolving finite indeterminacy: A definitive constructive universal prime ideal theorem	Peter Schuster, Daniel Wessel	Peter Schuster
C6.C	A Fixed Point Theorem on Lexicographic Lattice Structures	Angelos Charalambidis, Giannos Chatziagapis and Panos Rondogiannis	Giannos Chatziagapis
C6.D	Automata Learning: An Algebraic Approach	Henning Urbat and Lutz Schröder	Henning Urbat
C6.E	Interaction laws of monads and comonads	Shin-ya Katsumata, Exequiel Rivas, Tarmo Uustalu	Exequiel Rivas
C6.F	Coherence and normalisation-by-evaluation for bicategorical cartesian closed structure	Marcelo Fiore, Philip Saville	Philip Saville

Q/A Session D

THU, 09.07.2020, 17:00-18:00 UTC+2
when is this in my timezone?

Q/A Slot D1 — ICALP-A

Join via: Slack | YouTube Playlist Session chair(s): Martin Hoefer

Paper ID	Title	Authors	Video Presenter
D1.A	Tree Polymatrix Games are PPAD-hard	Argyrios Deligkas, John Fearnley, Rahul Savani	Argyrios Deligkas
D1.B	Existence and Complexity of Approximate Equilibria in Weighted Congestion Games	George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, Diogo Poças and Clara Waldmann	Diogo Poças
D1.C	Knapsack Secretary with Bursty Adversary	Thomas Kesselheim, Marco Molinaro	Thomas Kesselheim
D1.D	Node-Max-Cut and the Complexity of Equilibrium in Linear Weighted Congestion Games	Dimitris Fotakis, Vardis Kandiros, Thanasis Lianeas, Nikos Mouzakis, Panagiotis Patsilinakos and Stratis Skoulakis	Nikos Mouzakis
D1.E	Obviously Strategyproof Single-Minded Combinatorial Auctions	Bart de Keijzer, Maria Kyropoulou, Carmine Ventre	Carmine Ventre
D1.F	The Outer Limits of Contention Resolution on Matroids and Connections to the Secretary Problem.	Shaddin Dughmi	Shaddin Dughmi

Q/A Slot D2 — ICALP-A

Join via: Slack | YouTube Playlist Session chair(s): Erik Jan van Leeuwen

Paper ID	Title	Authors	Video Presenter
D2.A	Parameterized inapproximability for Steiner Orientation by gap amplification	Michal Wlodarczyk	Michal Wlodarczyk
D2.B	Space Efficient Construction of Lyndon Arrays in Linear Time	Philip Bille, Jonas Ellert, Johannes Fischer, Inge Li Gørtz, Florian Kurpicz, J. Ian Munro and Eva Rotenberg	Jonas Ellert
D2.C	The Power of Many Samples in Query Complexity	Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan	Lunjia Hu, Weijun Ma
D2.D	Towards Optimal Set-Disjointness and Set-Intersection Data Structures	Tsvi Kopelowitz, Virginia Vassilevska Williams	Tsvi Kopelowitz
D2.E	Faster Dynamic Range Mode	Bryce Sandlund, Yinzhan Xu	Yinzhan Xu
D2.F	Dynamic Longest Common Substring in Polylogarithmic Time	Panagiotis Charalampopoulos, Paweł Gawrychowski and Karol Pokorski	Karol Pokorski

Q/A Slot D3 — ICALP-A

Join via: Slack | YouTube Playlist Session chair(s): Christian Scheideler

Paper ID	Title	Authors	Video Presenter
D3.A	Improved Black-Box Constructions of Composable Secure Computation	Rohit Chatterjee, Xiao Liang, Omkant Pandey	Rohit Chatterjee
D3.B	Spectral Sparsification via Bounded-Independence Sampling	Dean Doron, Jack Murtagh, Salil Vadhan and David Zuckerman	Dean Doron
D3.C	Cryptographic Reverse Firewalls for Interactive Proof Systems	Chaya Ganesh, Bernardo Magri, Daniele Venturi.	Bernardo Magri
D3.D	Quantum Distributed Complexity of Set Disjointness on a Line	Frederic Magniez, Ashwin Nayak	Frederic Magniez, Ashwin Nayak
D3.E	On the complexity of zero gap MIP*	Hamoon Mousavi, Seyed Sajjad Nezhadi and Henry Yuen	Hamoon Mousavi
D3.F	From Holant to Quantum Entanglement and Back	Jin-Yi Cai, Zhiguo Fu and Shuai Shao	Shuai Shao

Q/A Slot D4 — ICALP-B

Join via: Slack | YouTube Playlist Session chair(s): Antonin Kucera

Paper ID	Title	Authors	Video Presenter
D4.A	Logical Characterisation of Hybrid Conformance	Maciej Gazda and Mohammadreza Mousavi	Maciej Gazda
D4.B	The Complexity of Bounded Context Switching with Dynamic Thread Creation	Pascal Baumann, Rupak Majumdar, Ramanathan Thinniyam Srinivasan, Georg Zetzsche	Pascal Baumann
D4.C	The Complexity of Verifying Loop-free Programs as Differentially Private	Marco Gaboardi, Kobbi Nissim and David Purser	David Purser
D4.D	Timed games and deterministic separability	Lorenzo Clemente, Sławomir Lasota and Radosław Piórkowski	Radosław Piórkowski
D4.E	The Topology of Local Computing in Networks	Pierre Fraigniaud and Ami Paz	Pierre Fraigniaud
D4.F	Dynamic Complexity of Reachability: How Many Changes Can We Handle?	Samir Datta, Pankaj Kumar, Anish Mukherjee, Anuj Tawari, Nils Vortmeier, Thomas Zeume	Nils Vortmeier

Q/A Slot D5 — LICS

Join via: Slack | YouTube Playlist Session chair(s): Antonina Kolokolova

Paper ID	Title	Authors	Video Presenter
D5.A	Counting Bounded Tree Depth Homomorphisms	Martin Grohe	Martin Grohe
D5.B	Lower Bounds for QBFs of Bounded Treewidth	Johannes K. Fichte, Markus Hecher and Andreas Pfandler	Markus Hecher
D5.C	Successor-Invariant First-Order Logic on Classes of Bounded Degree	Julien Grange	Julien Grange
D5.D	Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution	Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan	Joshua Blinkhorn
D5.E	The Surprising Power of Constant Depth Algebraic Proofs	Russell Impagliazzo, Sasank Mouli and Toniann Pitassi	Sasank Mouli
D5.F	The Hidden Subgroup Problem for Universal Algebras	Matthew Moore and Taylor Walenczyk	Matthew Moore

Q/A Slot D6 — LICS

Join via: Slack | YouTube Playlist Session chair(s): Elaine Pimentel

Paper ID	Title	Authors	Video Presenter
D6.A	A tier-based typed programming language characterizing Feasible Functionals	Hainry, Kapron, Marion, and Péchoux	Romain Péchoux
D6.B	Consuming and Persistent Types for Classical Logic	Delia Kesner, Pierre Vial	Pierre Vial
D6.C	Reconciling Noninterference and Gradual Typing	Arthur Azevedo de Amorim, Matt Fredrikson and Limin Jia	Arthur Azevedo de Amorim
D6.D	Deciding Differential Privacy for Programs with Finite Inputs and Outputs	Gilles Barthe, Rohit Chadha, Vishal Jagannath, A. Prasad Sistla and Mahesh Viswanathan	Rohit Chadha
D6.E	A calculus of expandable stores: Continuation-and-environment-passing style translations	Hugo Herbelin, Étienne Miquey	Étienne Miquey
D6.F	On Computability of Logical Approaches to Branching-Time Property Verification of Programs	Takeshi Tsukada	Takeshi Tsukada

Q/A Session E

FRI, 10.07.2020, 15:30-16:30 UTC+2
when is this in my timezone?

Q/A Slot E1 — ICALP-A

Join via: Slack | YouTube Playlist Session chair(s): Christian Scheideler

Paper ID	Title	Authors	Video Presenter
E1.A	Asynchronous Majority Dynamics in Preferential Attachment Trees	Maryam Bahrani, Nicole Immorlica, Divyarthi Mohan, S. Matthew Weinberg	Maryam Bahrani
E1.B	Quasi-majority Functional Voting on Expander Graphs	Nobutaka Shimizu and Takeharu Shiraga	Nobutaka Shimizu
E1.C	New Extremal bounds for Reachability and Strong-Connectivity Preservers under failures	Diptarka Chakraborty and Keerti Choudhary	Keerti Choudhary
E1.D	Node-Connectivity Terminal Backup, Separately-Capacitated Multiflow, and Discrete Convexity	Hiroshi Hirai and Motoki Ikeda	Motoki Ikeda
E1.E	A General Stabilization Bound for Influence Propagation in Graphs	Pál András Papp, Roger Wattenhofer	Pál András Papp
E1.F	New Fault Tolerant Subset Preservers	Greg Bodwin, Keerti Choudhary, Merav Parter and Noa Shahar	Noa Shahar

Q/A Slot E2 — ICALP-A

Join via: Slack | YouTube Playlist Session chair(s): Sepehr Assadi

Paper ID	Title	Authors	Video Presenter
E2.A	Deterministic Sparse Fourier Transform with an 𝓁_{∞} Guarantee	Yi Li, Vasileios Nakos	Yi Li
E2.B	Improved Bounds for Matching in Random-Order Streams	Aaron Bernstein	Aaron Bernstein
E2.C	Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation	Yu Chen, Sampath Kannan, Sanjeev Khanna	Yu Chen
E2.D	Robust Algorithms under Adversarial Injections	Paritosh Garg, Sagar Kale, Lars Rohwedder, Ola Svensson	Paritosh Garg
E2.E	Sampling Arbitrary Subgraphs Exactly Uniformly in Sublinear Time	Hendrik Fichtenberger, Mingze Gao and Pan Peng	Hendrik Fichtenberger
E2.F	Property Testing of LP-Type Problems	Rogers Epstein, Sandeep Silwal	Sandeep Silwal

Q/A Slot E3 — ICALP-A

Join via: Slack | YouTube Playlist Session chair(s): Shengyu Zhang

Paper ID	Title	Authors	Video Presenter
E3.A	Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds	Fedor Fomin, Daniel Lokshtanov, Ivan Mihajlin, Saket Saurabh and Meirav Zehavi	Meirav Zehavi
E3.B	Bridge-Depth Characterizes which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel	Marin Bougeret, Bart M. P. Jansen and Ignasi Sau	Bart M. P. Jansen
E3.C	Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem	Ofer Magen, Shiri Chechik	Ofer Magen
E3.D	On the Fine-Grained Complexity of Parity Problems	Amir Abboud, Shon Feller, Oren Weimann	Shon Feller
E3.E	Sublinear-Space Lexicographic Depth-First Search for Bounded Treewidth Graphs and Planar Graphs	Taisuke Izumi and Yota Otachi	Taisuke Izumi
E3.F	Efficient diagonalization of symmetric matrices associated with graphs of small treewidth	Martin Fürer, Carlos Hoppen and Vilmar Trevisan	Carlos Hoppen

Q/A Slot E4 — ICALP-B

Join via: Slack | YouTube Playlist Session chair(s): Szymon Toruńczyk

Paper ID	Title	Authors	Video Presenter
E4.A	The Post Correspondence Problem and equalisers for certain free group and monoid morphisms	Laura Ciobanu and Alan Logan	Alan Logan
E4.B	The complexity of knapsack problems in wreath products	Michael Figelius, Moses Ganardi, Markus Lohrey, Georg Zetzsche	Moses Ganardi
E4.C	Hardness results for constant-free pattern languages and word equations	Aleksi Saarela	Aleksi Saarela
E4.D	Weakly-unambiguous Parikh automata and their link to holonomic series	Alin Bostan, Arnaud Carayol, Florent Koechlin and Cyril Nicaud	Florent Koechlin
E4.E	On the structure of solution sets to regular word equations	Joel D Day and Florin Manea	Joel Day
E4.F	Rational subsets of Baumslag-Solitar groups	Michaël Cadilhac, Dmitry Chistikov, and Georg Zetzsche	Georg Zetzsche

Q/A Slot E5 — LICS

Join via: Slack | YouTube Playlist Session chair(s): Ugo Dal Lago

Paper ID	Title	Authors	Video Presenter
E5.A	Partial Univalence in n-truncated Type Theory	Christian Sattler, Andrea Vezzosi	Andrea Vezzosi
E5.B	The Integers as a Higher Inductive Type	Thorsten Altenkirch and Luis Scoccola	Thorsten Altenkirch
E5.C	Large and Infinitary Quotient Inductive-Inductive Types	András Kovács and Ambrus Kaposi	András Kovács
E5.D	Algebraic models of simple type theories: a polynomial approach	Nathanael Arkor & Marcelo Fiore	Nathanael Arkor
E5.E	A Constructive Model of Directed Univalence in Bicubical Sets	Matthew Z. Weaver, Daniel R. Licata	Matthew Z. Weaver
E5.F	Coherence via Well-Foundedness: Taming Set-Quotients in Homotopy Type Theory	Nicolai Kraus and Jakob von Raumer	Jakob von Raumer

Q/A Slot E6 — LICS

Join via: Slack | YouTube Playlist Session chair(s): Sam Staton

Paper ID	Title	Authors	Video Presenter
E6.A	A Cellular Howe Theorem	Peio Borthelle, Tom Hirschowitz, and Ambroise Lafont	Tom Hirschowitz
E6.B	A Complete Proof System for 1-Free Regular Expressions Modulo Bisimilarity	Clemens Grabmayer and Wan Fokkink	Clemens Grabmayer
E6.C	A Hennessy-Milner Theorem for ATL with Imperfect Information	Francesco Belardinelli, Catalin Dima, Vadim Malvone and Ferucio Tiplea	Catalin Dima
E6.D	Refinement-Based Game Semantics for Certified Abstraction Layers	Jérémie Koenig Zhong Shao	Jérémie Koenig
E6.E	The Complexity of Dynamic Data Race Prediction	Umang Mathur and Andreas Pavlogiannis and Mahesh Viswanathan	Andreas Pavlogiannis

Q/A Session F

SAT, 11.07.2020, 14:00-15:00 UTC+2
when is this in my timezone?

Q/A Slot F1 — ICALP-A

Join via: Slack | YouTube Playlist Session chair(s): Matthias Englert

Paper ID	Title	Authors	Video Presenter
F1.A	Scheduling in the Random-Order Model	Susanne Albers , Maximilian Janke	Maximilian Janke
F1.B	Lower bounds for dynamic distributed task allocation	Hsin-Hao Su, Nicole Wein	Nicole Wein
F1.C	Faster Minimization of Tardy Processing Time on a Single Machine	Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay and Philip Wellnitz	Nick Fischer
F1.D	Breaking the Barrier of 2 for the Storage Allocation Problem	Tobias Mömke and Andreas Wiese	Tobias Mömke
F1.E	The Online Min-Sum Set Cover Problem	Dimitris Fotakis, Loukas Kavouras, Grigorios Koumoutsos, Stratis Skoulakis, Manolis Vardas	Stratis Skoulakis
F1.F	Online Algorithms for Weighted Paging with Predictions	Zhihao Jiang, Debmalya Panigrahi and Kevin Sun	Kevin Sun

Q/A Slot F2 — ICALP-A

Join via: Slack | YouTube Playlist Session chair(s): Melanie Schmidt

Paper ID	Title	Authors	Video Presenter
F2.A	Popular Matchings with One-Sided Bias	Telikepalli Kavitha	Telikepalli Kavitha
F2.B	Matrices of optimal tree-depth and row-invariant parameterized algorithm for integer programming	Timothy Chan, Jacob Cooper, Martin Koutecký, Dan Král and Kristýna Pekárková	Jacob Cooper
F2.C	An FPT-algorithm for recognizing k-apices of minor-closed graph classes	Ignasi Sau, Giannos Stamoulis and Dimitrios M. Thilikos	Giannos Stamoulis
F2.D	Hitting long directed cycles is fixed-parameter tractable	Alexander Göke, Dániel Marx, Matthias Mnich	Alexander Göke
F2.E	On Quasipolynomial Multicut-Mimicking Networks and Kernelization of Multiway Cut Problems	Magnus Wahlström	Magnus Wahlström
F2.F	A (2 + ε)-Factor Approximation Algorithm for Split Vertex Deletion	Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Geevarghese Philip, Saket Saurabh	Philip Geevarghese

Q/A Slot F3 — ICALP-B

Join via: Slack | YouTube Playlist Session chair(s): Ranko Lazic

Paper ID	Title	Authors	Video Presenter
F3.A	Finite Sequentiality of Finitely Ambiguous Max-Plus Tree Automata	Erik Paul	Erik Paul
F3.B	Cost Automata, Safe Schemes, and Downward Closures	David Barozzini, Lorenzo Clemente, Thomas Colcombet and Paweł Parys	David Barozzini
F3.C	Computing measures of weak-MSO definable sets of trees	Damian Niwiński, Marcin Przybyłko, and Michał Skrzypczak	Michał Skrzypczak
F3.D	Single-use automata and transducers for infinite alphabets	Mikołaj Bojańczyk and Rafał Stefański	Rafał Stefański
F3.E	From linear to additive cellular automata	Alberto Dennunzio, Enrico Formenti, Darij Grinberg and Luciano Margara	Enrico Formenti
F3.F	When is a Bottom-Up Deterministic Tree Translation Top-Down Deterministic?	Sebastian Maneth, Helmut Seidl	Helmut Seidl

Q/A Slot F4 — LICS

Join via: Slack | YouTube Playlist Session chair(s): Emmanuel Filiot

Paper ID	Title	Authors	Video Presenter
F4.A	Good-for-games ω-Pushdown Automata	Karoliina Lehtinen and Martin Zimmermann	Karoliina Lehtinen
F4.B	Making Streett Determinization Tight	Cong Tian, Wensheng Wang, Zhenhua Duan	Cong Tian
F4.C	Uniformizations of regular relations over bi-infinite words	Grzegorz Fabiański, Michał Skrzypczak and Szymon Toruńczyk	Grzegorz Fabiański
F4.D	Re-pairing brackets	Dmitry Chistikov, Mikhail Vyalyi	Dmitry Chistikov
F4.E	Pebble Minimization of Polyregular Functions	Nathan Lhote	Nathan Lhote

Q/A Slot F5 — LICS

Join via: Slack | YouTube Playlist Session chair(s): Yijia Chen

Paper ID	Title	Authors	Video Presenter
F5.A	Temporal Constraint Satisfaction Problems in Fixed-Point Logic	Manuel Bodirsky, Wied Pakusa, and Jakub Rydval	Manuel Bodirsky and Jakub Rydval
F5.B	Descriptive complexity of real computation and probabilistic independence logic	Miika Hannula, Juha Kontinen, Jan Van den Bussche and Jonni Virtema	Jonni Virtema, Miika Hannula
F5.C	Intermediate problems in modular circuits satisfiability	Pawel Idziak, Piotr Kawalek, Jacek Krzaczkowski	Pawel Idziak
F5.D	On The Relational Width of First-Order Expansions of Finitely Bounded Homogeneous Binary Cores with Bounded Strict Width	Michał Wrona	Michał Wrona
F5.E	Sparse Hashing for Scalable Approximate Model Counting: Theory and Practice	Kuldeep Meel, S. Akshay	Kuldeep S. Meel
F5.F	On the Weisfeiler-Leman Dimension of Finite Groups	Jendrik Brachter, Pascal Schweitzer	Jendrik Brachter