List of accepted papers for ICALP 2009:


TRACK A:

Erik D. Demaine, Gad Landau and Oren Weimann. 
On Cartesian Trees and Range Minimum Queries 

Oren Weimann and Raphael Yuster. 
Computing the Girth of a Planar Graph in O(n log n) Time 

Ning Chen, Nicole Immorlica, Anna Karlin, Mohammad Mahdian and Atri Rudra. 
Approximating Matches Made in Heaven 

Andre Nies. 
Superhighness and strong jump traceability 

Nikhil Bansal, Ho-Leung Chan and Kirk Pruhs. 
Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule 

Erik D. Demaine, MohammadTaghi Hajiaghayi and Philip Klein. 
Node-weighted Steiner Tree and Group Steiner Tree in Planar Graphs 

Julien Cl?ment, Brigitte Vallee, Philippe Flajolet and James Allen Fill. 
The Number of Symbol Comparisons in Quicksort and Quickselect

Amin Coja-Oghlan. 
A better algorithm for random k-SAT 

Klaus Jansen. 
An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables 

Michael Fellows, Fedor Fomin, Daniel Lokshtanov, Elena Losievskaja, Frances A. Rosamond and Saket Saurabh. 
Distortion is Fixed Parameter Tractable 

Sudipto Guha and Zhiyi Huang. 
Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams 

Amit Chakrabarti, Graham Cormode and Andrew McGregor. 
Annotations in Data Streams 

Chrisil Arackaparambil, Joshua Brody and Amit Chakrabarti. 
Functional Monitoring Without Monotonicity 

Kazuyuki Amano. 
Bounds on the Size of Small Depth Circuits for Approximating Majority 

Hiroki Morizumi. 
Limiting Negations in Formulas 

Monaldo Mastrolilli and Ola Svensson. 
Improved Bounds for Flow Shop Scheduling 

Yuriy Arbitman, Moni Naor and Gil Segev. 
De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results 

Yuval Emek, Pierre Fraigniaud, Amos Korman and Adi Rosen. 
Online Computation with Advice 

Telikepalli Kavitha, Julian Mestre and Meghana Nasre. 
Popular Mixed Matchings 

Mathieu Hoyrup and Cristobal Rojas. 
Applications of Effective Probability Theory to Martin-Loef Randomness 

Jesper Nederlof. 
Fast polynomial-space algorithms using Mobius inversion: Improving on Steiner Tree and related problems 

Stepan Holub and Dirk Nowotka. 
The Ehrenfeucht-Silberger Problem 

Bruno Durand, Alexander Shen and Andrei Romashchenko. 
High Complexity Tilings with Sparse Errors 

Eric J Mc Dermid. 
A 3/2-approximation algorithm for general stable marriage 

Parikshit Gopalan, Ryan O'Donnell, Rocco Servedio, Amir Shpilka and Karl Wimmer. 
Testing Fourier dimensionality and sparsity 

Alexandr Andoni, Piotr Indyk, Krzysztof Onak and Ronitt Rubinfeld. 
External Sampling 

Steve Chien and Alistair Sinclair. 
Strong and Pareto Price of Anarchy in Congestion Games 

Daniel Golovin. 
B-Treaps: A Uniquely Represented Alternative to B-Trees 

Hirotada Kobayashi, Francois Le Gall, Harumichi Nishimura and Martin Roetteler. 
General Scheme for Perfect Quantum Network Coding with Free Classical Communication 

Yuli Ye and Allan Borodin. 
Elimination Graphs 

Chandra Chekuri and Nitish Korula. 
A Graph Reduction Step Preserving Element-Connectivity and Applications 

Nathalie Aubrun and Marie-Pierre B?al. 
Decidability of conjugacy of tree shifts of finite type 

Adam Klivans, Phil Long and Rocco Servedio. 
Learning Halfspaces with Malicious Noise 

Tak-Wah Lam, Lap-Kei Lee, Hing-Fung Ting, Isaac To and Prudence W.H. Wong. 
Sleep with Guilt and Work Faster to Minimize Flow plus Energy 

Philip Bille and Mikkel Thorup. 
Faster Regular Expression Matching 

