Important Dates

• Submission deadline: Monday 18 February 2019, 23:59 AoE
• Notification: Friday 19 April 2019
• Workshop submission deadline: Saturday 15 December 2018
• Final manuscript due: Monday 29 April 2019
• Early registration deadline: Sunday 9 June 2019
• Workshops: 8 July 2019
• Main conference:  9-12 July 2019

Submissions

Guidelines

Authors are invited to submit an extended abstract of no more than 12 pages, excluding references presenting original research on the theory of computer science. All submissions must be formatted in the LIPIcs style and submitted via Easychair to the appropriate track of the conference, using the following link:

https://easychair.org/conferences/?conf=icalp2019.

The use of pdflatex and the LIPIcs style are mandatory: papers that deviate significantly from the required format may be rejected without consideration of merit.

No prior publication and no simultaneous submission to other publication outlets (either a conference or a journal) is allowed.

Technical details necessary for a proper scientific evaluation of a submission must be included in the 12-page submission or in a clearly labelled appendix, to be consulted at the discretion of program committee members. Authors are strongly encouraged to also make full versions of their submissions freely accessible in an on-line repository such as ArXiv, HAL, ECCC.

It is imperative that if a paper is accepted then at least one of the authors must register at ICALP 2019, attend the conference, and present the paper.

Best Paper Awards

As in previous editions of ICALP, there will be best paper and best student paper awards for each track of the conference. In order to be eligible for a best student paper award, a paper should be authored only by students and should be marked as such upon submission.

Topics

Papers presenting original research on all aspects of theoretical computer science are sought. Typical but not exclusive topics of interest are:

Track A: Algorithms, complexity and games

• Approximation Algorithms
• Combinatorial Optimization
• Combinatorics in Computer Science
• Computational Biology
• Computational Complexity
• Computational Geometry
• Cryptography
• Data Structures
• Design and Analysis of Algorithms
• Foundations of Algorithmic Game Theory
• Machine Learning
• Parallel, Distributed and External Memory Computing
• Quantum Computing
• Randomness in Computation

Track B: Automata, logic, semantics, and theory of programming

• Algebraic and Categorical Models
• Automata, Games, and Formal Languages
• Emerging and Non-standard Models of Computation
• Databases, Semi-Structured Data and Finite Model Theory
• Logic in Computer Science, Theorem Proving and Model Checking
• Models of Concurrent, Distributed, and Mobile Systems
• Models of Reactive, Hybrid and Stochastic Systems
• Principles and Semantics of Programming Languages
• Program Analysis and Transformation
• Specification, Verification and Synthesis
• Type Systems and Theory, Typed Calculi

Track C: Foundations of networks and multi-agent systems: models, algorithms and information management

• Algorithmic Aspects of Networks and Networking
• Algorithmic Game Theory
• Formal Methods for Network Information Management
• Foundations of Privacy, Trust and Reputation in Networks
• Foundations of Complex Networks
• Message-Passing Models of Distributed Computing
• Mobile and Wireless Networks and Communication
• Network Economics and Incentive-Based Computing Related to Networks
• Networks of Low Capability Devices
• Network Mining and Analysis
• Overlay Networks and P2P Systems
• Specification, Semantics, Synchronization of Networked Systems
• Theory of Security in Networks

Focus of track C: The aim for Track C is to be the leading venue for theory papers motivated by networking applications, and/or proposing theoretical results relevant to networking, certified analytically.

Proceedings

ICALP proceedings are published in the Leibniz International Proceedings in Informatics (LIPIcs) series. This is a series of high-quality conference proceedings across all fields in informatics established in cooperation with Schloss Dagstuhl - Leibniz Center for Informatics. LIPIcs volumes are published according to the principle of Open Access, i.e., they are available online and free of charge.

ICALP 2019 Proceedings Chairs

Ioannis Chatzigiannakis (Sapienza University of Rome, Italy)

Emanuela Merelli (University of Camerino, Italy)

Program Committees

Track A: Algorithms, complexity and games

