Skip to main content
SpringerLink
Log in
Book cover

Automata, Languages and Programming

32nd International Colloquim, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings

  • Conference proceedings
  • © 2005

Overview

Editors:
  1. Luís Caires

    1. CITI / Departamento de Informática, Universidade Nova de Lisboa, Portugal

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Giuseppe F. Italiano

    1. Dipartimento di Informatica, Sistemi e Produzione, Università di Roma “Tor Vergata”, Roma, Italy

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Luís Monteiro

    1. Departamento de Informatica, Universidade Nova de Lisboa, Caparica, Portugal

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Catuscia Palamidessi

    1. Ecole Polytechnique, Palaiseau Cedex, France

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  5. Moti Yung

    1. Computer Science Department, Google Inc. and Columbia University, New York, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 3580)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: ICALP 2005.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (118 papers)

  1. Front Matter

    Download chapter PDF

  2. Invited Lectures

    1. Holographic Circuits

      • Leslie G. Valiant
      Pages 1-15

    2. Probabilistic Polynomial-Time Semantics for a Protocol Security Logic

      • Anupam Datta, Ante Derek, John C. Mitchell, Vitaly Shmatikov, Mathieu Turuani
      Pages 16-29

    3. A Gentle Introduction to Semantic Subtyping

      • Giuseppe Castagna, Alain Frisch
      Pages 30-34

    4. Logics for Unranked Trees: An Overview

      • Leonid Libkin
      Pages 35-50

    5. Nash Equilibria, the Price of Anarchy and the Fully Mixed Nash Equilibrium Conjecture

      • Martin Gairing, Thomas Lücking, Burkhard Monien, Karsten Tiemann
      Pages 51-65

  3. Data Structures I

    1. The Tree Inclusion Problem: In Optimal Space and Faster

      • Philip Bille, Inge Li Gørtz
      Pages 66-77

    2. Union-Find with Constant Time Deletions

      • Stephen Alstrup, Inge Li Gørtz, Theis Rauhe, Mikkel Thorup, Uri Zwick
      Pages 78-89

    3. Optimal In-place Sorting of Vectors and Records

      • Gianni Franceschini, Roberto Grossi
      Pages 90-102

    4. Towards Optimal Multiple Selection

      • Kanela Kaligosi, Kurt Mehlhorn, J. Ian Munro, Peter Sanders
      Pages 103-114

  4. Cryptography and Complexity

    1. Simple Extractors via Constructions of Cryptographic Pseudo-random Generators

      • Marius Zimand
      Pages 115-127

    2. Bounds on the Efficiency of “Black-Box” Commitment Schemes

      • Omer Horvitz, Jonathan Katz
      Pages 128-139

    3. On Round-Efficient Argument Systems

      • Hoeteck Wee
      Pages 140-152

    4. Computational Bounds on Hierarchical Data Processing with Applications to Information Security

      • Roberto Tamassia, Nikos Triandopoulos
      Pages 153-165

  5. Data Structures II

    1. Balanced Allocation and Dictionaries with Tightly Packed Constant Size Bins

      • Martin Dietzfelbinger, Christoph Weidling
      Pages 166-178

    2. Worst Case Optimal Union-Intersection Expression Evaluation

      • Ehsan Chiniforooshan, Arash Farzan, Mehdi Mirzazadeh
      Pages 179-190

    3. Measure and Conquer: Domination – A Case Study

      • Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch
      Pages 191-203

  6. Cryptography and Distributed Systems

    1. Optimistic Asynchronous Atomic Broadcast

      • Klaus Kursawe, Victor Shoup
      Pages 204-215

    2. Asynchronous Perfectly Secure Communication over One-Time Pads

      • Giovanni Di Crescenzo, Aggelos Kiayias
      Pages 216-227

    3. Single-Prover Concurrent Zero Knowledge in Almost Constant Rounds

      • Giuseppe Persiano, Ivan Visconti
      Pages 228-240
Back to top

Other volumes

  1. Automata, Languages and Programming

Keywords

About this book

The 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005) was held in Lisbon, Portugal from July 11 to July 15, 2005. These proceedings contain all contributed papers presented at ICALP 2005, - getherwiththepapersbytheinvitedspeakersGiuseppeCastagna(ENS),Leonid Libkin (Toronto), John C. Mitchell (Stanford), Burkhard Monien (Paderborn), and Leslie Valiant (Harvard). The program had an additional invited lecture by Adi Shamir (Weizmann Institute) which does not appear in these proceedings. ICALP is a series of annual conferences of the European Association for Theoretical Computer Science (EATCS). The ?rst ICALP took place in 1972. This year, the ICALP program consisted of the established track A (focusing on algorithms, automata, complexity and games) and track B (focusing on logic, semantics and theory of programming), and innovated on the structure of its traditional scienti?c program with the inauguration of a new track C (focusing on security and cryptography foundation). In response to a call for papers, the Program Committee received 407 s- missions, 258 for track A, 75 for track B and 74 for track C. This is the highest number of submitted papers in the history of the ICALP conferences. The P- gram Committees selected 113 papers for inclusion in the scienti?c program. In particular, the Program Committee for track A selected 65 papers, the P- gram Committee for track B selected 24 papers, and the Program Committee for track C selected 24 papers. All the work of the Program Committees was done electronically.

Editors and Affiliations

  • CITI / Departamento de Informática, Universidade Nova de Lisboa, Portugal

    Luís Caires

  • Dipartimento di Informatica, Sistemi e Produzione, Università di Roma “Tor Vergata”, Roma, Italy

    Giuseppe F. Italiano

  • Departamento de Informatica, Universidade Nova de Lisboa, Caparica, Portugal

    Luís Monteiro

  • Ecole Polytechnique, Palaiseau Cedex, France

    Catuscia Palamidessi

  • Computer Science Department, Google Inc. and Columbia University, New York, USA

    Moti Yung

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation