List of accepted papers for ICALP 2006:


TRACK A - ALGORITHMS, AUTOMATA, COMPLEXITY AND GAMES:

Burkhard Monien, Martin Gairing and Karsten Tiemann.
Routing (Un-) Splittable Flow in Games with Player-Specific Linear Latency Functions

Xin He and Huaming Zhang. 
Nearly Optimal Visibility Representations of Plane Graphs

Mohit Singh and R Ravi. Delegate and Conquer: 
An LP-based approximation algorithm for Minimum Degree MSTs

Lance Fortnow, John Hitchcock, A. Pavan, N. V. Vinodchandran and Fengming Wang. 
Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws

Naveen Garg and Amit Kumar. 
Better Algorithms for Minimizing Average Flow-time on Related Machines

Kurt Mehlhorn and Ralf Osbild. 
Reliable and Efficient Computational Geometry via Controlled Perturbation

Amin Coja-Oghlan. 
An adaptive spectral heuristic for partitioning random graphs

Oleg Verbitsky and Martin Grohe.
Testing Graph Isomorphism in Parallel by Playing a Game

Constantinos Daskalakis, Alex Fabrikant and Christos H. Papadimitriou. 
The Game World is Flat: The Complexity of Nash Equilibria in Succinct Games

Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky and Ronen Shabo. 
On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations

Michal Kunc. 
Algebraic characterization of the finite power property

Turlough Neary and Damien Woods. 
P-completeness of cellular automaton Rule 110

Gudmund Skovbjerg Frandsen and Peter Frands Frandsen. 
Dynamic Matrix Rank

I. Caragiannis, M. Flammini, C. Kaklamanis, P. Kanellopoulos and L. Moscardelli. 
Tight bounds for selfish and greedy load balancing

Jin-Yi Cai and Vinay Choudhary. 
Some Results on Matchgates and Holographic Algorithms

Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld and Kunal Talwar. 
A Push-Relabel Algorithm for Approximating Degree Bounded MSTs

Kei Uchizawa, Rodney Douglas and Wolfgang Maass. 
On the Computational Power of Threshold Circuits with Sparse Activity

G. Baier, T. Erlebach, A. Hall, E. Koehler, H. Schilling and M. Skutella.
Length-Bounded Cuts and Flows

Amin Coja-Oghlan and Andre Lanka. 
The spectral gap of random graphs with given expected degrees

Thomas Thierauf, Minh Thanh Hoang and Meena Mahajan. 
On the unique bipartite perfect matching Problem

Hristo Djidjev and Imrich Vrt'o. 
Planar Crossing Numbers of Genus g Graphs

Richard Cole, Tsvi Kopelowitz and Moshe Lewenstein. S
uffix Trays and Suffix Trists: Structures for Faster Text Indexing

Parikshit Gopalan, Phokion Kolaitis, Elitza Maneva and Christos Papadimitriou. 
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

Leah Epstein and Asaf Levin.
A robust APTAS for the classical bin packing problem

Magnus Bordewich, Martin Dyer and Karpinski Marek. 
Stopping Times, Metrics and Approximate Counting

Subhash Khot and Ashok Kumar Ponnuswami. Better Inapproximability 
Results for MaxClique, Chromatic Number and Min-3Lin-Deletion

Christos Kapoutsis. 
Small sweeping 2NFAs are not closed under complement

Kasturi Varadarajan, Bruno Codenotti and Luis Rademacher. 
Computing Equilibrium Prices in Exchange Economies with Tax Distortions

Julian Mestre. 
Weighted Popular Matchings

John Hitchcock and A. Pavan. 
Comparing Reductions to NP-Complete Sets

Thore Husfeldt and Andreas Bj?¶rklund. 
Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings

Irene Finocchi, Fabrizio Grandoni and Giuseppe F. Italiano. 
Optimal Resilient Sorting and Searching in the Presence of Memory Faults

Dániel Marx. 
A Parameterized View on Matroid Optimization Problems

Alexander Golynski. 
Optimal lower bounds for rank and select indexes

Shuheng Zhou and Satish Rao. 
Edge Disjoint Paths in Moderately Connected Graphs

Ramesh Hariharan, Telikepalli Kavitha and Kurt Mehlhorn. 
A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs

Douglas Carroll, Ashish Goel and Adam Meyerson. 
Embedding Bounded Bandwidth Graphs into $\ell_1$

