Overview Programme
ICALP 2019 Overview Programme.
ICALP 2019 Booklet (includes the detailed programme)
Detailed Programme
Programme of ICALP 2019 Workshops
8:15
Registration
9:00
18:00
*The programme of ICALP 2019 related workshops can be found at each workshop's website.
8:00
Registration
8:45
Opening Address
9:00
Keynote Lecture 1: Michal Feldman (Tel-Aviv University, Israel)
Auction Design under Interdependent Value
Room: I.4, Session Chair: Paola Flocchini
10:00
Break
Track: A
Session A.1.1
Room: I.4 Chair: Jiri Sgall
Track: A
Session A.2.1
Room: I.10 Chair: Paul Spirakis
Track: A
Session A.3.1
Room: II.8 Chair: Leslie Goldberg
Track: B
Session B.1
Room: II.9 Chair: Christel Baier10:30
Seffi Naor, Seeun William Umboh and David Williamson.
Tight Bounds for Online Weighted Tree AugmentationAlexandr Andoni, Tal Malkin and Negev Shekel Nosatzki.
Two Party Distribution Testing: Communication and SecurityVladimir Kolmogorov.
Testing the Complexity of a Valued CSP Language10:55
Anupam Gupta, Guru Guruganesh, Binghui Peng and David Wajc.
Stochastic Online Metric MatchingAngel Cantu, Austin Luchsinger, Robert Schweller and Tim Wylie.
Covert Computation in Self-Assembled CircuitsPablo Barcelo, Chih-Duo Hong, Xuan-Bach Le, Anthony W. Lin and Reino Niskanen.
Monadic Decomposability of Regular RelationsRaimundo Briceño, Andrei Bulatov, Victor Dalmau and Benoit Larose.
Dismantlability, Connectedness, and Mixing in Relational Structures11:20
Naveen Garg, Anupam Gupta, Amit Kumar and Sahil Singla.
Non-Clairvoyant Precedence Constrained SchedulingZhiyi Huang and Xue Zhu.
Scalable and Jointly Differentially Private PackingMiron Ficak, Marcin Kozik, Miroslav Olšák and Szymon Stankiewicz.
Dichotomy for Symmetric Boolean PCSPsPaul Brunet and Alexandra Silva.
A Kleene Theorem for Nominal Automata11:45
Break
Track: A
Session A.1.2
Room: I.4 Chair: Stefano Leonardi
Track: A
Session A.2.2
Room: I.10 Chair: Igor Carboni Oliveira
Track: B
Session B.2
Room: II.9 Chair: Volker Diekert
Track: A
Session A.3.2
Room: II.8 Chair: Kazuo IwamaSepehr Assadi and Shay Solomon.
When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear TimeAlexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova and Avishay Tal.
AC^0[p] Lower Bounds Against MCSP via the Coin ProblemKatrin Casel, Joel Day, Pamela Fleischmann, Tomasz Kociumaka, Florin Manea and Markus L. Schmid.
Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality NumberJannik Matuschke, Ulrike Schmidt-Kraepelin and José Verschae.
Maintaining Perfect Matchings at Low CostMahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu and Dimitrios Myrisiotis.
Circuit Lower Bounds for MCSP from Local Pseudorandom GeneratorsMartin Grohe and Sandra Kiefer.
A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded GenusAlex Bredariol Grilo.
A Simple Protocol for Verifiable Delegation of Quantum Computation in One RoundFalko Hegerfeld and Stefan Kratsch.
On Adaptive Algorithms for Maximum MatchingMrinal Kumar, Ramprasad Saptharishi and Rafael Oliveira.
Towards Optimal Depth Reductions for Syntactically Multilinear CircuitsAnuj Dawar, Erich Grädel and Wied Pakusa
Approximations of Isomorphism and Logics with Linear-Algebraic OperatorsYassine Hamoudi and Frederic Magniez.
Quantum Chebyshev's Inequality and ApplicationsLunch
Track: A
Session A.1.3
Room: I.4 Chair: Sandeep Sen
Track: A
Session A.2.3
Room: I.10 Chair: Amir Abboud
Track: A
Session A.3.3
Room: II.8 Chair: Andreas WieseDavid P. Woodruff and Guang Yang.
Separating k-Player from t-Player One-Way Communication, with Applications to Data StreamsThomas Watson.
Amplification with One NP Oracle QueryBenjamin Moseley.
Scheduling to Approximate Minimization Objectives on Identical MachinesGraham Cormode, Jacques Dark and Christian Konrad.
Independent Sets in Vertex-Arrival StreamsIgor Carboni Oliveira.
Randomness and Intractability in Kolmogorov ComplexitySiu-Wing Cheng and Yuchen Mao.
Restricted Max-Min Allocation: Approximation and Integrality GapAmin Coja-Oghlan, Oliver Gebhard, Maximilian Hahn-Klimroth and Philipp Loick.
Information-Theoretic and Algorithmic Thresholds for Group TestingDmitry Gavinsky, Troy Lee, Miklos Santha and Swagato Sanyal.
A Composition Theorem for Randomized Query Complexity via Max-Conflict ComplexityKyriakos Axiotis and Christos Tzamos.
Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms TALK WAS CANCELLEDTalya Eden, Dana Ron and Will Rosenbaum.
The Arboricity Captures the Complexity of Sampling EdgesYuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami and David Zuckerman.
Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product DistributionsBreak
Track: A
Session A.1.4
Room: I.4 Chair: Artur Czumaj
Track: A
Session A.2.4
Room: I.10 Chair: Thomas Erlebach
Track: A
Session A.3.4
Room: II.8 Chair: Kazuo Iwama
Track: A
W
Session A.4.1
Room: II.9 Chair: Sandeep SenVenkatesan Guruswami, Lingfei Jin and Chaoping Xing.
Constructions of Maximally Recoverable Local Reconstruction Codes via Function FieldsKlaus Jansen and Lars Rohwedder.
Local Search Breaks 1.75 for Graph BalancingSrinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar and Ronald de Wolf.
Two New Results About Quantum Exact LearningMikkel Thorup, Or Zamir and Uri Zwick.
Dynamic Ordered Sets with Approximate Queries, Approximate Heaps and Soft HeapsChaoping Xing and Chen Yuan.
Construction of Optimal Locally Recoverable Codes and Connection with HypergraphMina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas and Nicole Wein.
Tight Approximation Algorithms for Bichromatic Graph Diameter and Related ProblemsScott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu and Elham Kashefi.
Complexity-Theoretic Limitations on Blind Delegated Quantum ComputationBertie Ancona, Monika Henzinger, Liam Roditty, Virginia Vassilevska Williams and Nicole Wein.
Algorithms and Hardness for Diameter in Dynamic GraphsAndrii Riazanov and Venkatesan Guruswami.
Beating Fredman-Komlós for perfect k-hashingMina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas, Nicole Wein, Yinzhan Xu and Yuancheng Yu.
Approximation Algorithms for Min-Distance ProblemsShantanav Chakraborty, András Gilyén and Stacey Jeffery.
The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian SimulationEden Chlamtac, Michael Dinitz and Thomas Robinson.
The Norms of Graph SpannersAkbar Rafiey, Arash Rafiey and Thiago Santos.
Toward a Dichotomy for Approximation of H-ColoringKuan Cheng, Zhengzhong Jin, Xin Li and Ke Wu.
Block Edit Errors with Transpositions: Deterministic Document Exchange Protocols and Almost Optimal Binary CodesFernando 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 LearningYair Bartal, Nova Fandina and Ofer Neiman.
Covering Metric Spaces by Few TreesBreak
Welcome Reception
12:00
12:25
12:50
13:15
14:30
14:55
15:20
15:45
16:10
16:40
17:05
17:30
17:55
18:20
18:30
20:30
9:00
Keynote Lecture 2: Mihalis Yannakakis (Columbia University, USA)
Fixed point computation problems and facets of complexity
Room: I.4, Session Chair: Paul Spirakis
10:00
Break
Track: A
Session A.1.5
Room: I.4 Chair: Benjamin Moseley
Track: A
Session A.2.5
Room: I.10 Chair: Lefteris Kirousis
Track: B
Session B.3
Room: II.9 Chair: Florin Manea
Track: C
Session C.1
Room: II.8 Chair: Evangelos Kranakis10:30
Eyal Mizrachi, Roy Schwartz, Joachim Spoerhase and Sumedha Uniyal.
A Tight Approximation for Submodular Maximization with Mixed Packing and Covering ConstraintsTobias Friedrich and Ralf Rothenberger.
The Satisfiability Threshold for Non-Uniform Random 2-SATTitouan Carette, Emmanuel Jeandel, Simon Perdrix and Renaud Vilmart.
Completeness of Graphical Languages for Mixed States Quantum MechanicsArnaud Casteigts, Joseph Peters and Jason Schoeters.
Temporal Cliques Admit Sparse Spanners10:55
Alina Ene and Huy Nguyen.
A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack ConstraintThomas Sauerwald and Luca Zanetti.
Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return ProbabilitiesHenning Urbat and Stefan Milius.
Varieties of Data LanguagesMatthias Bonne and Keren Censor-Hillel.
Distributed Detection of Cliques in Dynamic Networks11:20
Alina Ene and Huy Nguyen.
Towards Nearly-Linear Time Algorithms for Submodular Maximization with a Matroid ConstraintMatija Pasch and Konstantinos Panagiotou.
Satisfiability Thresholds for Regular Occupation ProblemsUgo Dal Lago, Francesco Gavazzo and Akira Yoshimizu.
Differential Logical Relations: The Simply-Typed CaseDariusz Kowalski and Miguel A. Mosteiro.
Polynomial Anonymous Dynamic Distributed Computing Without a Unique Leader11:45
Break
Track: A
Session A.1.6
Room: I.4 Chair: Ioannis Caragiannis
Track: A
Session A.2.6
Room: I.10 Chair: Giuseppe Italiano
Track: B
Session B.4
Room: II.9 Chair: Erich Gradel
Track: C
Session C.2
Room: II.8 Chair: Arnaud CasteigtsFedor Fomin, Petr Golovach, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi.
Covering Vectors by Spaces in Perturbed Graphic Matroids and Their DualsMassimo Equi, Roberto Grossi, Veli Mäkinen and Alexandru I. Tomescu.
On the Complexity of String Matching for GraphsThomas Place and Marc Zeitoun.
On All Things Star-FreeThomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko and Jakob Spooner.
Two Moves per Time Step Make a DifferenceAkanksha Agrawal, Fedor Fomin, Daniel Lokshtanov, Saket Saurabh and Prafullkumar Tale.
Path Contraction Faster Than 2^nGiulia Bernardini, Pawel Gawrychowski, Nadia Pisanti, Solon Pissis and Giovanna Rosone.
Even Faster Elastic-Degenerate String Matching via Fast Matrix MultiplicationAntonio Molina Lovett and Jeffrey Shallit.
Optimal Regular Expressions for PermutationsEleni 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??Fedor Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh and Meirav Zehavi.
Decomposition of Map Graphs with ApplicationsWilliam Kuszmaul.
Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the LowDistance Regime and Approximate EvaluationMohamed-Amine Baazizi, Dario Colazzo, Giorgio Ghelli and Carlo Sartiani.
A Type System for Interactive JSON Schema InferenceFrederik Mallmann-Trenn, Yannic Maus and Dominik Pajak.
Noidy Conmunixatipn: On the Convergence of the Averaging Population ProtocolLunch
Keynote Lecture 3: Frits Vaandrager (Radboud University, Netherlands)
Automata Learning and Galois Connections
Room: I.4, Session Chair: Christel Baier
Break
Track: A
Session A.1.7
Room: I.4 Chair: Aris Anagnostopoulos
Track: A
Session A.2.7
Room: I.10 Chair: Paul Spirakis
Track: B
Session B.5
Room: II.9 Chair: Anca Muscholl
Track: C
Session C.3
Room: II.8 Chair: Jukka SuomelaPavel Hrube, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao and Amir Yehudayoff.
Lower Bounds on Balancing Sets and Depth-2 Threshold CircuitsVincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee and Jason Li.
Tight FPT Approximations for k-Median and k-MeansDani Dorfman, Haim Kaplan and Uri Zwick.
A Faster Deterministic Exponential Time Algorithm for Energy Games and Mean Payoff GamesArgyrios Deligkas, John Fearnley, Themistoklis Melissourgos and Paul Spirakis.
Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam TheoremPeyman Afshani, Casper Benjamin Freksen, Lior Kamma and Kasper Green Larsen.
Lower Bounds for Multiplication via Network CodingVincent Cohen-Addad and Jason Li.
On the Fixed-Parameter Tractability of Capacitated Clustering.Kousha Etessami, Emanuel Martinov, Alistair Stewart and Mihalis Yannakakis.
Reachability for Branching Concurrent Stochastic GamesSungjin Im, Benjamin Moseley, Kirk Pruhs and Manish Purohit.
Matroid Coflow SchedulingIan Mertz, Toniann Pitassi and Yuanhao Wei.
Short Proofs Are Hard to FindPranjal Awasthi, Ainesh Bakshi, Maria-Florina Balcan, Colin White and David P.Woodruff.
Robust Communication-Optimal Distributed Clustering AlgorithmsBader Abu Radi and Orna Kupferman.
Minimizing GFG Transition-Based AutomataBreak
Special issue of TCS on M. Nivat
Room: I.4
Chair: Paul Spirakis
Chair: Paul Spirakis
EATCS General Assembly
Room: I.4
Cocktail
12:00
12:25
12:50
13:15
14:30
15:30
15:45
16:10
16:35
17:00
17:15
17:45
20:00
9:00
Keynote Lecture 4: Ola Svensson (EPFL, Switzerland)
Approximately Good and Modern Matchings
Room: I.4, Session Chair: Stefano Leonardi
10:00
Break
Track: A
Session A.1.8
Room: I.4 Chair: Josep Diaz
Track: A
Session A.2.8
Room: I.10 Chair: Karl Bringmann
Track: B
Session B.6
Room: II.9 Chair: Martin Grohe
Track: C
Session C.4
Room: II.8 Chair: Jukka Suomela10:30
Andreas Björklund, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi.
Approximate Counting of k-Paths: Deterministic and in Polynomial SpaceMikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler and Günter Rote.
Geometric MulticutPablo Barceló, Diego Figueira and Miguel Romero Orth.
Boundedness of Conjunctive Regular Path QueriesChristian Scheideler and Alexander Setzer.
On the Complexity of Local Graph Transformations10:55
Andreas Björklund and Ryan Williams.
Computing Permanents and Counting Hamiltonian Cycles by Listing Dissimilar VectorsJérémie Chalopin, Victor Chepoi, Shay Moran and Manfred K. Warmuth.
Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum ClassesLe Thanh Dung Nguyen and Pierre Pradic.
From Normal Functors to Logarithmic Space QueriesSiddharth Gupta, Adrian Kosowski and Laurent Viennot.
Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond11:20
Ivona Bezakova, Andreas Galanis, Leslie Ann Goldberg and Daniel Stefankovic.
The Complexity of Approximating the Matching Polynomial in the Complex PlaneHolger Dell, Marc Roth and Philip Wellnitz.
Counting Answers to Existential QuestionsMohsen Ghaffari and Ali Sayyadi.
Distributed Arboricity-Dependent Graph Coloring via All-to-All Communication11:45
Break
Track: A
Session A.1.9
Room: I.4 Chair: Andreas Wiese
Track: A
Session A.2.9
Room: I.10 Chair: Stefano Leonardi
Track: B
Session B.7
Room: II.9 Chair: Marc Zeitoun
Track: C
Session C.5
Room: II.8 Chair: Joseph PetersKlaus Jansen, Alexandra Lassota and Lars Rohwedder.
Near-Linear Time Algorithm for n-fold ILPs via Color CodingJohn Fearnley, Spencer Gordon, Ruta Mehta and Rahul Savani.
Unique End of Potential LineJean-Eric Pin and Christophe Reutenauer.
A Mahler's Theorem for Word FunctionsAmos Korman and Yoav Rodeh.
Multi-Round Cooperative Search Games with Multiple PlayersArturo Merino and Jose Soto.
The Minimum Cost Query Problem on Matroids with Uncertainty AreasPaul Goldberg and Alexandros Hollender.
The Hairy Ball Problem is PPAD-CompleteMatthieu Picantin.
Automatic Semigroups vs Automaton SemigroupsIoannis Caragiannis and Angelo Fanelli.
On Approximate Pure Nash Equilibria in Weighted Congestion Games with Polynomial LatenciesAdam Kurpisz.
Sum-Of-Squares Bounds via Boolean Function AnalysisJosep Díaz, Lefteris Kirousis, Sofia Kokonezi and John Livieratos.
Algorithmically Efficient Syntactic Characterization of Possibility DomainsMurray Elder and Laura Ciobanu.
Solutions Sets to Systems of Equations in Hyperbolic Groups Are EDT0L in PSPACEDaniel Schmand, Marc Schroder and Alexander Skopalik.
Network Investment Games with Wardrop FollowersLunch
Track: A
Session A.1.10
Room: I.4 Chair: Shay Solomon
Track: A
Session A.2.10
Room: I.10 Chair: Karl Bringmann
Track: B
Session B.8
Room: II.9 Chair: Jean-Eric Pin
Track: C
Session C.6
Room: II.8 Chair: Ioannis CaragiannisRan Duan, Ce Jin and Hongxun Wu.
Faster Algorithms for All Pairs Non-Decreasing Paths ProblemJulian Dörfler, Christian Ikenmeyer and Greta Panova.
On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence ObstructionsAnca Muscholl and Gabriele Puppis.
Equivalence of Finite-Valued Streaming String Transducers Is DecidableIlan Cohen, Jakubcki, Stefano Leonardi and Aris Anagnostopoulos.
Stochastic Graph ExplorationAndreas Björklund, Petteri Kaski and Ryan Williams.
Solving Systems of Polynomial Equations over GF(2) by a Parity-Counting Self-ReductionMikolaj Bojanczyk, Sandra Kiefer and Nathan Lhote.
String-to-String Interpretations With Polynomial-Size OutputShunhao Oh, Anuja Meetoo Appavoo and Seth Gilbert.
Periodic Bandits and Wireless Network SelectionAmir 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-CutsThomas Colcombet, Joël Ouaknine, Pavel Semukhin and James Worrell.
On Reachability Problems for Low-Dimensional Matrix SemigroupsPierre-Alain Reynier and Didier Villevalois.
Sequentiality of String-to-Context TransducersAlexandr Andoni, Clifford Stein and Peilin Zhong.
Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge ConnectivityAnkit Garg, Nikhil Gupta, Neeraj Kayal and Chandan Saha.
Determinant Equivalence Test over Finite Fields and over QMartin Raszyk, David Basin and Dmitriy Traytel.
From Nondeterministic to Multi-Head Deterministic Finite-State TransducersBreak
Awards Session
Chair: Paul Spirakis
Room: I.4
ICALP Best paper awards
Appointment of EATCS Fellows
Fedor Fomin, Rocco de Nicola, Dana Ron
EATCS Distinguished Dissertation Awards
Arturs Backurs, Robert Robere, Sepehr Assadi
EATCS Award
Thomas A. Henzinger
Room: I.4
Model Checking Game Properties of Multi-Agent Systems
Presburger Award
Karl Bringmann
Room: I.4
Fine-Grained Complexity of Dynamic Programming Problems
Presburger Award
Kasper Green Larsen
Room: I.4
A Quest Towards Strong Unconditional Lower Bounds
Alonso Church Award
Murdoch J. Gabbay and Andrew M. Pitts
Room: I.4
Nominal techniques, past and future
End of Awards Session
Conference Dinner
12:00
12:25
12:50
13:15
14:30
14:55
15:20
15:45
16:10
16:30
16:45
17:30
17:55
18:20
18:45
20:30
9:00
Keynote Lecture 5: Martin Grohe (RWTH Aachen University, Germany)
Symmetry and Similarity
Room: I.4, Session Chair: Anca Muscholl
10:00
Break
Track: A
Session A.1.11
Room: I.4 Chair: Christos Zaroliagis
Track: A
Session A.2.11
Room: I.10 Chair: Ioannis Caragiannis
Track: B
Session B.9
Room: II.9 Chair: Mikolaj Bojanczyk
Track: C