Preliminary schedule:

DAY 1 Wed 08.7.2020
Invited Talk (LICS/ICALP) Andrew Yao
Opening Ceremony (LICS/ICALP)and Best Video Awards
Q/A Session A
Invited Talk (ICALP-A) Virginia Vassilevska Williams
Q/A Session B
Social Meeting
DAY 2 Thu 09.7.2020
Invited Talk (LICS/ICALP)Jerome Leroux
Tutorial (LICS/ICALP) Erich Grädel
Q/A Session C
Q/A Session D
EATCS Award (ICALP)and Best Paper Announcement
DAY 3 Fri 10.7.2020
Invited Talk (ICALP-B)Stefan Kiefer
Award Session (LICS/ICALP)Presburger Award, Gödel Prize, Test of Time (ICALP-A, ICALP-B and LICS)
Q/A Session E
Tutorial (LICS) Brigitte Pientka
DAY 4 Sat 11.7.2020
Invited Talk (LICS)Mariangiola Delzani
Q/A Session F
Invited Talk (ICALP-A)Robert Krauthgamer
Business Meetings

Accepted Papers

Accepted Papers - Track A

  • Andreas Galanis, Leslie Ann Goldberg, Heng Guo and Kuan Yang. Counting solutions to random CNF formulas.
  • Petr Gregor, Ondřej Mička and Torsten Mütze. On the central levels problem.
  • Artsiom Hovarau, Jin-Yi Cai and Martin Dyer. A dichotomy for bounded degree graph homomorphisms with nonnegative weights.
  • Alex Brandts, Marcin Wrochna and Stanislav Živný. The complexity of promise SAT on non-Boolean domains.
  • Andrés Fielbaum, Ignacio Morales and José Verschae. A Water-Filling Primal-Dual Algorithm for Approximating Non-Linear Covering Problems.
  • Telikepalli Kavitha. Popular Matchings with One-Sided Bias.
  • Marcin Bienkowski, Maciej Pacut and Krzysztof Piecuch. An Optimal Algorithm for Online Multiple Knapsack.
  • Michal Wlodarczyk. Parameterized inapproximability for Steiner Orientation by gap amplification.
  • Fedor Fomin, Daniel Lokshtanov, Ivan Mihajlin, Saket Saurabh and Meirav Zehavi. Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds.
  • Rohit Chatterjee, Xiao Liang and Omkant Pandey. Improved Black-Box Constructions of Composable Secure Computation.
  • Maryam Bahrani, Nicole Immorlica, Divyarthi Mohan and S. Matthew Weinberg. Asynchronous Majority Dynamics in Preferential Attachment Trees.
  • Jin-Yi Cai and Tianyu Liu. Counting perfect matchings and the eight-vertex model.
  • Andrea Lincoln and Adam Yedidia. Faster Random k-CNF Satisfiability.
  • Maximilian Janke and Susanne Albers. Scheduling in the Random-Order Model.
  • Argyrios Deligkas, John Fearnley and Rahul Savani. Tree Polymatrix Games are PPAD-hard.
  • Philip Bille, Jonas Ellert, Johannes Fischer, Inge Li Gørtz, Florian Kurpicz, J. Ian Munro and Eva Rotenberg. Space Efficient Construction of Lyndon Arrays in Linear Time.
  • Nobutaka Shimizu and Takeharu Shiraga. Quasi-majority Functional Voting on Expander Graphs.
  • George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, Diogo Poças and Clara Waldmann. Existence and Complexity of Approximate Equilibria in Weighted Congestion Games.
  • Shuai Shao and Yuxin Sun. Contraction: a Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems.
  • Sariel Har-Peled, Mitchell Jones and Saladi Rahul. Active learning a convex body in low dimensions.
  • Shiri Chechik and Moran Nechushtan. Simplifying and Unifying Replacement Paths Algorithms in Weighted Directed Graphs.
  • Daniel Wiebking. Graph isomorphism in quasipolynomial time parameterized by treewidth.
  • Thijs Laarhoven. Polytopes, lattices, and spherical codes for the nearest neighbor problem.
  • Taihei Oki. On Solving (Non)commutative Weighted Edmonds’ Problem.
  • Yi Li and Vasileios Nakos. Deterministic Sparse Fourier Transform with an $\ell_{\infty}$ Guarantee.
  • Dean Doron, Jack Murtagh, Salil Vadhan and David Zuckerman. Spectral Sparsification via Bounded-Independence Sampling.
  • Arturo Merino and Andreas Wiese. On the two-dimensional knapsack problem for convex polygons.
  • Julia Chuzhoy, Merav Parter and Zihan Tan. On Packing Low-Diameter Spanning Trees.
  • Marin Bougeret, Bart M. P. Jansen and Ignasi Sau. Bridge-Depth Characterizes which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel.
  • Ran Duan, Haoqing He and Tianyi Zhang. A Scaling Algorithm for Weighted f-Factors in General Graphs.
  • Anna Gilbert, Albert Gu, Christopher Re, Mary Wootters and Atri Rudra. Sparse Recovery for Orthogonal Polynomial Transforms.
  • Ofer Magen and Shiri Chechik. Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem.
  • Timothy Chan, Jacob Cooper, Martin Koutecký, Dan Král and Kristýna Pekárková. Matrices of optimal tree-depth and row-invariant parameterized algorithm for integer programming.
  • Aaron Bernstein. Improved Bounds for Matching in Random-Order Streams.
  • Pawel Gawrychowski, Shay Mozes and Oren Weimann. Minimum Cut in O(m log^2 n) Time.
  • Naor Alaluf, Alina Ene, Moran Feldman, Huy Nguyen and Andrew Suh. Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints.
  • Suman Kalyan Bera, Amit Chakrabarti and Prantar Ghosh. Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models.
  • Hsin-Hao Su and Nicole Wein. Lower Bounds for Dynamic Distributed Task Allocation.
  • Evi Micha and Nisarg Shah. Proportionally Fair Clustering Revisited.
  • Mina Dalirrooyfard and Virginia Vassilevska Williams. Conditionally optimal approximation algorithms for the girth of a directed graph.
  • Ignasi Sau, Giannos Stamoulis and Dimitrios Thilikos. An FPT-algorithm for recognizing k-apices of minor-closed graph classes.
  • Pál András Papp and Roger Wattenhofer. Network-Aware Strategies in Financial Systems.
  • Amir Abboud, Karl Bringmann, Danny Hermelin and Dvir Shabtay. Scheduling Lower Bounds via AND Subset Sum.
  • Andrei Bulatov and Amineh Dadsetan. Counting homomorphisms in plain exponential time.
  • Alexander Göke, Dániel Marx and Matthias Mnich. Hitting Long Directed Cycles is Fixed-Parameter Tractable.
  • Karl Bringmann, Nick Fischer, Danny Hermelin, Dvir Shabtay and Philip Wellnitz. Faster Minimization of Tardy Processing Time on a Single Machine.
  • Laurine Bénéteau, Jérémie Chalopin, Victor Chepoi and Yann Vaxès. Medians in median graphs and their cube complexes in linear time.
  • Daniel Neuen. Hypergraph Isomorphism for Groups with Restricted Composition Factors.
  • Thomas Kesselheim and Marco Molinaro. Knapsack Secretary with Bursty Adversary.
  • Diptarka Chakraborty and Keerti Choudhary. New Extremal bounds for Reachability and Strong-Connectivity Preservers under failures.
  • Anuj Dawar and Gregory Wilsenach. Symmetric Arithmetic Circuits.
  • Matias Korman, André van Renssen, Marcel Roeloffzen and Frank Staals. Kinetic Geodesic Voronoi Diagrams in a Simple Polygon.
  • Hiroshi Hirai and Motoki Ikeda. Node-Connectivity Terminal Backup, Separately-Capacitated Multiflow, and Discrete Convexity.
  • Arnold Filtser. Scattering and Sparse Partitions, and their Applications.
  • Chaya Ganesh, Bernardo Magri and Daniele Venturi. Cryptographic Reverse Firewalls for Interactive Proof Systems.
  • Frederic Magniez and Ashwin Nayak. Quantum Distributed Complexity of Set Disjointness on a Line.
  • Yu Chen, Sampath Kannan and Sanjeev Khanna. Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation.
  • Hongxun Wu. Near-optimal Algorithm for Constructing Greedy Consensus Tree.
  • Man-Kwun Chiu, Aruni Choudhary and Wolfgang Mulzer. Computational Complexity of the alpha-Ham-Sandwich Problem.
  • Jan Dreier, Henri Lotze and Peter Rossmanith. Hard Problems on Random Graphs.
  • Tobias Mömke and Andreas Wiese. Breaking the Barrier of 2 for the Storage Allocation Problem.
  • Dan Alistarh, Giorgi Nadiradze and Amirmojtaba Sabour. Dynamic Averaging Load Balancing on Cycles.
  • Armin Weiss. Hardness of equations over finite solvable groups under the exponential time hypothesis.
  • Dimitris Fotakis, Vardis Kandiros, Thanasis Lianeas, Nikos Mouzakis, Panagiotis Patsilinakos and Stratis Skoulakis. Node-Max-Cut and the Complexity of Equilibrium in Linear Weighted Congestion Games.
  • Pál András Papp and Roger Wattenhofer. A General Stabilization Bound for Influence Propagation in Graphs.
  • Arun Ganesh, Bruce Maggs and Debmalya Panigrahi. Robust Algorithms for NP-hard Problems: TSP and Steiner Tree.
  • Anindya De, Sanjeev Khanna, Huan Li and Hesam Nikpey. An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs.
  • Ruoxu Cen, Ran Duan and Yong Gu. Roundtrip Spanners with (2k-1) Stretch.
  • Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma and Li-Yang Tan. Correlated Input Samples in Query Complexity.
  • Dimitris Fotakis, Loukas Kavouras, Grigorios Koumoutsos, Stratis Skoulakis and Manolis Vardas. The Online Min-Sum Set Cover Problem.
  • Eduard Eiben, Robert Ganian, Thekla Hamm, Fabian Klute and Martin Nöllenburg. Extending Partial 1-Planar Drawings.
  • Zhihao Jiang, Debmalya Panigrahi and Kevin Sun. Online Algorithms for Weighted Paging with Predictions.
  • Kevin Buchin, Chenglin Fan, Maarten Löffler, Aleksandr Popov, Benjamin Raichel and Marcel Roeloffzen. Fréchet Distance for Uncertain Curves.
  • Bart de Keijzer, Maria Kyropoulou and Carmine Ventre. Obviously Strategyproof Single-Minded Combinatorial Auctions.
  • Paritosh Garg, Sagar Kale, Lars Rohwedder and Ola Svensson. Robust Algorithms under Adversarial Injections.
  • Rohit Gurjar and Rajat Rathi. Linearly Representable Submodular Functions: An Algebraic Algorithm for Minimization.
  • Amir Abboud, Shon Feller and Oren Weimann. On the Fine-Grained Complexity of Parity Problems.
  • Ilan Cohen, Sungjin Im and Debmalya Panigrahi. Online Two-dimensional Load Balancing.
  • Hamoon Mousavi, Seyed Sajjad Nezhadi and Henry Yuen. On the complexity of zero gap MIP*.
  • Arnold Filtser, Omrit Filtser and Matthew Katz. Approximate Nearest Neighbor for Curves – Simple, Efficient, and Deterministic.
  • Greg Bodwin, Keerti Choudhary, Merav Parter and Noa Shahar. New Fault Tolerant Subset Preservers.
  • Hendrik Fichtenberger, Mingze Gao and Pan Peng. Sampling Arbitrary Subgraphs Exactly Uniformly in Sublinear Time.
  • Toniann Pitassi, Morgan Shirley and Thomas Watson. Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity.
  • Mingmou Liu, Yitong Yin and Huacheng Yu. Succinct data structures for sets of unknown sizes.
  • Tsvi Kopelowitz and Virginia Vassilevska Williams. Towards Optimal Set-Disjointness and Set-Intersection Data Structures.
  • Venkatesan Guruswami and Sai Sandeep. d-to-1 Hardness of Coloring 3-colorable Graphs with O(1) colors.
    Jin-Yi Cai, Zhiguo Fu and Shuai Shao. From Holant to Quantum Entanglement and Back.
  • Bryce Sandlund and Yinzhan Xu. Faster Dynamic Range Mode.
  • Sandra Kiefer and Brendan McKay. The Iteration Number of Colour Refinement.
  • Taisuke Izumi and Yota Otachi. Sublinear-Space Lexicographic Depth-First Search for Bounded Treewidth Graphs and Planar Graphs.
  • Mohammad Mahmoody, Caleb Smith and David Wu. Can Verifiable Delay Functions be Based on Random Oracles?
  • Tuomas Hakoniemi. Feasible Interpolation for Polynomial Calculus and Sums-of-Squares.
  • Sandeep Silwal and Rogers Epstein. Property Testing of LP-Type Problems.
  • Magnus Wahlström. On quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems.
  • Martin Fürer, Carlos Hoppen and Vilmar Trevisan. Efficient diagonalization of symmetric matrices associated with graphs of small treewidth.
  • Panagiotis Charalampopoulos, Pawel Gawrychowski and Karol Pokorski. Dynamic Longest Common Substring in Polylogarithmic Time.
  • Aditya Potukuchi. A spectral bound on hypergraph discrepancy.
  • Uriel Feige and Vadim Grinberg. How to hide a clique?
  • Xiaoming Sun, Yuan Sun, Jiaheng Wang, Kewen Wu, Zhiyu Xia and Yufan Zheng. On the Degree of Boolean Functions as Polynomials over Zm.
  • Shaddin Dughmi. The Outer Limits of Contention Resolution on Matroids and Connections to the Secretary Problem.
  • Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Geevarghese Philip and Saket Saurabh. A (2 + ε)-factor Approximation Algorithm for Split Vertex Deletion.
  • Milutin Brankovic, Nikola Grujic, André van Renssen and Martin P. Seybold. A Simple Dynamization of Trapezoidal Point Location in Planar Subdivisions.

    Accepted Papers - Track B

    • Mahmoud Abo Khamis, Phokion Kolaitis, Hung Ngo and Dan Suciu. Decision Problems in Information Theory.
    • Laura Ciobanu and Alan Logan. The Post Correspondence Problem and equalisers for certain free group and monoid morphisms.
    • Georgina Bumpus, Christoph Haase, Stefan Kiefer, Paul-Ioan Stoienescu and Jonathan Tanner. On the Size of Finite Rational Matrix Semigroups.
    • Erik Paul. Finite Sequentiality of Finitely Ambiguous Max-Plus Tree Automata.
    • Maciej Gazda and Mohammadreza Mousavi. Logical Characterisation of Hybrid Conformance.
    • David Barozzini, Lorenzo Clemente, Thomas Colcombet and Paweł Parys. Cost Automata, Safe Schemes, and Downward Closures.
    • Lê Thành Dũng Nguyễn and Pierre Pradic. Implicit automata in typed lambda-calculi I: aperiodicity in a non-commutative logic.
    • Damian Niwiński, Marcin Przybyłko and Michał Skrzypczak. Computing measures of weak-MSO definable sets of trees.
    • Jakob Piribauer and Christel Baier. On Skolem-hardness and saturation points in Markov decision processes.
    • Sebastian Maneth and Helmut Seidl. When is a Bottom-Up Deterministic Tree Translation Top-Down Deterministic?
    • Pierre Gillibert, Julius Jonušas, Michael Kompatscher, Antoine Mottet and Michael Pinsker. Hrushovski’s encoding and ω-categorical CSP monsters.
    • Aleksi Saarela. Hardness results for constant-free pattern languages and word equations.
    • Michael Benedikt, Egor V. Kostylev and Tony Tan. Two variable logic with ultimately periodic counting.
    • Lorenzo Clemente, Sławomir Lasota and Radosław Piórkowski. Timed games and deterministic separability.
    • Libor Barto, Marcin Kozik, Johnson Tan and Matt Valeriote. Sensitive Instances of the Constraint Satisfaction Problem.
    • Michael Figelius, Moses Ganardi, Markus Lohrey and Georg Zetzsche. The complexity of knapsack problems in wreath products.
    • Titouan Carette and Emmanuel Jeandel. A unified framework for quantum graphical languages.
    • Joel Day and Florin Manea. On the structure of solution sets to regular word equations.
    • Alin Bostan, Arnaud Carayol, Florent Koechlin and Cyril Nicaud. Weakly-unambiguous Parikh automata and their link to holonomic series.
    • Emmanuel Filiot, Raffaella Gentilini and Jean-Francois Raskin. The Adversarial Stackelberg Value in Quantitative Games.
    • Pascal Baumann, Rupak Majumdar, Ramanathan Thinniyam Srinivasan and Georg Zetzsche. The complexity of bounded context switching with dynamic thread creation.
    • Mikolaj Bojanczyk and Rafał Stefański. Single-use automata and transducers for infinite alphabets.
    • Pierre Fraigniaud and Ami Paz. The Topology of Local Computing in Networks.
    • Michaël Cadilhac, Filip Mazowiecki, Charles Paperman, Michał Pilipczuk and Géraud Sénizergues. On polynomial recursive sequences.
    • Rupak Majumdar, Mahmoud Salamati and Sadegh Soudjani. On Decidability of Time-bounded Reachability in CTMDPs.
    • Shaull Almagor, Edon Kelmendi, Joël Ouaknine and James Worrell. Invariants for Continuous Linear Dynamical Systems.
    • Wenbo Zhang, Qiang Yin, Huan Long and Xian Xu. Bisimulation Equivalence of Pushdown Automata is Ackermann-Complete.
    • Mathieu Hoyrup. Descriptive complexity on non-Polish spaces II.
    • Marco Gaboardi, Kobbi Nissim and David Purser. The Complexity of Verifying Loop-free Programs as Differentially Private.
    • Samir Datta, Pankaj Kumar, Anish Mukherjee, Anuj Tawari, Nils Vortmeier and Thomas Zeume. Optimal Dynamic Complexity Bounds for Reachability in Restricted Graphs.
    • Boaz Barak, Raphaëlle Crubillé and Ugo Dal Lago. On Higher-Order Cryptography.
    • Alberto Dennunzio, Enrico Formenti, Darij Grinberg and Luciano Margara. From linear to additive cellular automata.
    • Michaël Cadilhac, Dmitry Chistikov and Georg Zetzsche. Rational subsets of Baumslag-Solitar groups.
    • Laure Daviaud, Marcin Jurdzinski and K. S. Thejaswini. The Strahler number of a parity game.
    • Zachary Remscrim. The Power of a Single Qubit: Two-way Quantum Finite Automata and the Word Problem.
    • Dmitry Chistikov and Christoph Haase. On the power of ordering in linear arithmetic theories.