Roberto Cominetti, Jose Correa and Nicolas Stier. 
Network Games with Atomic Players

David Doty, Jack Lutz and Satyadev Nandakumar. 
Finite-State Dimension and Real Arithmetic

Philip Bille. 
New Algorithms for Regular Expression Matching

Chia-Jung Lee, Chi-Jen Lu and Shi-Chun Tsai. 
Deterministic Extractors for Independent-Symbol Sources

V. Auletta, R. De Prisco, P. Penna, G. Persiano and Carmine Ventre. 
New Constructions of Mechanisms with Verification

Mikolaj Bojanczyk, Mathias Samuelides, Thomas Schwentick and Luc Segoufin. 
On the expressive power of pebble automata

Ben Reichardt. 
Fault-tolerance threshold for a distance-three quantum code (Extended abstract)

Virginia Vassilevska, Ryan Williams and Raphael Yuster. 
Finding the smallest $H$-subgraph in real weighted graphs and related problems

Deeparnab Chakrabarty, Aranyak Mehta and Vijay Vazirani. 
Towards a Theory of Intelligent Design or Design is as Easy as Optimization

Jaikumar Radhakrishnan. 
Gap amplification in PCPs using lazy random walks

Piotr Sankowski. 
Weighted Bipartite Matching in Matrix Multiplication Time

A. Kaporis, C. Makris, S. Sioutas, A. Tsakalidis, K. Tsichlas and C. Zaroliagis. 
Dynamic Interpolation Search Revisited

Xi Chen and Xiaotie Deng. 
On the Complexity of 2D Discrete Fixed Point Problem

Ronald de Wolf. 
Lower Bounds on Matrix Rigidity via a Quantum Argument

Paolo Ferragina, Giovanni Manzini and Raffaele Giancarlo. 
The Myriad Virtues of Wavelet Trees

Martin Dyer, Leslie Ann Goldberg and Mike Paterson. 
On counting homomorphisms to directed acyclic graphs

G. Blelloch, K. Dhamdhere, E. Halperin, R. Ravi, R. Schwartz and S. Sridhar. 
Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction

Toshihiro Fujito. 
How to trim an MST: A 2-approximation algorithm for minimum cost tree cover

Guy Kortsarz and Zeev Nutov. 
Tight Approximation Algorithm for Connectivity Augmentation Problems

Frederic Magniez, Dominic Mayers, Michele Mosca and Harold Ollivier. 
Self-Testing of Quantum Circuits

Arist Kojevnikov.
Exponential Lower Bound on the Size of Static Lovasz-Schrijver Calculus

Amos Korman and David Peleg. 
Dynamic Routing Schemes for General Graphs

Rolf Harren. 
Approximating the Orthogonal Knapsack Problem for Hypercubes

Spyros Kontogiannis, Dimitris Fotakis and Paul Spirakis. 
Atomic Congestion Games among Coalitions


TRACK B - LOGIC, SEMANTICS, AND THEORY OF PROGRAMMING:

Michael Benedikt and Christoph Koch. 
Interpreting Tree-to-Tree Queries

Filip Murlak. 
The Wadge Hierarchy of Deterministic Tree Languages

Colin Stirling. 
A game-theoretic approach to deciding higher-order matching

Piero A. Bonatti, Carsten Lutz, Aniello Murano and Moshe Y. Vardi. 
The Complexity of Enriched $\mu$-Calculi

Markus Lohrey and Gé©raud én©nizergues. 
Theories of HNN-extensions and amalgamated products

Radha Jagadeesan, Alan Jeffrey, Corin Pitcher and James Riely. 
LRBAC: Programming With Role-Based Access Control

Kohei Honda, Martin Berger and Nobuko Yoshida. 
Descriptive and Relative Completeness of Logics for Higher-Order Functions

Tomasz Jurdzinski. 
On Complexity of Grammars Related to the Safety Problem

Eryk Kopczynski. 
Half-positional Determinacy of Infinite Games

Luca Aceto, Wan Fokkink, Anna Ingolfsdottir and Bas Luttik. 
A finite equational base for CCS with left merge and communication merge

Qiqi Yan. 
Lower Bounds for Complementation of omega-Automata via the Full Automata Technique

Patricia Bouyer, Serge Haddad and Pierre-Alain Reynier. 
Timed Petri Nets and Timed Automata: On the Discriminating Power of Zeno Sequences

Paul Blain Levy. 
Jumbo Lambda Calculus

