Program

Sunday, July 3rd, 2011

09:00-18:30: Workshops

19:00-21:00 ICALP Registration and Welcome Apéro.

Monday, July 4th, 2011

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

Tuesday, July 5th, 2011

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)

Wednesday, July 6th, 2011

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 Algorithms
Ittai 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 Bounds
Ryan 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

Thursday, July 7th, 2011

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

Friday, July 8th, 2011

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