Venkatesan Chakaravarthy, Vinayaka Pandit, Sambuddha Roy and Yogish Sabharwal. 
Approximating Decision Trees with Multiway Branches 

Neeraj Kayal and Timur Nezhmetdinov. 
Factoring groups efficiently 

Geir Agnarsson, Magn?s M?r Halld?rsson and Elena Losievskaja. 
SDP-based Algorithms for Maximum Independent Set Problems on Hypergraphs 

Michael Dom, Daniel Lokshtanov and Saket Saurabh. 
Incompressibility through Colors and IDs 

Enav Weinreb, Eyal Kushilevitz and Jan Draisma. 
Partition Arguments in Multiparty Communication Complexity 

J?r?mie Roland and Mario Szegedy. 
Amortized communication complexity of distributions 

Noga Alon, Daniel Lokshtanov and Saket Saurabh. 
Fast FAST 

Beat Gfeller and Peter Sanders. 
Towards Optimal Range Medians 

Barna Saha and Samir Khuller. 
On Finding Dense Subgraphs 

Erik D. Demaine, MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi. 
Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs 

Arash Farzan, Rajeev Raman and Srinivasa Rao Satti. 
Universal representation of Succinct Trees? 

Marek Cygan and Marcin Pilipczuk. 
Exact and approximate Bandwidth 

Omid Amini, Fedor Fomin and Saket Saurabh. 
Counting Subgraphs via Homomorphisms 

Nir Ailon and Edo Liberty. 
Correlation Clustering Revisited: The ``True'' Cost of Error Minimization Problems 

Mikl?s Ajtai, Vitaly Feldman, Avinatan Hassidim and Jelani Nelson. 
Sorting and Selection with Imprecise Comparisons 

Harry Buhrman, Lance Fortnow and Rahul Santhanam. 
Unconditional Lower Bounds against Advice 

Arash Farzan and Ian Munro. 
Dynamic Succinct Ordered Trees 

Endre Boros and Kazuhisa Makino. 
A Fast and Simple Parallel Algorithm for the Monotone Duality Problem 

Ioannis Koutis and Ryan Williams. 
Limits and applications of group algebras for parameterized problems 

Sanjeev Arora, David Steurer and Avi Wigderson. 
Towards a study of low-complexity graphs 

Robert Elsaesser and Thomas Sauerwald. 
Tight Bounds for the Cover Time of Multiple Random Walks 

Harish Chandran, Nikhil Gopalkrishnan and John Reif. 
The Tile Complexity of Linear Assemblies 

Luca Becchetti and Elias Koutsoupias. 
Competitive analysis of aggregate max in windowed streaming 

Martin Dietzfelbinger and Michael Rink. 
Applications of a splitting trick 

Christos Koufogiannakis and Neal Young. 
Greedy $\degree$-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost 

Benjamin Doerr, Tobias Friedrich and Thomas Sauerwald. 
Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness 

Magnus M. Halldorsson and Roger Wattenhofer. 
Wireless Communication is in APX 


TRACK B:

Thomas Place and Luc Segoufin.
A decidable characterization of LT on trees 

Michael Ummels and Dominik Wojtczak. 
The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games 

Ugo Dal Lago and Simone Martini. 
On Constructor Rewrite Systems and the Lambda-Calculus 

Jean-Eric Pin and Mario J. J. Branco. 
Equations defining the polynomial closure of a lattice of regular languages 

Patricia Bouyer and Vojtech Forejt. 
Reachability in Stochastic Timed Games 

Jakub Michaliszyn. 
Decidability of the Guarded Fragment with the Transitive Closure 

Naoki Kobayashi and Luke Ong. 
Complexity of Model Checking Recursion Schemes for Fragments of the Modal Mu-Calculus 

Vincent Gripon and Olivier Serre. 
Qualitative Concurrent Games with Imperfect Information 

Martin Beaudry and Fran?ois Lemieux. 
Faithful Loops for Aperiodic E-ordered Monoids 

Philippe Chaput, Vincent Danos, Prakash Panangaden and Gordon Plotkin. 
Approximating Markov Processes By Averaging 

