Detailed Program

Specific programs are also available for Track A, Track B, and Track C. You can also have a look at the Program at a Glance.

Tuesday, July 6

8:45-9:00 Opening and welcome

9:00-10:00 Invited talk - Chair: Burkhard Monien

10:30-12:30 Session 1

Track A: Combinatorial Optimization - Chair: David Peleg

  • Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse and Ljubomir Perkovic. Plane spanners of maximum degree six
  • Jop Briet, Fernando Mario de Oliveira Filho and Frank Vallentin. The positive semidefinite Grothendieck problem with rank constraint
  • Amihood Amir, Estrella Eisenberg, Avivit Levy, Ely Porat and Natalie Shapira. Cycle Detection and Correction
  • Daniel Kral. Decomposition width of matroids

Track B: Automata - Chair: Mikolaj Bojanczyk

  • Blaise Genest, Hugo Gimbert, Anca Muscholl and Igor Walukiewicz. Optimal Zielonka-Type Construction of Deterministic Asynchronous Automata
  • Pierre Chambart and Philippe Schnoebelen. Pumping And Counting On The Regular Post's Embedding Problem
  • Udi Boker, Orna Kupferman and Adin Rosenberg. Alternation Removal in Büchi Automata
  • Laurent Braud and Arnaud Carayol. Linear orders in the pushdown hierarchy

Track C: Communication in Networks - Chair: Giuseppe Persiano

  • Anna Blasiak and Robert Kleinberg. The Serializability of Network Codes
  • Dan Alistarh, Seth Gilbert, Rachid Guerraoui and Morteza Zadimoghaddam. How Efficient Can Gossip Be? (On the Message Complexity of Resilient Information Exchange)
  • Petra Berenbrink, Jurek Czyzowicz, Robert Elsasser and Leszek Gasieniec. Efficient information exchange in the random phone-call model
  • Guy Even and Moti Medina. An O(log n)-Competitive Online Centralized Randomized Packet-Routing Algorithm for Lines

14:00-16:00 Session 2

Track A: Game Theory - Chair: Giuseppe Persiano

  • MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Nicole Immorlica and Hamid Mahini. The cooperative game theory foundations of network bargaining games
  • Tobias Harks and Max Klimm. On the Existence of Pure Nash Equilibria in Weighted Congestion Games
  • Allan Borodin and Brendan Lucier. On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions
  • Albert Atserias and Elitza Maneva. Mean-payoff games and propositional proofs

Track A: Security - Chair: Hélène Kirchner

  • Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi and Piotr Sankowski. Online Network Design with Outliers
  • Benoit Libert and Moti Yung. Efficient Completely Non-Malleable Public Key Encryption
  • Tsuyoshi Ito. Polynomial-Space Approximation of No-Signaling Provers
  • Benny Applebaum, Yuval Ishai and Eyal Kushilevitz. From Secrecy to Soundness: Efficient Verification via Secure Computation

Track B: Formal Languages - Chair: Dominique Perrin

  • Mai Gehrke, Serge Grigorieff and Jean-Eric Pin. A topological approach to recognition
  • Norbert Blum. On LR(k)-parsers of polynomial size
  • Georg Zetzsche. On Erasing Productions in Random Context Grammars

16:30-18:30 Session 3

Track A: Data Structures - Chair: Nicolas Hanusse

  • Ozgur Ozkan and John Iacono. Mergeable Dictionaries
  • Jittat Fakcharoenphol, Bundit Laekhanukit and Danupon Nanongkai. Faster Algorithms for Semi-Matching Problems
  • Mingji Xia. Holographic reduction: a domain changed application and its partial converse theorems
  • Ran Duan. New Data Structures for Subgraph Connectivity

Track A: Sorting & Hashing - Chair: Boaz Patt-Shamir

  • Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh and Michael Rink. Tight Thresholds for Cuckoo Hashing via XORSAT
  • Richard Cole and Vijaya Ramachandran. Resource Oblivious Sorting on Multicores
  • Rosa M. Jiménez and Conrado Martinez. Interval Sorting

19:00-22:00 Wine and cheese reception

Wednesday, July 7

9:00-10:00 Invited talk - Chair: Claude Kirchner

10:30-12:30 Session 4

Track A: Graphs, Nets and Optimization - Chair: Nicolas Bonichon

  • Nikhil Bansal and Subhash Khot. Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
  • Anupam Gupta, Viswanath Nagarajan and R Ravi. Thresholded Covering Algorithms for Robust and Max-Min Optimization
  • Jin-Yi Cai, Xi Chen and Pinyan Lu. Graph Homomorphisms with Complex Values: A Dichotomy Theorem
  • Nikhil Bansal, Niv Buchbinder and Seffi Naor. Metrical Task Systems and the k-Server Problem on HSTs

Track B: Semantics - Chair: Jean Goubault-Larrecq

  • James Laird. Game Semantics for Call-by-Value Polymorphism
  • Martin Hofmann, Aleksandr Karbyshev and Helmut Seidl. What is a pure functional?
  • Francesco Ranzato and Roberto Giacobazzi. Example-Guided Abstraction Simplification
  • Annabelle McIver, Larissa Meinicke and Carroll Morgan. Compositional closure for Bayes Risk in probabilistic noninterference

Track C: Fault Tolerance, Ranking - Chair: Miroslaw Kutylowski

  • Nikhil Bansal, Kamal Jain, Anna Kazeykina and Joseph (Seffi) Naor. Approximation Algorithms for Diversified Search Ranking
  • Nishanth Chandran, Juan Garay and Rafail Ostrovsky. Improved Fault Tolerance and Secure Computation on Sparse Networks
  • Shiri Chechik, Yuval Emek, Boaz Patt-Shamir and David Peleg. Sparse Reliable Graph Backbones
  • Paul Bunn and Rafail Ostrovsky. Throughput-Optimal Routing in Unreliable Networks

14:00-16:00 Session 5

Track A: Scheduling - Chair: Gautier Stauffer

  • Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier, Martin Skutella, José Verschae and Andreas Wiese. Scheduling periodic tasks in a hard real-time environment
  • Anupam Gupta, Ravishankar Krishnaswamy and Kirk Pruhs. Scalably Scheduling Power-Heterogeneous Processors
  • Nikhil Bansal, Ravishankar Krishnaswamy and Viswanath Nagarajan. Better Scalable Algorithms for Broadcast Scheduling
  • Leah Epstein, Asaf Levin and Rob van Stee. Max-min online allocations with a reordering buffer

Track A: Graphs & Hypergraphs - Chair: Ralf Klasing

  • Nikolaos Fountoulakis and Konstantinos Panagiotou. Orientability of Random Hypergaphs and the Power of Multiple Choices
  • Venkatesan Guruswami and Rishi Saket. On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs
  • Juanjo Rué, Ignasi Sau and Dimitrios M. Thilikos. Dynamic Programming for Graphs on Surfaces
  • Johannes Koebler, Sebastian Kuhnert, Bastian Laubner and Oleg Verbitsky. Interval Graphs: Canonical Representation in Logspace

Track B: Graphs, Categories and Quantum Information - Chair: Samson Abramsky

  • Ross Duncan and Simon Perdrix. Rewriting measurement-based quantum computations with generalised flow
  • Bob Coecke and Aleks Kissinger. The compositional structure of multipartite quantum entanglement
  • Arend Rensink. Compositionality in Graph Transformation

16:30-18:00 Session 6 - Best Papers

Chair: Burkhard Monien

  • Leslie Ann Goldberg and Mark Jerrum. Approximating the Partition Function of the Ferromagnetic Potts Model
  • George B. Mertzios, Ignasi Sau, Mordechai Shalom and Shmuel Zaks. Placing Regenerators in Optical Networks to Satisfy Multiple Sets of Requests
  • Yijia Chen and Jörg Flum. On optimal proof systems and logics for PTIME