Yossi Azar (Tel-Aviv University)
Sayan Bhattacharya (University of Warwick)
Aaron Bernstein (Rutgers University)
Jarosław Byrka (University of Wroclaw)
Karl Bringmann (Max-Planck-Institut für Informatik, Saarbrücken)
Gerth Stølting Brodal (Aarhus University)
Parinya Chalermsook (Aalto University)
Paul Duetting (London School of Economics)
Uriel Feige (Weizmann Institute, Rehovot)
Claudio Gentile (INRIA, Lille and Google Research, New York)
Mohsen Ghaffari (ETH Zurich)
Antoine Joux (IMJ-PRG, Sorbonne)
Thomas Kesselheim (University of Bonn)
Michal Koucký (Charles University of Prague)
Alexander Kulikov (Steklov Institute of Mathematics, St. Petersburg)
Sophie Laplante (Université Paris Diderot)
François Le Gall (Kyoto University)
Stefano Leonardi (Sapienza University of Rome, chair)
Vangelis Markakis (Athens University of Economics and Business)
Renato Paes-Leme (Google Research, New York)
Marcin Pilipczuk (University of Warsaw)
MS Ramanujan (University of Warwick)
Adi Rosén (CNRS and U. Paris Diderot)
Eva Rotenberg (Technical University of Denmark)
Rahul Santhanam (University of Oxford)
Alessandra Scafuro (North Carolina State University)
Sandeep Sen (IIT Delhi)
Francesco Silvestri (University of Padua)
Paul Spirakis (U. Liverpool and U. Patras)
Leen Stougie (CWI, Amsterdam)
Kavitha Telikepalli (Tata Institute of Fundamental Research, Mumbai)
Chaitanya Swamy (University of Waterloo)
Stefan Szeider (Technical University of Vienna)
Rico Zenklusen (ETH Zurich)

Track B: Automata, logic, semantics, and theory of programming

Parosh Abdulla (Uppsala University)
Christel Baier (TU Dresden, chair)
Krishnendu Chatterjee (IST)
Thomas Colcombet (CNRS and U. Paris Diderot)
Laure Daviaud (University Warwick)
Pedro D’Argenio (Universidad Nacional de Córdoba)
Josee Desharnais (Université Laval)
Mariangiola Dezani (Università di Torino)
Amina Doumane (ENS Lyon)
Rocco de Nicola (IMT Lucca)
Nathanaël Fijalkow (CNRS, U. Bordeaux)
Wan Fokkink (Vrije Universiteit Amsterdam)
Christoph Haase (University of Oxford)
Ichiro Hasuo (National Institute of Informatics, Tokyo)
Rahda Jagadeesan (De Paul University Chicago)
Markus Lohrey (Universität Siegen)
Radu Mardare (Aarlborg University)
Matteo Mio (ENS Lyon)
Madhusudan Parthasarathy (University of Illinois)
Mickael Randour (Université de Mons)
Sven Schewe (University of Liverpool)
Lutz Schröder (Universität Erlangen-Nürnberg)
Helmut Seidl (TU München)
Michal Skrzypczak (University of Warsaw)
Pawel Sobocinski (University of Southampton)
Christine Tasson (Université Paris Diderot)

Track C: Foundations of networks and multi-agent systems: models, algorithms and information management

Amotz Bar-Noy (CUNY)
Vittorio Bilo' (University of Salento)
Bogdan S. Chlebus (University of Colorado Denver)
Xiaotie Deng (Peking University, Beijing)
Paola Flocchini (University of Ottawa, chair)
Leszek Gasieniec (University of Liverpool)
Tobias Harks (University of Augsburg)
Magnús Halldórsson (Reykjavik University)
Christos Kaklamanis (University of Patras)
Ralf Klasing (CNRS and University of Bordeaux)
Max Klimm (Humboldt Universität zu Berlin)
Ravi Kumar (Google Mountain View)
Silvio Lattanzi (Google Zurich)
Toshimitsu Masuzawa (University of Osaka)
Ruta Mehta (U. Illinois Urbana-Champaign)
Olga Nikolaevna Goussevskaia (Federal University of Minas Gerais)
Ariel Orda (Technion)
Gopal Pandurangan (University of Houston)
Pino Persiano (University of Salerno)
Maria Potop-Butucaru (U. Paris VI)
Giuseppe Prencipe (University of Pisa)
Andrea Richa (Arizona State U.)
Patrick Thiran (EPFL)
Nicola Santoro (Carleton University)
Jukka Suomela (Aalto University)
Peter Widmayer (ETH Zurich)

ICALP 2019 Accepted Papers

ICALP 2019 - Track A Accepted Papers

• Thomas Watson.
  Amplification with One NP Oracle Query
