| Monday,
11 |
Track A |
|
Track C |
| 8:45 |
|
Opening
Session |
|
| 9:00 |
|
Invited
Talk (Adi Shamir) |
|
|
|
|
|
| 10:00 |
|
Coffee /
Tea |
|
|
A.1:
Data Structures I |
|
C.1: Cryptography and Complexity |
| 10:30 |
Philip Bille and Inge Li
Gortz. |
|
Marius Zimand. |
|
The Tree Inclusion Problem:
In Optimal Space and Faster |
|
Simple extractors via
constructions of cryptographic pseudo-random generators |
| 11:00 |
Stephen
Alstrup, Inge Li Gortz, Theis Rauhe, Mikkel Thorup and Uri Zwick. |
|
Omer
Horvitz and Jonathan Katz |
|
Union-Find with Constant
Time Deletions |
|
Bounds on the Efficiency of
``Black-Box'' Commitment Schemes |
| 11:30 |
Gianni
Franceschini and Roberto Grossi. |
|
Hoeteck Wee |
|
Optimal In-Place Sorting of
Vectors and Records |
|
On Round-Efficient Argument
Systems |
| 12:00 |
Kanela
Kaligosi, Kurt Mehlhorn, J. Ian Munro and Peter Sanders |
|
Roberto
Tamassia and Nikos Triandopoulos |
|
Towards Optimal Multiple
Selection |
|
Computational Bounds on
Hierarchical Data Processing with Applications to Information Security |
| 12:30 |
|
Lunch |
|
|
A.2: Data Structures II |
|
C.2: Cryptography and Distributed Systems |
| 14:00 |
Martin Dietzfelbinger and
Christoph Weidling |
|
Klaus Kursawe and Victor
Shoup |
|
Balanced Allocation and
Dictionaries with Tightly Packed Constant Size Bins |
|
Optimistic Asynchronous
Atomic Broadcast |
| 14:30 |
Ehsan
Chiniforooshan, Arash Farzan and Mehdi Mirzazadeh |
|
Giovanni Di
Crescenzo and Aggelos Kiayias |
|
Worst Case Optimal
Union-Intersection Expression Evaluation |
|
Asynchronous Perfectly
Secure Communication over One-time Pads |
| 15:00 |
Fedor V.
Fomin, Fabrizio Grandoni and Dieter Kratsch |
|
Giuseppe
Persiano and Ivan Visconti |
|
Measure and Conquer:
Domination - A Case Study |
|
Single-Prover Concurrent
Zero Knowledge in Almost Constant Rounds |
| 15:30 |
|
Coffee / Tea |
|
|
A.3: Graph Algorithms I |
|
C.3: Security Mechanisms |
| 16:00 |
Miroslaw Kowaluk and
Andrzej Lingas |
|
Tal Moran and Moni Naor |
|
LCA queries in directed
acyclic graphs |
|
Basing Cryptographic
Protocols on Tamper-Evident Seals |
| 16:30 |
Liam
Roditty and Uri Zwick |
|
Dario
Catalano and Ivan Visconti |
|
Replacement paths and k
simple shortest paths in unweighted directed graphs |
|
Hybrid Trapdoor Commitments
and their Applications |
| 17:00 |
Liam
Roditty, Mikkel Thorup and Uri Zwick |
|
Nicholas
Hopper |
|
Deterministic constructions
of approximate distance oracles and spanners |
|
On Steganographic Chosen
Covertext Security |
| 17:30 |
Telikepalli
Kavitha |
|
An Braeken,
Yuri Borissov, Svetla Nikova and Bart Preneel |
|
An Õ(m2n) Randomized Algorithm to compute a Minimum Cycle Basis of
a Directed Graph |
|
Classification of Boolean
Functions of 6 Variables or Less with Respect to Cryptographic Properties |
| 18:00 |
|
Reception |
|
|
|
|
|
|
|
|
|
| Tuesday, 12 |
Track A |
Track A |
Track C |
| 9:00 |
|
Invited
Talk (Leslie Valiant) |
|
|
|
|
|
| 10:00 |
|
Coffee /
Tea |
|
|
A.4.1: Graph Algorithms I |
A.4.2: Automata and Formal Languages I |
C.4: Signature and Message Authentication |
| 10:30 |
Reuven
Cohen, Pierre Fraigniaud, David Ilcinkas, Amos Korman and David Peleg |
Juraj Hromkovic and Georg Schnitger |
Eike Kiltz, Anton Mityagin, Saurabh Panjwani and Barath Raghavan |
|
Label-Guided Graph
Exploration by a Finite Automaton |
NFAs with
and without e-transitions |
Append-Only
Signatures |
| 11:00 |
Bogdan
Chlebus, Leszek Gasieniec, Dariusz Kowalski and Tomasz Radzik |
Marie-Pierre Beal, Sylvain Lombardy and Jacques Sakarovitch |
Marten Trolin and Douglas Wikstrom |
|
On the Wake-up Problem in
Radio Networks |
On the
equivalence of Z-automata |
Hierarchical
Group Signatures |
| 11:30 |
Jiri Fiala,
Peter Golovach and Jan Kratochvil |
Eugen Czeizler and Jarkko Kari |
Helger Lipmaa, Guilin Wang and Feng Bao |
|
Distance constrained
labelings of graphs of bounded treewidth |
A tight
linear bound on the neighborhood of inverse cellular automata |
Designated
Verifier Signature Schemes: Attacks, New Security Notions and A New
Construction |
| 12:00 |
Qian-Ping
Gu and Hisao Tamaki |
Martin Beaudry, Francois Lemieux and Denis Therien |
Ueli Maurer and Johan Sjodin |
|
Optimal
branch-decomposition of planar graphs in O(n3) time |
Groupoids
that recognize only regular languages |
Single-Key
AIL-MACs from any FIL-MAC |
| 12:30 |
|
Lunch |
|
| 14:00 |
|
Invited Talk (John
Mitchell) |
|
|
|
|
|
|
A.5.1: Algorithmic Game Theory |
A.5.2: Automata and Logic |
C.5: Computational Algebra |
| 15:00 |
Li Zhang |
Manfred Droste and Paul
Gastin |
Mitsuhiro
Haneda, Mitsuru Kawazoe and Tetsuya Takahashi |
|
The efficiency and fairness
of a fixed budget resource allocation game |
Weighted automata and
weighted logics |
Suitable
Curves for Genus-4 HCC over Prime Fields: Point Counting Formulae for
Hyperelliptic Curves of Type y2=x{2k+1}+ax |
| 15:30 |
Henry Lin,
Tim Roughgarden, Eva Tardos and Asher Walkover |
Pascal
Tesson and Denis Thérien |
Neeraj Kayal |
|
Braess's Paradox, Fibonacci
Numbers, and Exponential Inapproximability |
Restricted Two-Variable
FO+MOD Sentences, Circuits and Communication Complexity |
Solvability
of a System of Bivariate Polynomial Equations over a Finite Field |
| 16:00 |
|
Coffee / Tea |
|
|
A.6.1: Cache-Oblivious Algorithms and Algorithmic Engineering |
A.6.2: On-line Algorithms |
C.6: Security Protocols Logic |
| 16:30 |
Hema Jampala and Norbert
Zeh |
Leah Epstein and Meital
Levy |
Chevalier
Yannick and Rusinowitch Michael |
|
Cache-Oblivious Planar
Shortest Paths |
Online Interval Coloring
and Variants |
Combining
Intruder Theories |
| 17:00 |
Gerth
Brodal, Rolf Fagerberg and Gabriel Moruz |
Wun-Tat
Chan, Tak-Wah Lam and Prudence Wong |
Mathieu Baudet, Veronique Cortier and Steve Kremer |
|
Cache-Aware and
Cache-Oblivious Adaptive Sorting |
Dynamic Bin Packing of Unit
Fractions Items |
Computationally
sound implementations of equational theories against passive adversaries |
| 17:30 |
Ingo
Wegener |
Matthias
Englert and Matthias Westermann |
Martín Abadi and Bogdan Warinschi |
|
Simulated annealing beats
Metropolis in combinatorial optimization |
Reordering Buffer
Management for Non-Uniform Cost Models |
Password-Based
Encryption Analyzed |
| 18:00-19:00 |
|
EATCS
General Assembly |
|
|
|
|
|
|
|
|
|
| Wednesday, 13 |
Track A |
Track B |
Track C |
| 9:00 |
|
Invited
Talk (Giuseppe Castagna) |
|
| 10:00 |
|
Coffee / Tea |
|
|
A.7: Random Graphs |
B.1: Concurrency I |
C.7: Encryption and related Primitives |
| 10:30 |
Chen Avin
and Gunes Ercal |
Damien Pous |
Marc Fischlin |
|
On The Cover Time of Random
Geometric Graphs |
Up-to Techniques for Weak
Bisimulation |
Completely
Non-Malleable Schemes |
| 11:00 |
Charilaos
Efthymiou and Paul Spirakis |
Eric Badouel, Jules Chenou and Goulven Guillou |
David Galindo |
|
On the Existence of
Hamiltonian Cycles in Random Intersection Graphs |
Petri Algebras |
Boneh-Franklin
Identity Based Encryption Revisited |
| 11:30 |
Nedialko B.
Dimitrov and C. Greg Plaxton |
Wan Fokkink and Sumit Nain |
Craig Gentry and Zulfikar Ramzan |
|
Optimal Cover Time for a
Graph-Based Coupon Collector Process |
A Finite Basis for Failure
Semantics |
Single-Database
Private Information Retrieval with Constant Communication Rate |
| 12:00 |
Debora
Donato, Stefano Leonardi and Panayiotis Tsaparas |
Giovanni Conforti, Damiano Macedonio and Vladimiro Sassone |
Giovanni Di Crescenzo and Ivan Visconti |
|
Stability and Similarity of
Link Analysis Ranking algorithms |
Spatial Logics for Bigraphs |
Concurrent
Zero-Knowledge in the Public-Key Model |
| 12:30 |
|
Lunch |
|
| 14:30 |
|
Excursion |
|
|
|
|
|
|
|
|
|
| Thursday, 14 |
Track A |
Track A |
Track B |
| 9:00 |
|
Invited
Talk (Burkhard Monien) |
|
|
|
|
|
| 10:00 |
|
Coffee / Tea |
|
|
A.9.1: Approximation Algorithms I |
|
B.2: Games |
| 10:30 |
Martin
Gairing, Burkhard Monien and Andreas Woclaw |
|
Krishnendu
Chatterjee, Luca de Alfaro and Thomas A. Henzinger |
|
A Faster Combinatorial
Approximation Algorithm for Scheduling Unrelated Parallel Machines |
|
The Complexity of
Stochastic Rabin and Streett Games |
| 11:00 |
Annamaria
Kovacs |
|
Kousha
Etessami and Mihalis Yannakakis |
|
Polynomial Time Preemptive
Sum-Multicoloring on Paths |
|
Recursive Markov Decision
Processes and Recursive Stochastic Games |
| 11:30 |
Kamal Jain,
MohammadTaghi Hajiaghayi and Kunal Talwar |
|
James Laird |
|
The Generalized Deadlock
Resolution Problem |
|
Decidability in
Syntactic Control of Interference |
| 12:00 |
Mihai
Badoiu, Artur Czumaj, Piotr Indyk and Christian Sohler |
|
Andrzej S.
Murawski, C.-H. L. Ong and Igor Walukiewicz |
|
Facility Location in
Sublinear Time |
|
Idealized Algol with Ground
Recursion, and DPDA Equivalence |
| 12:30 |
|
Lunch |
|
| 14:00 |
|
Invited Talk (Leonid
Libkin) |
|
|
|
|
|
|
A.9.1: Approximation Algorithms II |
A.9.2: Lower Bounds |
B.3: Probability |
| 15:00 |
Jochen
Konemann, Stefano Leonardi, Guido Schafer and Stefan van Zwam |
Corina E. Patrascu and Mihai Patrascu |
Michael Mislove |
|
From Primal-Dual to Cost
Shares and Back: A Stronger LP Relaxation for the Steiner Forest Problem |
On Dynamic
Bit-Probe Complexity |
Discrete Random Variables
Over Domains |
| 15:30 |
David
Cashman, Avner Magen and Allan Borodin |
Scott Diehl and Dieter Van Melkebeek |
Franck van Breugel, Claudio Hermida, Michael Makkai and James
Worrell |
|
How well can Primal-Dual
and Local-Ratio algorithms perform? |
Time-Space
Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines |
An Accessible
Approach to Behavioural Pseudometrics |
| 16:00 |
Gustav Hast |
Arkadev Chattopadhyay and Kristoffer Arnsfelt Hansen |
Eugene Asarin and Pieter Collins |
|
Approximating Max kCSP -
outperforming a random assignment with almost a linear factor |
Lower
Bounds for Circuits With Few Modular and Symmetric Gates |
Noisy Turing Machines |
| 16:30 |
|
Coffee /
Tea |
|
| 16:45-17:30 |
|
EATCS Awards Ceremony |
|
| 17:30-18:15 |
|
Elsevier /
TCS Prize Cerimony |
|
| 18:15-18:30 |
|
Drinks |
|
|
|
|
|
| 20:00 |
|
ICALP Dinner |
|
|
|
|
|
| Friday, 15 |
Track A |
Track A |
Track B |
|
A.10: Approximation Algorithms III |
|
B.4: Automata and Formal Languages II |
| 9:00 |
George Karakostas |
|
Martin Grohe, Christoph
Koch and Nicole Schweikardt |
|
A better approximation
ratio for the Vertex Cover problem |
|
Tight Lower Bounds for
Query Processing on Streaming and External Memory Data |
| 9:30 |
Anupam
Gupta and Martin Pal |
|
Parosh
Abdulla, Johann Deneux, Joel Ouaknine and James Worrell |
|
Stochastic Steiner Trees
without a Root |
|
Decidability and Complexity
Results for Timed Automata via Channel Machines |
| 10:00 |
Sriram
Pemmaraju and Rajiv Raman |
|
Rajeev
Alur, Viraj Kumar, P. Madhusudan and Mahesh Viswanathan |
|
Approximation Algorithms
for the Max-Coloring Problem |
|
Congruences for Visibly
Pushdown Languages |
| 10:30 |
|
Coffee /
Tea |
|
|
A.11. 1. Approximation Algorithms IV |
A.11.2: Algebraic Computation and Communication Complexity |
B.5: Concurrency II |
| 11:00 |
Khaled
Elbassioni, Aleksei V. Fishkin, Nabil H. Mustafa and Rene Sitters |
Jeff Ford and Anna Gal |
Michael Baldamus, Joachim Parrow and Bjorn Victor |
|
Approximation Algorithms
for Euclidean Group TSP |
Hadamard
tensors and lower bounds on multiparty communication complexity |
A Fully
Abstract Encoding of the pi-Calculus with Data Terms |
| 11:30 |
David
Kempe, Jon Kleinberg and Eva Tardos |
Paul Beame, Toniann Pitassi and Nathan Segerlind |
Mohammad Reza Mousavi and Michel A. Reniers |
|
Influential Nodes in a
Diffusion Model for Social Networks |
Lower
bounds for Lovasz-Schrijver systems and beyond, using multiparty
communication |
Orthogonal
Extensions in Structural Operational Semantics |
| 12:00 |
Christoph
Ambuhl |
Douglas Wikstrom |
Rocco De Nicola, Daniele Gorla and Rosario Pugliese |
|
An Optimal Bound for the
MST Algorithm to Compute Energy Efficient Broadcast Trees in Wireless
Networks |
On the
l-Ary GCD-Algorithm in Rings of Integers |
Basic
Observables for a Calculus for Global Computing |
| 12:30 |
Friedrich
Eisenbrand, Fabrizio Grandoni, Gianpaolo Oriolo and Martin Skutella |
|
Giorgio
Delzanno and Maurizio Gabbrielli |
|
New Approaches for Virtual
Private Network Design |
|
Compositional Verification
of Asynchronous Processes via Constraint Solving |
| 13:00 |
|
Lunch |
|
|
A.12.1: String Matching and Computational Biology |
A.12.2: Quantum Complexity |
B.6: Analysis and Verification |
| 14:30 |
Martin
Farach-Colton, Gad M. Landau, S. Cenk Sahinalp and Dekel Tsur |
Pascal Koiran, Vincent Nesme and Natacha Portier |
Roberto Giacobazzi and Mila Dalla Preda |
|
Optimal spaced seeds for
faster approximate string matching |
A quantum
lower bound for the query complexity of Simon's problem |
Semantic-based
Code Obfuscation by Abstract Interpretation |
| 15:00 |
Isaac Elias
and Jens Lagergren |
Robert Spalek and Mario Szegedy |
Bernhard Reus and Thomas Streicher |
|
Fast Neighbor Joining |
All
Quantum Adversary Methods are Equivalent |
About
Hoare Logics for Higher-order Store |
| 15:30 |
Manan
Sanghi, Ming-Yang Kao and Robert Schweller |
Frederic Magniez and Ashwin Nayak |
Aaron Bradley, Zohar Manna and Henny Sipma |
|
Randomized Fast Design of
Short DNA Words |
Quantum
Complexity of Testing Group Commutativity |
The
Polyranking Principle |
| 16:00 |
|
Coffee /
Tea |
|
|
A.13.1: Geometry and Load Balancing |
A.13.2: Concrete Complexity and Codes |
B.7: Model Theory and Model Checking |
| 16:30 |
Bengt J.
Nilsson |
Jaikumar Radhakrishnan, Martin Roetteler and Pranab Sen |
Albert Atserias, Anuj Dawar and Martin Grohe |
|
Approximate Guarding of
Monotone and Rectilinear Polygons |
On the
Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the
Heisenberg Group |
Preservation
under Extensions on Well-Behaved Finite Structures |
| 17:00 |
Amit Kumar,
Yogish Sabharwal and Sandeep Sen |
Matthew Cary, Atri Rudra and Ashish Sabharwal |
Teodor Knapik, Damian Niwinski, Pawel Urzyczyn and Igor Walukiewicz
|
|
Linear Time Algorithms for
Clustering Problems in any dimensions |
On the
Hardness of Embeddings Between Two Finite Metrics |
Unsafe grammars and panic
automata |
| 17:30 |
Petra
Berenbrink, Tom Friedetzky and Russell Martin |
Stephanie Wehner and Ronald de Wolf |
Cheng Li, Zhe Dang, Oscar Ibarra and Hsu-Chun Yen |
|
Dynamic Diffusion Load
Balancing |
Improved
Lower Bounds for Locally Decodable Codes and Private Information Retrieval |
Signaling
P Systems and Verification Problems |
| 18:00 |
|
Closure |
|
|
|
|
|