18:00-20:00 EATCS general Assembly

Thursday, July 8

9:00-10:00 Invited talk - Chair: Pavlos Spirakis

10:30-12:30 Session 7

Track A: Algebraic Problems - Chair: Emo Welzl

  • Amir Shpilka and Ilya Volkovich. On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors
  • Bruce Litow. On Sums of Roots of Unity
  • Holger Dell, Thore Husfeldt and Martin Wahlén. Exponential Time Complexity of the Permanent and the Tutte Polynomial
  • Amitabha Bhattacharya, Bhaskar DasGupta, Dhruv Mubayi and Gyrogy Turan. On Approximate Horn Formula Minimization

Track B: Logic - Chair: Andrzej Murawski

  • Pietro Sala, Angelo Montanari and Gabriele Puppis. Maximal decidable fragments of Halpern and Shoham’s modal logic of intervals
  • Emanuel Kieroński, Jerzy Marcinkowski and Jakub Michaliszyn. B and D are enough to make the Halpern - Shoham logic undecidable
  • Antonis Achilleos, Michael Lampis and Valia Mitsou. Parameterized Modal Satisfiability
  • Raul Leal, Gaelle Fontaine and Yde Venema. Automata for Coalgerbas: an an approach via predicate liftings

Track C: Privacy, Selfishness - Chair: Christos Kaklamanis

  • Roberto Grossi, Alessio Orlandi and Rajeev Raman. Optimal Trade-Off for Succinct String Indexes
  • T-H. Hubert Chan, Elaine Shi and Dawn Song. Private and Continual Release of Statistics
  • Ning Chen and Xiaotie Deng. Envy-Free Pricing in Multi-Item Markets
  • Giorgos Christodoulou, Katrina Ligett and Evangelia Pyrga. Contention Resolution under Selfishness

14:00-15:00 Invited talk - Chair: Samson Abramsky

15:00-19:00 Excursion

Friday, July 9

9:00-10:00 Invited talk - Chair: Friedhelm Meyer auf der Heide

10:30-12:30 Session 8

Track A: Networks & Communication Complexity - Chair: Cyril Gavoille

  • Amos Beimel, Sebastian Ben Daniel, Eyal Kushilevitz and Enav Weinreb. Choosing, Agreeing, and Eliminating in Communication Complexity
  • David Woodruff. Additive Spanners in Nearly Quadratic Time
  • Troy Lee and Shengyu Zhang. Composition theorems in communication complexity
  • Fabrizio Grandoni and Thomas Rothvoss. Network Design via Core Detouring for Problems Without a Core

Track B: Concurrency - Chair: Samson Abramsky

  • Ivan Lanese, Jorge A. Perez, Davide Sangiorgi and Alan Schmitt. On the Expressiveness of Polyadic and Synchronous Communication in Higher-Order Process Calculi
  • Daniel Hirschkoff and Damien Pous. On Bisimilarity and Substitution in Presence of Replication
  • Peter Habermehl, Roland Meyer and Harro Wimmel. The Downward-Closure of Petri net Languages
  • Tomas Brazdil, Petr Jancar and Antonin Kucera. Reachability Games on Extended Vector Addition Systems with States

Track C: Mobile Agents - Chair: Friedhelm Meyer auf der Heide

  • Andrea Clementi, Angelo Monti and Riccardo Silvestri. Modelling Mobility: A Discrete Revolution
  • Andrew Collins, Jurek Czyzowicz, Leszek Gasieniec and Arnaud Labourel. Tell me where I am so I can meet you sooner: Asynchronous rendezvous with location information
  • Jérémie Chalopin and Shantanu Das. Rendezvous of Mobile Agents without Agreement on Local Orientation
  • Jeremiah Blocki and Ryan Williams. Resolving the Complexity of Some Data Privacy Problems

14:00-16:00 Award Ceremony

16:30-18:00 Session 9