• Benjamin Moseley.
  Scheduling to Approximate Minimization Objectives on Identical Machines
• Alex Bredariol Grilo.
  A simple protocol for verifiable delegation of quantum computation in one round
• Therese Biedl and Philipp Kindermann.
  Finding Tutte paths in linear time
• Vladimir Kolmogorov.
  Testing the complexity of a valued CSP language
• Ivona Bezakova, Andreas Galanis, Leslie Ann Goldberg and Daniel Stefankovic.
  The complexity of approximating the matching polynomial in the complex plane
• Guillaume Ducoffe.
  Faster approximation algorithms for computing shortest cycles on weighted graphs
• Venkatesan Guruswami, Lingfei Jin and Chaoping Xing.
  Constructions of maximally recoverable local reconstruction codes via function fields
• Seffi Naor, Seeun William Umboh and David Williamson.
  Tight Bounds for Online Weighted Tree Augmentation
• Amin Coja-Oghlan, Oliver Gebhard, Maximilian Hahn-Klimroth and Philipp Loick.
  Information-theoretic and algorithmic thresholds for group testing
• Julian Dšrfler, Christian Ikenmeyer and Greta Panova.
  On geometric complexity theory: Multiplicity obstructions are stronger than occurrence obstructions
• Fernando G.S.L. Brandao, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore and Xiaodi Wu.
  Quantum SDP Solvers: Large Speed-ups, Optimality, and Applications to Quantum Learning
• Andreas Bjšrklund, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi.
  Approximate Counting of $k$-Paths: Deterministic and in Polynomial Space
• Klaus Jansen, Alexandra Lassota and Lars Rohwedder.
  Near-Linear Time Algorithm for n-fold ILPs via Color Coding
• Matija Pasch and Konstantinos Panagiotou.
  Satisfiability Thresholds for Regular Occupation Problems
• Yassine Hamoudi and Frederic Magniez.
  Quantum ChebyshevΥs Inequality and Applications
• John Fearnley, Spencer Gordon, Ruta Mehta and Rahul Savani.
  Unique End of Potential Line
• Josep D’az, Lefteris Kirousis, Sofia Kokonezi and John Livieratos.
  Algorithmically Efficient Syntactic Characterization of Possibility Domains
• Andreas Bjšrklund and Ryan Williams.
  Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors
• Chaoping Xing and Chen Yuan.
  Construction of optimal locally recoverable codes and connection with hypergraph
• Mikkel Thorup, Or Zamir and Uri Zwick.
  Dynamic ordered sets with approximate queries, approximate heaps and soft heaps
• William Kuszmaul.
  Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation
• Naveen Garg, Anupam Gupta, Amit Kumar and Sahil Singla.
  Non-clairvoyant Precedence Constrained Scheduling
• Igor Carboni Oliveira.
  Randomness and Intractability in Kolmogorov Complexity
• Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami and David Zuckerman.
  Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions
• Massimo Equi, Roberto Grossi, Veli Mäkinen and Alexandru I. Tomescu.
  On the Complexity of String Matching for Graphs
• Nabil Mustafa.
  Computing Optimal Epsilon-nets is as Easy as Finding an Unhit Set
• Arturo Merino and Jose Soto.
  The minimum cost query problem on matroids with uncertainty areas
• Pavel Hrubeš, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao and Amir Yehudayoff.
  Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits
• Shantanav Chakraborty, András Gilyén and Stacey Jeffery.
  The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Mrinal Kumar, Ramprasad Saptharishi and Rafael Oliveira.
  Towards Optimal Depth Reductions for Syntactically Multilinear Circuits
• Fedor Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh and Meirav Zehavi.
  Decomposition of Map Graphs with Applications
• Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova and Avishay Tal.
  AC^0[p] Lower Bounds against MCSP via the Coin Problem
• Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar and Ronald de Wolf.
  Two new results about quantum exact learning
• Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu and Dimitrios Myrisiotis.
  Circuit Lower Bounds for MCSP from Local Pseudorandom Generators
• Alina Ene and Huy Nguyen.
  A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
• Alina Ene and Huy Nguyen.
  Towards Nearly-linear Time Algorithms for Submodular Maximization with a Matroid Constraint
• Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas and Nicole Wein.
  Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
• Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu and Yuancheng Yu.
  Approximation Algorithms for Min-Distance Problems
