Ca' Foscari logo ICALP 2006
33rd International Colloquium on
Automata, Languages and Programming

July 9 - 16, 2006
S. Servolo, Venice - Italy


Monday 10.7 Track A   Track C
8:50 - 9:00 Opening
9:00 - 10:00 Invited talk - Alon Noga: Additive Approximation for Edge-Deletion Problems
10:00 - 10:30 Coffee Break
10:30 - 12:30 A.1 - Graph Theory   C.1 - Zero Knowledge and Signatures
  Martin Grohe and Oleg Verbitsky   Ivan Visconti
  Testing Graph Isomorphism in Parallel by Playing a Game   Efficient Zero Knowledge on the Internet
  Amin Coja-Oghlan and Andre Lanka   Jun Furukawa, Kaoru Kurosawa and Hideki Imai
  The spectral gap of random graphs with given expected degrees   An Efficient Compiler from Sigma-Protocol to 2-move Deniable Zero-Knowledge
  Douglas Carroll, Ashish Goel and Adam Meyerson   Damien Vergnaud
  Embedding Bounded Bandwidth Graphs into $\ell_1$   New Extensions of Pairing-based Signatures into Universal Designated Verifier Signatures
  Martin Dyer, Leslie Ann Goldberg and Mike Paterson   Rosario Gennaro and Silvio Micali
  On counting homomorphisms to directed acyclic graphs   Independent Zero-Knowledge Sets
12:30 - 14:30 Lunch
14:30 - 16:00 A.2 - Quantum Computing   C.2 - Cryptographic protocols
  Ben Reichardt   Daniele Micciancio and Saurabh Panjwani
  Fault-tolerance threshold for a distance-three quantum code (Extended abstract)   Corrupting One vs. Corrupting Many: The Case of Broadcast and Multicast Encryption
  Ronald de Wolf   Pedro Adao and Cedric Fournet. 
  Lower Bounds on Matrix Rigidity via a Quantum Argument   Cryptographically Sound Implementations for Communicating Processes
  Frederic Magniez, Dominic Mayers, Michele Mosca and Harold Ollivier   Detlef Kähler, Ralf Küsters and Thomas Wilke
  Self-Testing of Quantum Circuits    A Dolev-Yao-based Definition of Abuse-free Protocols
16:00 - 16:30 Coffee Break
16:30 - 18:00 A.3 - Randomness   C.3 - Secrecy and protocol analysis
  Chia-Jung Lee, Chi-Jen Lu and Shi-Chun Tsai   Rajeev Alur, Pavol Cerny and Steve Zdancewic. 
  Deterministic Extractors for Independent-Symbol Sources    Preserving Secrecy under Refinement
  Jaikumar Radhakrishnan   Michele Boreale. 
  Gap amplification in PCPs using lazy random walks   Quantifying information leakage in process calculi
  Magnus Bordewich, Martin Dyer and Karpinski Marek   S. Delaune, P. Lafourcade, D. Lugiez and R. Treinen 
  Stopping Times, Metrics and Approximate Counting    Symbolic Protocol Analysis in Presence of a Homomorphism Operator and Exclusive Or