Jean-Pierre Jouannaud and Vincent van Oostrom. 
Diagrammatic Completion 

Christopher Broadbent. 
There is no Such Thing as an Inherently Unsafe Word Language 

Pawel Parys and Igor Walukiewicz. 
Weak Alternating Timed Automata 

Christian Dax, Felix Klaedtke and Martin Lange. 
On Regular Temporal Logics with Past 

Manuel Bodirsky, Peter Jonsson and Timo von Oertzen. 
Semilinear Program Feasibility 

Thomas Colcombet. 
The theory of stabilization monoids and regular cost functions 

Sylvie Boldo. 
Floats & Ropes: a case study for formal numerical program verification 

Achim Blumensath, Martin Otto and Mark Weyer. 
Boundedness of monadic second-order formulae over finite words 

Christel Baier, Nathalie Bertrand, Patricia Bouyer and Thomas Brihaye. 
When are Timed Automata Determinizable? 

Lucia Acciai and Michele Boreale. 
Deciding safety properties in in?nite-state pi-calculus via behavioural types 

Paul-Andr? Melli?s, Nicolas Tabareau and Christine Tasson. 
An explicit formula for the free exponential modality of linear logic 

Lars Kuhtz and Bernd Finkbeiner. 
LTL Path Checking is Efficiently Parallelizable 

Thomas Colcombet and Konrad Zdanowski. 
A Tight Lower Bound for Determinization of Buchi automata 

Jean Goubault-Larrecq and Alain Finkel.
Forward Analysis for WSTS, Part II: Complete WSTS 


TRACK C:

Sudipto Guha and Kamesh Munagala. 
Multi-armed Bandits with Metric Switching Costs 

Rosario Pugliese, Francesco Tiezzi and Nobuko Yoshida. 
On observing dynamic prioritised actions in SOC 

Damon Mosk-Aoyama and Tim Roughgarden. 
Worst-Case Efficiency Analysis of Queueing Disciplines 

Ioannis Chatzigiannakis, Othon Michail and Paul Spirakis. 
Mediated Population Protocols 

Kook Jin Ahn and Sudipto Guha. 
Graph Sparsification in the Semi-streaming Model 

Flavio Chierichetti, Silvio Lattanzi and Alessandro Panconesi. 
Rumor Spreading in Social Networks 

Andrea Clementi, Francesco Pasquale and Riccardo Silvestri. 
MANETS: High mobility can make up for low transmission power 

Dariusz Kowalski and Andrzej Pelc. 
Leader Election in Ad Hoc Radio Networks: a Keen Ear Helps 

Nitish Korula and Martin Pal.
Algorithms for Secretary Problems on Graphs and Hypergraphs 

Tobias Friedrich, Thomas Sauerwald and Dan Vilenchik. 
Smoothed Analysis of Balancing Networks 

Christian Scheideler and Stefan Schmid. 
A Distributed and Oblivious Heap 

Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian and Eli Upfal. 
Sort Me If You Can: How to Sort Dynamic Data 

Rocco De Nicola, Diego Latella, Michele Loreti and Mieke Massink. 
Rate-based Transition Systems for Stochastic Process Calculi 

Dimitris Fotakis, Alexis Kaporis and Paul Spirakis. 
Efficient Methods for Selfish Network Design 

Colin Cooper, David Ilcinkas, Ralf Klasing and Adrian Kosowski. 
Derandomizing Random Walks in Undirected Graphs Using Locally Fair Exploration Strategies 

Rachid Guerraoui and Eric Ruppert. 
Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures 

Alexander Fanghaenel, Thomas Kesselheim and Berthold Voecking. 
Improved Algorithms for Latency Minimization in Wireless Networks 

Constantinos Daskalakis and Christos Papadimitriou. 
On a Network Generalization of the Minmax Theorem 

Colin Cooper, Alan Frieze and Tomasz Radzik. 
Multiple random walks and interacting particle systems 

Li Zhang. 
Proportional response dynamics for the Fisher market 

Yossi Azar, Aleksander Madry, Thomas Moscibroda, Debmalya Panigrahi and Aravind Srinivasan. 
Maximum Bipartite Flow in Networks with Adaptive Channel Width