• Bingkai Lin.
  A Simple Gap-producing Reduction for the Parameterized Set Cover Problem
• Ran Duan, Ce Jin and Hongxun Wu.
  Faster Algorithms for All Pairs Non-decreasing Paths Problem
• Paul Goldberg and Alexandros Hollender.
  The Hairy Ball Problem is PPAD-complete
• Talya Eden, Dana Ron and Will Rosenbaum.
  The Arboricity Captures the Complexity of Sampling Edges
• Fedor Fomin, Petr Golovach, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi.
  Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals
• Siu-Wing Cheng and Yuchen Mao.
  Restricted Max-Min Allocation: Approximation and Integrality Gap
• Ankit Garg, Nikhil Gupta, Neeraj Kayal and Chandan Saha.
  Determinant equivalence test over finite fields and over Q
• JŽrŽmie Chalopin, Victor Chepoi, Shay Moran and Manfred K. Warmuth.
  Unlabeled sample compression schemes and corner peelings for ample and maximum classes
• Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir and Toniann Pitassi.
  Query-to-communication lifting for BPP using inner product
• Samuel Haney, Mehraneh Liaee, Bruce M. Maggs, Rajmohan Rajaraman, Debmalya Panigrahi and Ravi Sundaram.
  Retracting Graphs to Cycles
• Joran van Apeldoorn and Andras Gilyen.
  Improvements in Quantum SDP-Solving with Applications
• Thomas Colcombet, Jo‘l Ouaknine, Pavel Semukhin and James Worrell.
  On reachability problems for low dimensional matrix semigroups
• Klaus Jansen and Lars Rohwedder.
  Local search breaks 1.75 for Graph Balancing
• Eyal Mizrachi, Roy Schwartz, Joachim Spoerhase and Sumedha Uniyal.
  A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints
• Thomas Sauerwald and Luca Zanetti.
  Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities
• Jannik Matuschke, Ulrike Schmidt-Kraepelin and JosŽ Verschae.
  Maintaining Perfect Matchings at Low Cost
• Falko Hegerfeld and Stefan Kratsch.
  On adaptive algorithms for maximum matching
• Noga Alon, Shiri Chechik and Sarel Cohen.
  Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
• Alexandr Andoni, Clifford Stein and Peilin Zhong.
  Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity
• Peyman Afshani, Casper Benjamin Freksen, Lior Kamma and Kasper Green Larsen.
  Lower Bounds for Multiplication via Network Coding
• Yair Bartal, Nova Fandina and Ofer Neiman.
  Covering Metric Spaces by Few Trees
• Merav Parter and Eylon Yogev.
  Optimal Short Cycle Decomposition in Almost Linear Time
• Mark Bun, Nikhil Mande and Justin Thaler.
  Sign-Rank Can Increase Under Intersection
• Sepehr Assadi and Shay Solomon.
  When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
• Raimundo Brice–o, Andrei Bulatov, Victor Dalmau and Benoit Larose.
  Dismantlability, connectedness, and mixing in relational structures
• Eden Chlamtac, Michael Dinitz and Thomas Robinson.
  The Norms of Graph Spanners
• Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemys_aw Uznanski and Daniel Wolleb-Graf.
  Faster Algorithms for All-Pairs Bounded Min-Cuts
• Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler and Günter Rote.
  Geometric Multicut
• Andrii Riazanov and Venkatesan Guruswami.
  Beating Fredman-Komlós for perfect $k$-hashing
• Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee and Jason Li.
  Tight FPT Approximations for k-Median and k-Means
• Pranjal Awasthi, Ainesh Bakshi, Maria-Florina Balcan, Colin White and David P. Woodruff.
  Robust Communication-Optimal Distributed Clustering
• Ian Mertz, Toniann Pitassi and Yuanhao Wei.
  Short Proofs are Hard to Find
• Andreas Bjšrklund, Petteri Kaski and Ryan Williams.
  Solving systems of polynomial equations by a parity-counting self-reduction
• Dmitry Gavinsky, Troy Lee, Miklos Santha and Swagato Sanyal.
  A composition theorem for randomized query complexity via max-conflict complexity
• Bertie Ancona, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams and Nicole Wein.
  Algorithms and Hardness for Diameter in Dynamic Graphs
• Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu and Elham Kashefi.
  Complexity-theoretic limitations on blind delegated quantum computation