Track A: Complexity & Automata - Chair: Bruno Courcelle

  • Klaus Ambos-Spies and Timur Bakibayev. Weak Completeness Notions for Exponential Time
  • Mikołaj Bojańczyk and Paweł Parys. Efficient Evaluation of Nondeterministic Automata Using Factorization Forests
  • Tobias Jacobs, Ferdinando Cicalese, Eduardo Laber and Marco Molinaro. On the Complexity of Searching in Trees: Average-case Minimization

Track A: Finding & Testing - Chair: Moti Yung

  • Hari Krovi, Frederic Magniez, Maris Ozols and Jérémie Roland. Finding is as easy as detecting for quantum walks
  • Mahdi Cheraghchi. Improved Constructions for Non-adaptive Threshold Group Testing
  • Ronitt Rubinfeld and Ning Xie. Testing Non-uniform k-wise Independent Distributions over Product Spaces

Track B: Probabilistic Computation - Chair: Joël Ouaknine

  • Hugo Gimbert and Youssouf Oualhadj. Probabilistic Automata: Decidable and Undecidable Problems
  • Tomas Brazdil, Javier Esparza, Stefan Kiefer and Michael Luttenberger. Space-efficient scheduling of stochastically generated tasks
  • John Fearnley. Exponential Lower Bounds For Policy Iteration

18:00-23:00 Conference Diner

Saturday, July 10

9:00-10:00 Invited talk - Chair: Paul Spirakis

10:30-12:30 Session 10

Track A: Approximations - Chair: Mark Jerrum

  • Danny Segev and Iftah Gamzu. A Sublogarithmic Approximation for Highway and Tollbooth Pricing
  • Konstantin Makarychev, Rajsekar Manokaran and Maxim Sviridenko. Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm
  • Mark Greve, Allan Grønlund Jørgensen, Kasper Dalgaard Larsen and Jakob Truelsen. Cell Probe Lower Bounds and Approximations for Range Mode
  • Venkatesan Guruswami, Subhash Khot, Ryan O'Donnell, Preyas Popat, Madhur Tulsiani and Yi Wu. SDP gaps for 2-to-1 and other Label-Cover variants

Track A: Streaming & Preprocessing - Chair: Richard Cole

  • Atri Rudra and Steve Uurtamo. Data Stream Algorithms for Codeword Testing
  • Bjarni Halldorsson, Magnus M. Halldorsson, Elena Losievskaja and Mario Szegedy. Streaming algorithms for independent sets
  • Stefan Kratsch and Magnus Wahlström. Preprocessing of Min Ones Problems: A Dichotomy
  • Jian Li, Ke Yi and Qin Zhang. Clustering with Diversity

Track B: Automata - Chair: Géraud Senizergues

  • Thomas Colcombet, Denis Kuperberg and Sylvain Lombardy. Regular Temporal Cost Functions
  • Stefan Göller, Christoph Haase, Joel Ouaknine and James Worrell. Model Checking Succinct and Parametric One-Counter Automata
  • Benedikt Bollig, Paul Gastin, Benjamin Monmege and Marc Zeitoun. Pebble weighted automata and transitive closure logics
  • Krishnendu Chatterjee and Laurent Doyen. Energy Parity Games

14:00-15:30 Session 11

Track A: Adaptive, Knowledge & Optimality - Chair: Nicolas Bonichon

  • Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan and R Ravi. Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems
  • Andrew C. Yao, Moti Yung and Yunlei Zhao. Concurrent Knowledge Extraction in the Public-Key Model

Track A: Covering, Graphs & Independence - Chair: Cyril Gavoille

  • Mihai Patrascu and Mikkel Thorup. On the k-Independence Required by Linear Probing and Minwise Independence
  • Andreas Björklund, Thore Husfeldt, Mikko Koivisto and Petteri Kaski. Covering and Packing in Linear Space
  • Loukas Georgiadis. Testing 2-vertex connectivity and computing pairs of vertex-disjoint s-t paths in digraphs


Conference Information


Blix theme adapted by David Gilbert, powered by PmWiki