18:00 - 18:30 IBM talk - Birgit Pfitzmann: Security and privacy challenges in industrial research
18:30 - 20:00 Welcome Reception
Tuesday 11.7 Track A Track A  Track C
9:00 - 10:00 Invited talk - Cynthia Dwork: Differential Privacy
10:00 - 10:30 Coffee Break
10:30 - 12:30 A.4.1 - Formal Languages A.4.2 - Approximation Algorithms I  C.4 - Cryptographic primitives
  Michal Kunc Mohit Singh and R Ravi Vadim Lyubashevsky and Daniele Micciancio. 
  Algebraic characterization of the finite power property Delegate and Conquer: An LP-based approximation algorithm for Minimum Degree MSTs  Generalized Compact Knapsacks are Collision Resistant
  Turlough Neary and Damien Woods Naveen Garg and Amit Kumar Vivien Dubois, Louis Granboulan and Jacques Stern. 
  P-completeness of cellular automaton Rule 110 Better Algorithms for Minimizing Average Flow-time on Related Machines  An Efficient Provable Distinguisher for HFE
   Christos Kapoutsis Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld and Kunal Talwar Krzysztof Pietrzak. 
  Small sweeping 2NFAs are not closed under complement  A Push-Relabel Algorithm for Approximating Degree Bounded MSTs A Tight Bound for EMAC
  Mikolaj Bojanczyk, Mathias Samuelides, Thomas Schwentick and Luc Segoufin Shuheng Zhou and Satish Rao Frederik Armknecht and Matthias Krause. 
  On the expressive power of pebble automata  Edge Disjoint Paths in Moderately Connected Graphs  Constructing single- and multi-output Boolean functions with maximal immunity
12:30 - 14:30 Lunch
14:30 - 16:00 A.5.1 - Approximation Algorithms II A.5.2 - Graph Algorithms I C.5 - Bounded storage and quantum models
  Leah Epstein and Asaf Levin Ramesh Hariharan, Telikepalli Kavitha and Kurt Mehlhorn Danny Harnik and Moni Naor. 
  A robust APTAS for the classical bin packing problem  A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs  On Everlasting Security in the Hybrid Bounded Storage Model
  Subhash Khot and Ashok Kumar Ponnuswami Virginia Vassilevska, Ryan Williams and Raphael Yuster Yevgeniy Dodis and Renato Renner. 
  Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion Finding the smallest H-subgraph in real weighted graphs and related problems  On the Impossibility of Extracting Classical Randomness Using a Quantum Computer
  Rolf Harren Piotr Sankowsk Akinori Kawachi and Tomoyuki Yamakami. 
  Approximating the Orthogonal Knapsack Problem for Hypercubes Weighted Bipartite Matching in Matrix Multiplication Time  Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding 
16:00 - 16:30 Coffee Break
16:30 - 18:00 A.6.1 - Algorithms I  A.6.2 - Complexity I  C.6 - Foundations
  Irene Finocchi, Fabrizio Grandoni and Giuseppe F. Italiano Arist Kojevnikov Iftach Haitner, Danny Harnik and Omer Reingold. 
  Optimal Resilient Sorting and Searching in the Presence of Memory Faults Exponential Lower Bound on the Size of Static Lovasz-Schrijver Calculus Efficient Pseudorandom Generators from Exponentially Hard One-Way Functions
  Kurt Mehlhorn and Ralf Osbild Lance Fortnow, John Hitchcock, A. Pavan, N. V. Vinodchandran and Fengming Wang Pierre-Alain Fouque, Jacques Stern, David Pointcheval and Sebastien Zimmer. 
  Reliable and Efficient Computational Geometry via Controlled Perturbation Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws Hardness of Distinguishing the MSB or LSB of Secret Keys in Diffie-Hellman and Related Schemes
   I. Caragiannis, M. Flammini, C. Kaklamanis, P. Kanellopoulos and L. Moscardelli Parikshit Gopalan, Phokion Kolaitis, Elitza Maneva and Christos Papadimitriou Ricardo Corin and Jerry den Hartog. 
  Tight bounds for selfish and greedy load balancing The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies  A Probabilistic Hoare-style logic for Game-based Cryptographic Proofs