Kousha Etessami and Mihalis Yannakakis. 
Recursive Concurrent Stochastic Games

Blaise Genest and Anca Muscholl. 
Constructing Exponential-size Deterministic Zielonka Automata

Wong Karianto, Aloys Krieg and Wolfgang Thomas. 
On Intersection Problems for Polynomially Generated Sets

Wieslaw Zielonka and Hugo Gimbert. 
Deterministic priority mean-payoff  games as limits of  discounted games

Luca Aceto, Taolue Chen, Wan Fokkink and Anna Ingolfsdottir. 
On the Axiomatizability of Priority

Esfandiar Haghverdi. 
Typed GoI for Exponentials

Marius BOZGA, Radu IOSIF and Yassine LAKHNECH. 
Flat Parametric Counter Automata

Juhani Karhumaki, Michal Kunc and Alexander Okhotin. 
Communication of two stacks and rewriting

Stefano Guerrini and Patrizia Marzuoli. 
Commutative Locative Quantifiers for Multiplicative Linear Logic

Rasmus Ejlers Mo¸gelberg. 
Interpreting Polymorphic FPC into domain theoretic models of parametric polymorphism

Ittai Balaban, Amir Pnueli and Lenore Zuck. 
Invisible Safety of Distributed Protocols


TRACK C - SECURITY AND CRYPTOGRAPHY FOUNDATIONS:

Tamir Tassa and Nira Dyn. 
Multipartite Secret Sharing by Bivariate Interpolation

Rajeev Alur, Pavol Cerny and Steve Zdancewic. 
Preserving Secrecy under Refinement

Stéphanie Delaune, Pascal Lafourcade, Denis Lugiez and Ralf Treinen. 
Symbolic Protocol Analysis in Presence of a Homomorphism Operator and Exclusive Or

Pedro Adao and Cedric Fournet. 
Cryptographically Sound Implementations for Communicating Processes

Ivan Visconti. 
Efficient Zero Knowledge on the Internet

Damien Vergnaud. 
New Extensions of Pairing-based Signatures into Universal Designated Verifier Signatures

Rosario Gennaro and Silvio Micali. 
Independent Zero-Knowledge Sets

Detlef Kaehler, Ralf Kuesters and Thomas Wilke. 
A Dolev-Yao-based Definition of Abuse-free Protocols

Michel Abdalla, Dario Catalano, Alexander Dent, John Malone-Lee, Gregory Neven and Nigel Smart. 
Identity-Based Encryption Gone Wild

Pierre-Alain Fouque, Jacques Stern, David Pointcheval and S?©bastien Zimmer. 
Hardness of Distinguishing the MSB or LSB of Secret Keys in Diffie-Hellman and Related Schemes

Frederik Armknecht and Matthias Krause. 
Constructing single- and multi-output boolean functions with maximal immunity

Akinori Kawachi and Tomoyuki Yamakami. 
Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding

Michele Boreale. 
Quantifying  information leakage in process calculi

Duong Hieu Phan, Rei Safavi-Naini and Dongvu Tonien. 
Generic Construction of Hybrid Public Key Traitor Tracing with Full-Public-Traceability

Vivien Dubois, Louis Granboulan and Jacques Stern. 
An Efficient Provable Distinguisher for HFE

Yevgeniy Dodis and Renato Renner. 
On the Impossibility of Extracting Classical Randomness Using a Quantum Computer

Vadim Lyubashevsky and Daniele Micciancio. 
Generalized Compact Knapsacks are Collision Resistant

Douglas Wikstro¶m and Jens Groth. 
An Adaptively Secure Mix-Net Without Erasures

Krzysztof Pietrzak. 
A Tight Bound for EMAC

Daniele Micciancio and Saurabh Panjwani. 
Corrupting One vs. Corrupting Many: The Case of Broadcast and Multicast Encryption

Jun Furukawa, Kaoru Kurosawa and Hideki Imai. 
An Efficient Compiler from Sigma-Protocol to 2-move Deniable Zero-Knowledge

Iftach Haitner, Danny Harnik and Omer Reingold. 
Efficient Pseudorandom Generators from Exponentially Hard One-Way Functions

Danny Harnik and Moni Naor. 
On Everlasting Security in the Hybrid Bounded Storage Model

Ricardo Corin and Jerry den Hartog. 
A Probabilistic Hoare-style logic for Cryptographic Proofs