• Akbar Rafiey, Arash Rafiey and Thiago Santos.
  Toward a Dichotomy for Approximation of H-coloring
• Alexandr Andoni, Tal Malkin and Negev Shekel Nosatzki.
  Two Party Distribution Testing: Communication and Security
• Vincent Cohen-Addad and Jason Li.
  On the Fixed-Parameter Tractability of Capacitated Clustering
• Angel Cantu, Austin Luchsinger, Robert Schweller and Tim Wylie.
  Covert Computation in Self-Assembled Circuits
• Kyriakos Axiotis and Christos Tzamos.
  Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms
• Ce Jin.
  An Improved FPTAS for 0-1 Knapsack
• Tobias Friedrich and Ralf Rothenberger.
  The Satisfiability Threshold for Non-Uniform Random 2-SAT
• Zhiyi Huang and Xue Zhu.
  Scalable and Jointly Differentially Private Packing
• Kuan Cheng, Zhengzhong Jin, Xin Li and Ke Wu.
  Block Edit Errors with Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary Codes
• David P. Woodruff and Guang Yang.
  Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams
• Anupam Gupta, Guru Guruganesh, Binghui Peng and David Wajc.
  Stochastic Online Metric Matching
• Miron Ficak, Marcin Kozik, Miroslav Ol_‡k and Szymon Stankiewicz.
  Dichotomy for symmetric Boolean PCSPs
• Giulia Bernardini, Pawel Gawrychowski, Nadia Pisanti, Solon Pissis and Giovanna Rosone.
  Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication
• Xue Chen and Eric Price.
  Estimating the frequency of a clustered signal
• Graham Cormode, Jacques Dark and Christian Konrad.
  Independent Sets in Vertex-Arrival Streams
• Amir Abboud.
  Fine-Grained Reductions and Quantum Speedups for Dynamic Programming
• Xiaoming Sun, David P. Woodruff, Guang Yang and Jialin Zhang.
  Querying a Matrix through Matrix-Vector Products
• Akanksha Agrawal, Fedor Fomin, Daniel Lokshtanov, Saket Saurabh and Prafullkumar Tale.
  Path Contraction Faster than 2^n
• Adam Kurpisz.
  Sum-of-Squares bounds via boolean function analysis

ICALP 2019 - Track B Accepted Papers

• Jean-Eric Pin and Christophe Reutenauer.
  A Mahler's theorem for word functions
• Nikhil Balaji, Stefan Kiefer, Petr Novotný, Guillermo A. Pérez and Mahsa Shirmohammadi.
  On the Complexity of Value Iteration
• Sylvain Schmitz.
  The Parametric Complexity of Lossy Counter Machines
• Holger Dell, Marc Roth and Philip Wellnitz.
  Counting Answers to Existential Questions
• Christof Löding and Anton Pirogov.
  Determinization of Büchi Automata: Unifying the Approaches of Safra and Muller-Schupp
• Titouan Carette, Emmanuel Jeandel, Simon Perdrix and Renaud Vilmart.
  Completeness of Graphical Languages for Mixed States Quantum Mechanics
• Paul Bell.
  Polynomially Ambiguous Probabilistic Automata on Restricted Languages
• Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi and Patrick Totzke.
  Büchi Objectives in Countable MDPs
• Dani Dorfman, Haim Kaplan and Uri Zwick.
  A faster deterministic exponential time algorithm for Energy Games and Mean Payoff Games
• Antonio Molina Lovett and Jeffrey Shallit.
  Optimal Regular Expressions for Permutations
• Matthieu Picantin.
  Automatic semigroups vs automaton semigroups
• Anca Muscholl and Gabriele Puppis.
  Equivalence of finite-valued streaming string transducers is decidable
• Ugo Dal Lago, Francesco Gavazzo and Akira Yoshimizu.
  Differential Logical Relations
• Kousha Etessami, Emanuel Martinov, Alistair Stewart and Mihalis Yannakakis.
  Reachability for Branching Concurrent Stochastic Games
• Mohamed-Amine Baazizi, Dario Colazzo, Giorgio Ghelli and Carlo Sartiani.
  A Type System for Interactive JSON Schema Inference
• Katrin Casel, Joel Day, Pamela Fleischmann, Tomasz Kociumaka, Florin Manea and Markus L. Schmid.
  Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number
• Pablo Barceló, Diego Figueira and Miguel Romero Orth.
  Boundedness of Conjunctive Regular Path Queries