18:00 - 19:30 EATCS Assembly
Wednesday 12.7 Track A Track B Track C
9:00 - 10:00 Invited talk - Simon Peyton Jones: Composable memory transactions
10:00 - 10:30 Coffee Break
10:30 - 12:30 A.7 - Data Structures and Linear Algebra B.1 - Games C.7 - Multi-party protocols
  Richard Cole, Tsvi Kopelowitz and Moshe Lewenstein Wieslaw Zielonka and Hugo Gimbert Duong Hieu Phan, Rei Safavi-Naini and Dongvu Tonien. 
  Suffix Trays and Suffix Trists: Structures for Faster Text Indexing  Deterministic priority mean-payoff  games as limits of discounted games  Generic Construction of Hybrid Public Key Traitor Tracing with Full-Public-Traceability
  Alexander Golynski Kousha Etessami and Mihalis Yannakakis. Douglas Wikström and Jens Groth. 
  Optimal lower bounds for rank and select indexes  Recursive Concurrent Stochastic Games An Adaptively Secure Mix-Net Without Erasures 
  A. Kaporis, C. Makris, S. Sioutas, A. Tsakalidis, K. Tsichlas and C. Zaroliagis Eryk Kopczynski Tamir Tassa and Nira Dyn. 
  Dynamic Interpolation Search Revisited Half-positional Determinacy of Infinite Games  Multipartite Secret Sharing by Bivariate Interpolation
  Gudmund Skovbjerg Frandsen and Peter Frands Frandsen Colin Stirling Michel Abdalla, Dario Catalano, Alexander Dent, John Malone-Lee, Gregory Neven and Nigel Smart. 
  Dynamic Matrix Rank A game-theoretic approach to deciding higher-order matching Identity-Based Encryption Gone Wild
12:30 - 14:30 Lunch
14:30 - 20:00 Excursion
Thursday 13.7 Track A Track A  Track B
9:00 - 10:00 Invited talk - Prakash Panangaden: The One Way to Quantum Computation
10:00 - 10:30 Coffee Break
10:30 - 12:30 A.8.1 - Graphs  A.8.2 - Complexity II B.2 - Semantics
  Xin He and Huaming Zhang Thomas Thierauf, Minh Thanh Hoang and Meena Mahajan Kohei Honda, Martin Berger and Nobuko Yoshida
  Nearly Optimal Visibility Representations of Plane Graphs  On the unique bipartite perfect matching Problem Descriptive and Relative Completeness of Logics for Higher-Order Functions
  Hristo Djidjev and Imrich Vrt'o John Hitchcock and A. Pavan Paul Blain Levy
  Planar Crossing Numbers of Genus g Graphs Comparing Reductions to NP-Complete Sets Jumbo Lambda Calculus 
  Toshihiro Fujito Deeparnab Chakrabarty, Aranyak Mehta and Vijay Vazirani Esfandiar Haghverdi
  How to trim an MST: A 2-approximation algorithm for minimum cost tree cover Towards a Theory of Intelligent Design or Design as Easy as Optimization  Typed GoI for Exponentials
  Guy Kortsarz and Zeev Nutov Xi Chen and Xiaotie Deng Stefano Guerrini and Patrizia Marzuoli
  Tight Approximation Algorithm for Connectivity Augmentation Problems On the Complexity of 2D Discrete Fixed Point Problem  Commutative Locative Quantifiers for Multiplicative Linear Logic
12:30 - 14:30 Lunch
14:30 - 16:00 A.9.1 - Game Theory I A.9.2 - Algorithms B.3-  Automata I 
  Burkhard Monien, Martin Gairing and Karsten Tiemann David Doty, Jack Lutz and Satyadev Nandakumar Filip Murlak
  Routing (Un-) Splittable Flow in Games with Player-Specific Linear Latency Functions  Finite-State Dimension and Real Arithmetic  The Wadge Hierarchy of Deterministic Tree Languages
  Constantinos Daskalakis, Alex Fabrikant and Christos H. Papadimitriou Thore Husfeldt and Andreas Björklund Patricia Bouyer, Serge Haddad and Pierre-Alain Reynier
  The Game World is Flat: The Complexity of Nash Equilibria in Succinct Games Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings Timed Petri Nets and Timed Automata: On the Discriminating Power of Zeno Sequences
  Roberto Cominetti, Jose R. Correa and Nicolas E. Stier-Moses Paolo Ferragina, Giovanni Manzini and Raffaele Giancarlo Tomasz Jurdzinski
  Network Games with Atomic Players The Myriad Virtues of Wavelet Trees  On Complexity of Grammars Related to the Safety Problem
