09:00-18:30: Workshops
19:00-21:00 ICALP Registration and Welcome Apéro.
| 08:50-09:00 | Opening Remarks (Room: ML D28) |
||
| 09:00-10:00 | Invited Lecture (Room: ML D28) — Chair: Monika Henzinger Welfare and Revenue in Ad Auctions Éva Tardos |
||
| 10:00-10:30 | Coffee Break | ||
| Session B1 (Room: CAB G11) Foundations of Program Semantics Chair: Franck van Breugel |
Session A1 (Room: CAB G61) Network Design Problems Chair: Stefano Leonardi |
Session A2 (Room: CAB G51) Quantum Computing Chair: Fedor Fomin |
|
| 10:30-11:00 | A Fragment of ML Decidable by Visibly Pushdown Automata David Hopkins, Andrzej Murawski and Luke Ong |
Improved Approximation for the Directed Spanner Problem Piotr Berman, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova and Grigory Yaroslavtsev |
On the Power of Lower Bound Methods for One-way Quantum Communication Complexity Shengyu Zhang |
| 11:00-11:30 | Krivine Machines and Higher-Order Schemes Sylvain Salvati and Igor Walukiewicz |
An Improved Approximation Algorithm for the Minimum-Cost Subset k-Connectivity Bundit Laekhanukit |
Advice Coins for Classical and Quantum Computation Scott Aaronson and Andrew Drucker |
| 11:30-12:00 | Relating Computational Effects by TT-Lifting Shin-Ya Katsumata |
Approximation schemes for capacitated geometric network design Anna Adamaszek, Artur Czumaj, Andrzej Lingas and Jakub Onufry Wojtaszczyk |
Quantum Commitments from Complexity Assumptions André Chailloux, Iordanis Kerenidis and Bill Rosgen |
| 12:00-12:30 | Constructing Differential Categories and Deconstructing Categories of Games Jim Laird, Giulio Manzonetto and Guy McCusker |
An O(log n)-competitive algorithm for online constrained forest problems Jiawei Qian and David Williamson |
Limitations on Quantum Dimensionality Reduction Ashley Montanaro, Aram Harrow and Anthony Short |
| 12:30-14:00 | Lunch Break | ||
| Session A4 (Room: CAB G11) Games, Approximation Schemes, Smoothed Analysis Chair: Stefano Leonardi |
Session A3 (Room: CAB G61) Graph Algorithms Chair: Dariusz Kowalski |
Session B2 (Room: CAB G51) Automata and Formal Languages Chair: Anca Muscholl |
|
| 14:00-14:30 | Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes Endre Boros, Khaled Elbassioni, Mahmoud Fouz, Vladimir Gurvich, Kazuhisa Makino and Bodo Manthey |
On Tree-Constrained Matchings and Generalizations Stefan Canzar, Khaled Elbassioni, Gunnar W. Klau and Julián Mestre |
Nondeterminism is Essential in Small 2FAs with Few Reversals Christos Kapoutsis |
| 14:30-15:00 | Pairwise-interaction Games Velumailum Mohanaraj and Martin Dyer |
Tight Bounds for Linkages in Planar Graphs Isolde Adler, Stavros Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh and Dimitrios Thilikos |
Isomorphism of Regular Trees and Words Markus Lohrey and Christian Mathissen |
| 15:00-15:30 | Settling the Complexity of Local Max-Cut (Almost) Completely Robert Elsässer and Tobias Tscheuschner |
A Tighter Insertion-based Approximation of the Crossing Number Markus Chimani and Petr Hliněný |
On the Capabilities of Grammars, Automata, and Transducers Controlled by Monoids Georg Zetzsche |
| 15:30-16:00 | Efficiently Decodable Error-Correcting List Disjunct Matrices and Applications Hung Ngo, Ely Porat and Atri Rudra |
Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs Ken-Ichi Kawarabayashi, Philip Klein and Christian Sommer |
The Cost of Traveling between Languages Michael Benedikt, Gabriele Puppis and Cristian Riveros |
| 16:00-16:30 | Coffee Break | ||
| Best Student Papers (Room: ML D28) Chair: Burkhard Monien |
|||
| 16:30-17:00 | A 1.488-Approximation Algorithm for the Uncapacitated Facility Location Problem Shi Li |
||
| 17:00-17:30 | Rice's Theorem for mu-Limit Sets of Cellular Automata Martin Delacourt |
||
| 17:30-18:00 | Fault-Tolerant Compact Routing Schemes for General Graphs Shiri Chechik |
||
| 18:00-22:00 | Apéro | ||
| 09:00-10:00 | Invited Lecture (Room: ML D28) — Chair: Luca Aceto Streaming String Transducers Rajeev Alur |
||
| 10:00-10:30 | Coffee Break | ||
| Session A5 (Room: CAB G11) Online Algorithms Chair: Prudence Wong |
Session B3 (Room: CAB G61) Model Checking Chair: Rajeev Alur |
Session A6 (Room: CAB G51) Data Structures, Distributed Computing Chair: Fedor Fomin |
|
| 10:30-11:00 | On Variants of File Caching Leah Epstein, Csanád Imreh, Asaf Levin and Judit Nagy-György |
Emptiness and Universality Problems in Timed Automata with Positive Frequency Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye and Amélie Stainer |
Range Majority in Constant Time and Linear Space Stephane Durocher, Meng He, Ian Munro, Patrick Nicholson and Matthew Skala |
| 11:00-11:30 | On the Advice Complexity of the k-Server Problem Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královič and Richard Královič |
Buechi Automata can have Smaller Quotients Lorenzo Clemente |
Dynamic Planar Range Maxima Queries Konstantinos Tsakalidis and Gerth Stølting Brodal |
| 11:30-12:00 | Sleep Management on Multiple Machines for Energy and Flow Time Sze-Hang Chan, Tak-Wah Lam, Lap-Kei Lee, Chi-Man Liu and Hing-Fung Ting |
Automata-based CSL Model Checking Lijun Zhang, David N. Jansen, Flemming Nielson and Holger Hermanns |
Compact Navigation and Distance Oracles for Graphs with Small Treewidth Arash Farzan and Shahin Kamali |
| 12:00-12:30 | Meeting Deadlines: How much Speed Suffices? Anand S, Naveen Garg and Nicole Megow |
A Progress Measure for Explicit-State Probabilistic Model-Checkers Franck van Breugel and Xin Zhang |
Player-Centric Byzantine Agreement Vassilis Zikas and Martin Hirt |
| 12:30-14:00 | Lunch Break | ||
| Session C1 (Room: CAB G11) Graphs Chair: Alessandro Panconesi |
Session A8 (Room: CAB G61) Submodular Optimization, Matroids Chair: Martin Dietzfelbinger |
Session A7 (Room: CAB G51) Complexity, Randomness Chair: Uli Wagner |
|
| 14:00-14:30 | Online Graph Exploration: New Results on Old and New Algorithms Nicole Megow, Kurt Mehlhorn and Pascal Schweitzer |
Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm Moran Feldman, Seffi Naor and Roy Schwartz |
Limits on the Computational Power of Random Strings Eric Allender, Luke Friedman and William Gasarch |
| 14:30-15:00 | Distance Oracles for Vertex-Labeled Graphs Danny Hermelin, Avivit Levy, Oren Weimann and Raphael Yuster |
Submodular Cost Allocation Problem and Applications Chandra Chekuri and Alina Ene |
The Decimation Process in Random k-SAT Amin Coja-Oghlan and Angelica Pachon-Pinzon |
| 15:00-15:30 | Asymptotically Optimal Randomized Rumor Spreading Benjamin Doerr and Mahmoud Fouz |
Robust Independence Systems Naonori Kakimura and Kazuhisa Makino |
Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority Frédéric Magniez, Ashwin Nayak, Miklos Santha and David Xiao |
| 15:30-16:00 | Fast Convergence for Consensus in Dynamic Networks T-H. Hubert Chan and Li Ning |
Buyback Problem - Approximate Matroid Intersection with Cancellation Costs Ashwinkumar Badanidiyuru Varadaraja |
The Fourier Entropy-Influence Conjecture for Certain Classes of Boolean Functions Ryan O'Donnell, John Wright and Yuan Zhou |
| 16:00-16:30 | Coffee Break | ||
| Best Papers (Room: ML D28) Chair: Burkhard Monien |
|||
| 16:30-17:00 | Local Matching Dynamics in Social Networks Martin Hoefer |
||
| 17:00-17:30 | Regular Languages of Words Over Countable Linear Orderings Olivier Carton, Thomas Colcombet and Gabriele Puppis |
||
| 17:30-18:00 | Algebraic Independence and Blackbox Identity Testing Malte Beecken, Johannes Mittmann and Nitin Saxena |
||
| 18:00-19:30 | EATCS General Assembly (Room: ML D28) |
||
| 09:00-10:00 | Invited Lecture (Room: ML D28) — Chair: Jiří Sgall An Introduction to Randomness Extractors Ronen Shaltiel |
|||
| 10:00-10:30 | Coffee Break | |||
| Session A9 (Room: CAB G11) Cryptography, Learning Chair: Maria Serna |
Session B4 (Room: CAB G61) Probabilistic systems Chair: James Worrell |
Session A10 (Room: CAB G51) Fixed Parameter Tractability Chair: Rolf Niedermeier |
Session C2 (Room: CAB G59) Matchings and Equilibria Chair: Monika Henzinger |
|
| 10:30-11:00 | Tamper-Proof Circuits: How to Trade Leakage for Tamper-Resilience Sebastian Faust, Krzysztof Pietrzak and Daniele Venturi |
Probabilistic Bisimulation and Simulation Algorithms by Abstract Interpretation Silvia Crafa and Francesco Ranzato |
Constraint Satisfaction Parameterized by Solution Size Andrei Bulatov and Dániel Marx |
Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem Kook Jin Ahn and Sudipto Guha |
| 11:00-11:30 | New Algorithms for Learning in Presence of Errors Sanjeev Arora and Rong Ge |
On the Semantics of Markov Automata Matthew Hennessy and Yuxin Deng |
Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization Hans L. Bodlaender, Bart M. P. Jansen and Stefan Kratsch |
Restoring Pure Equilibria to Weighted Congestion Games Konstantinos Kollias and Tim Roughgarden |
| 11:30-12:00 | (talk moved up) VC-Dimension and Shortest Path AlgorithmsIttai Abraham, Daniel Delling, Amos Fiat, Andrew Goldberg and Renato Werneck |
Runtime Analysis of Probabilistic Programs with Unbounded Recursion Tomáš Brázdil, Stefan Kiefer, Antonín Kučera and Ivana Hutarova Varekova |
Subset Feedback Vertex Set is Fixed Parameter Tractable Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk and Jakub Wojtaszczyk |
Existence and Uniqueness of Equilibria for Flows over Time Roberto Cominetti, Jose Correa and Omar Larre |
| 12:00-12:30 | (talk cancelled) Exact Learning Algorithms, Betting Games, and Circuit Lower BoundsRyan Harkins and John Hitchcock |
Approximating the termination value of One-counter MDPs and Stochastic Games Tomáš Brázdil, Václav Brožek, Kousha Etessami and Antonín Kučera |
Domination when the Stars Are Out Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen and Gerhard J. Woeginger |
Collusion in Atomic Splittable Routing Games Chien-Chung Huang |
| 12:30-14:00 | Lunch Break | |||
| 14:00-19:00 | Free for Excursions | |||
| 09:00-10:00 | Invited Lecture (Room: ML D28) — Chair: Jiří Sgall Invitation to Algorithmic Uses of Inclusion-Exclusion Thore Husfeldt |
||
| 10:00-10:30 | Coffee Break | ||
| Session A11 (Room: CAB G11) Hardness of Approximation Chair: Martin Dietzfelbinger |
Session B5 (Room: CAB G61) Logic in Computer Science Chair: Igor Walukiewicz |
Session A12 (Room: CAB G51) Counting, Testing Chair: Prudence Wong |
|
| 10:30-11:00 | A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem Subhash Khot and Per Austrin |
Generic Expression Hardness Results for Primitive Positive Formula Comparison Simone Bova, Hubie Chen and Matt Valeriote |
A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid Leslie Ann Goldberg and Mark Jerrum |
| 11:00-11:30 | Recoverable Values for Independent Sets Daniel Reichman and Uriel Feige |
Guarded Negation Vince Bárány, Balder Ten Cate and Luc Segoufin |
Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width Magnus Bordewich and Ross J. Kang |
| 11:30-12:00 | Vertex Cover in Graphs with Locally Few Colors Fabian Kuhn and Monaldo Mastrolilli |
Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-In Predicates Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt and Luc Segoufin |
Efficient Sample Extractors for Juntas with Applications Sourav Chakraborty, David García-Soriano and Arie Matsliah |
| 12:00-12:30 | Maximizing a Polynomial Subject to Assignment Constraints Konstantin Makarychev and Maxim Sviridenko |
Modular Markovian Logic Radu Mardare, Luca Cardelli and Kim Larsen |
Clique Clustering Yields a PTAS for Max-Coloring Interval Graphs Tim Nonner |
| 12:30-14:30 | Lunch Break | ||
| 14:30-16:00 | Award Ceremony (Room: ML D28) | ||
| 16:00-16:30 | Coffee Break | ||
| Session B6 (Room: CAB G11) Hybrid Systems Chair: Patricia Bouyer |
Session C3 (Room: CAB G61) Privacy and Content Search Chair: Manfred Kudlek |
Session A13 (Room: CAB G51) Complexity Chair: Thomas Erlebach |
|
| 16:30-17:00 | Programming with Infinitesimals: A While-Language for Hybrid System Modeling Kohei Suenaga and Ichiro Hasuo |
Privacy-Preserving Access of Outsourced Data via Oblivious RAM Simulation Michael Goodrich and Michael Mitzenmacher |
Robust Simulations and Significant Separations Lance Fortnow and Rahul Santhanam |
| 17:00-17:30 | Model Checking the Quantitative mu-Calculus on Linear Hybrid Systems Diana Fischer and Łukasz Kaiser |
Adaptively Secure Non-Interactive Threshold Cryptosystems Benoît Libert and Moti Yung |
A PCP Characterization of AM Andrew Drucker |
| 17:30-18:00 | On Reachability for Hybrid Automata over Bounded Time Thomas Brihaye, Laurent Doyen, Gilles Geeraerts, Joël Ouaknine, Jean-François Raskin and James Worrell |
Content Search Through Comparisons Amin Karbasi, Stratis Ioannidis and Laurent Massoulié |
Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model Markus Jalsenius and Raphael Clifford |
| 18:00-21:30 | Apéro | ||
| 09:00-10:00 | Invited Lecture (Room: ML D28) — Chair: Luca Aceto On the relation between Differential Privacy and Quantitative Information Flow Catuscia Palamidessi |
||
| 10:00-10:30 | Coffee Break | ||
| Session C4 (Room: CAB G11) Distributed Computation Chair: Roger Wattenhofer |
Session A14 (Room: CAB G61) Proof Complexity Chair: Rolf Niedermeier |
Session A15 (Room: CAB G51) Matchings and Sorting Chair: Thomas Erlebach |
|
| 10:30-11:00 | Efficient Distributed Communication in Ad-hoc Radio Networks Bogdan Chlebus, Dariusz Kowalski, Andrzej Pelc and Mariusz Rokicki |
Automatizability and Simple Stochastic Games Lei Huang and Toniann Pitassi |
Sorting by Transpositions is Difficult Laurent Bulteau, Guillaume Fertin and Irena Rusu |
| 11:00-11:30 | Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR Model Magnús Halldórsson and Pradipta Mitra |
Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds Yuval Filmus, Toniann Pitassi and Rahul Santhanam |
Popular Matchings in the Stable Marriage Problem Chien-Chung Huang and Telikepalli Kavitha |
| 11:30-12:00 | Convergence Time of Power Control Dynamics Johannes Dams, Martin Hoefer and Thomas Kesselheim |
Parameterized Bounded-Depth Frege is Not Optimal Olaf Beyersdorff, Nicola Galesi, Massimo Lauria and Alexander Razborov |
Center Stable Matchings and Centers of Cover Graphs of Distributive Lattices Christine Cheng, Eric McDermid and Ichiro Suzuki |
| 12:00-12:30 | A new Approach for Analyzing Convergence Algorithms for Mobile Robots Andreas Cord-Landwehr, Bastian Degener, Barbara Kempkes, Friedhelm Meyer Auf Der Heide, Sven Kurras, Matthias Fischer, Martina Hüllmann, Alexander Klaas, Peter Kling, Marcus Märtens, Kamil Swierkot, Christoph Raupach, Daniel Warner, Christoph Weddemann and Daniel Wonisch |
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution Jakob Nordström and Alexander Razborov |
--- |
| 12:30-14:00 | Lunch Break | ||
| Session A16 (Room: CAB G11) Constraint Satisfaction, Algebraic Complexity Chair: Jiří Sgall |
Session B7 (Room: CAB G61) Specification and Verification Chair: Catuscia Palamidessi |
Session A17 (Room: CAB G51) Steiner Problems, Clustering Chair: Uli Wagner |
|
| 14:00-14:30 | Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems Stefan Mengel |
Deciding Robustness against Total Store Ordering Ahmed Bouajjani, Roland Meyer and Eike Möhlmann |
Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs Carsten Moldenhauer |
| 14:30-15:00 | The Complexity of Symmetric Boolean Parity Holant Problems Heng Guo, Pinyan Lu and Leslie Valiant |
Multiply-Recursive Upper Bounds with Higman's Lemma Sylvain Schmitz and Philippe Schnoebelen |
Steiner Transitive-Closure Spanners of Low-Dimensional Posets Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David Woodruff and Grigory Yaroslavtsev |
| 15:00-15:30 | Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth Maurice Jansen and Rahul Santhanam |
Liveness-Preserving Atomicity Abstraction Alexey Gotsman and Hongseok Yang |
Solving the Chromatic Cone Clustering Problem via Minimum Spanning Sphere Hu Ding and Jinhui Xu |
| 15:30-16:00 | On the Power of Algebraic Branching Programs of Width Two Eric Allender and Fengming Wang |
On Stabilization in Herman's Algorithm Stefan Kiefer, Andrzej Murawski, Joël Ouaknine, James Worrell and Lijun Zhang |
Clustering with Local Restrictions Daniel Lokshtanov and Dániel Marx |
| 16:00-16:30 | Coffee Break | ||