• Pablo Barcelo, Chih-Duo Hong, Xuan-Bach Le, Anthony W. Lin and Reino Niskanen.
  Monadic Decomposability of Regular Relations
• Pierre-Alain Reynier and Didier Villevalois.
  Sequentiality of String-to-Context Transducers
• Henning Urbat and Stefan Milius.
  Varieties of Data Languages
• Bader Abu Radi and Orna Kupferman.
  Minimizing GFG Transition-Based Automata
• Paul Brunet and Alexandra Silva.
  A Kleene theorem for nominal automata
• Martin Raszyk, David Basin and Dmitriy Traytel.
  From Nondeterministic to Multi-Head Deterministic Finite-State Transducers
• Anuj Dawar, Erich Grädel and Wied Pakusa.
  Approximations of Isomorphism and Logics with Linear-Algebraic Operators
• Martin Grohe and Sandra Kiefer.
  A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus
• Thomas Place and Marc Zeitoun.
  On all things star-free
• Mehran Hosseini, Joel Ouaknine and James Worrell.
  On Termination of Integer Linear Loops
• Mikolaj Bojanczyk, Sandra Kiefer and Nathan Lhote.
  String-to-string interpretations with polynomial size output
• Marie Fortin.
  FO = FO3 for linear orders with monotone binary relations
• Murray Elder and Laura Ciobanu.
  Solutions sets to systems of equations in hyperbolic groups are EDT0L in PSPACE
• Le Thanh Dung Nguyen and Pierre Pradic.
  From normal functors to logarithmic space queries

ICALP 2019 - Track C Accepted Papers

• Eleni C. Akrida, George Mertzios, Sotiris Nikoletseas, Christoforos Raptopoulos, Paul Spirakis and Viktor Zamaraev.
  How fast can we reach a target vertex in stochastic temporal graphs?
• Matthias Bonne and Keren Censor-Hillel.
  Distributed Detection of Cliques in Dynamic Networks
• Ioannis Caragiannis and Angelo Fanelli.
  On approximate pure Nash equilibria in weighted congestion game with polynomial latencies
• Arnaud Casteigts, Joseph Peters and Jason Schoeters.
  Temporal Cliques Admit Sparse Spanners
• Keren Censor-Hillel and Mikaël Rabie.
  Distributed Reconfiguration of Maximal Independent Sets
• Ilan Cohen, Jakubcki, Stefano Leonardi and Aris Anagnostopoulos.
  Stochastic Graph Exploration
• Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Manuel Lafond, Jaroslav Opatrny and Sunil Shende.
  Energy Consumption of Group Search on a Line
• Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos and Paul Spirakis.
  Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem
• Stefan Dobrev, Lata Narayanan, Jaroslav Opatrny and Denis Pankratov.
  Exploration of High-Dimensional Grids by Finite Automata
• Yuval Emek, Shay Kutten, Ron Lavi and William K. Moses Jr..
  Deterministic Leader Election in Programmable Matter
• Thomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko and Jakob Spooner.
  Two Moves per Time Step Make a Difference
• Mohsen Ghaffari and Ali Sayyadi.
  Distributed Arboricity-Dependent Graph Coloring via All-to-All Communication
• Siddharth Gupta, Adrian Kosowski and Laurent Viennot.
  Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond
• Bernhard Haeupler, Fabian Kuhn, Anders Martinsson, Kalina Petrova and Pascal Pfister.
  Optimal Strategies for Patrolling Fences
• Sungjin Im, Benjamin Moseley, Kirk Pruhs and Manish Purohit.
  Matroid Coflow Scheduling
• Amos Korman and Yoav Rodeh.
  Multi-Round Cooperative Search Games with Multiple Players
• Dariusz Kowalski and Miguel A. Mosteiro.
  Polynomial Anonymous Dynamic Distributed Computing without a Unique Leader
• Frederik Mallmann-Trenn, Yannic Maus and Dominik Pajak.
  Noidy Conmunixatipn: On the Convergence of the Averaging Population Protocol
• Shunhao Oh, Anuja Meetoo Appavoo and Seth Gilbert.
  Periodic Bandits and Wireless Network Selection
• Christian Scheideler and Alexander Setzer.
  On the Complexity of Local Graph Transformations
• Daniel Schmand, Marc Schroder and Alexander Skopalik.
  Network Investment Games with Wardrop Followers