16:00 - 16:30 Coffee Break
16:30 - 18:00 Award Ceremony
20:00 - 23:00 ICALP Banquet
Friday 14.7 Track A Track B  
9:00 - 10:30 A.10 - Game Theory II B.4 - Models  
  Dimitris Fotakis, Spyros Kontogiannis and Paul Spirakis Rasmus Ejlers Møgelberg  
  Atomic Congestion Games among Coalitions  Interpreting Polymorphic FPC into domain theoretic models of parametric polymorphism  
  Kasturi Varadarajan, Bruno Codenotti and Luis Rademacher Radha Jagadeesan, Alan Jeffrey, Corin Pitcher and James Riely.  
  Computing Equilibrium Prices in Exchange Economies with Tax Distortions  LRBAC: Programming With Role-Based Access Contro  
  V. Auletta, R. De Prisco, P. Penna, G. Persiano and C. Ventre Juhani Karhumaki, Michal Kunc and Alexander Okhotin  
  New Constructions of Mechanisms with Verification  Communication of two stacks and rewriting   
10:30 -- 11:00 Coffee Break
11:00 -- 13:00 A.11 - Networks, Circuits and Regular Expressions B.5 - Equations   
   A. Fiat, H. Kaplan., M.Levy, S. Olonetsky and R. Shabo Luca Aceto, Taolue Chen, Wan Fokkink and Anna Ingolfsdottir  
  On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations  On the Axiomatizability of Priority  
  Amos Korman and David Peleg Luca Aceto, Wan Fokkink, Anna Ingolfsdottir and Bas Luttik  
  Dynamic Routing Schemes for General Graphs  A finite equational base for CCS with left merge and communication merge  
  Kei Uchizawa, Rodney Douglas and Wolfgang Maass Markus Lohrey and Géraud Sénizergues  
  Energy Complexity and Entropy of Threshold Circuits Theories of HNN-extensions and amalgamated products   
  Philip Bille Wong Karianto, Aloys Krieg and Wolfgang Thomas  
  New Algorithms for Regular Expression Matching On Intersection Problems for Polynomially Generated Sets   
13:00 - 14:30 Lunch
14:30 - 16:00 A.12  - Fixed Parameter Complexity and Approximation Algorithms B.6 - Logics  
  Dániel Marx Ittai Balaban, Amir Pnueli and Lenore Zuck.  
  A Parameterized View on Matroid Optimization Problems Invisible Safety of Distributed Protocols  
  G. Blelloch, K. Dhamdhere, E. Halperin, R. Ravi, R. Schwartz and S. Sridhar Piero A. Bonatti, Carsten Lutz, Aniello Murano and Moshe Y. Vardi  
  Fixed Parameter tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction  The Complexity of Enriched mu-Calculi  
  G. Baier, T. Erlebach, A. Hall, E. Koehler, H. Schilling and M. Skutella Michael Benedikt and Christoph Koch  
  Length-Bounded Cuts and Flows  Interpreting Tree-to-Tree Queries  
16:00 - 16:30 Coffee Break
16:30 - 18:00 A.13 B.7 - Automata II  
  Amin Coja-Oghlan Blaise Genest and Anca Muscholl  
  An adaptive spectral heuristic for partitioning random graphs  Constructing Exponential-size Deterministic Zielonka Automata  
  Jin-Yi Cai and Vinay Choudhary Marius Bozga Radu Iosif and Yassine Lakhnech  
  Some Results on Matchgates and Holographic Algorithms Flat Parametric Counter Automata  
  Julian Mestre Qiqi Yan  
  Weighted Popular Matchings  Lower Bounds for Complementation of omega-Automata via the Full Automata Technique  
18:00 - 18:10 Closing