Skip to main content
SpringerLink
Log in
Book cover

Automata, Languages and Programming

35th International Colloquium, ICALP 2008 Reykjavik, Iceland, July 7-11, 2008 Proceedings, Part I

  • Conference proceedings
  • © 2008

Overview

Editors:
  1. Luca Aceto

    1. School of Computer Science, Reykjavik University, Reykjavík, Iceland

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Ivan Damgård

    1. Department of Computer Science, IT-Parken, University of Aarhus, ÅrhusN, Denmark

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Leslie Ann Goldberg

    1. Department of Computer Science, University of Liverpool, Liverpool, UK

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Magnús M. Halldórsson

    1. School of Computer Science, Reykjavik University, Reykjavik, Iceland

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  5. Anna Ingólfsdóttir

    1. Department of Computer Science, Reykjavik University, Reykjavík, Iceland

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  6. Igor Walukiewicz

    1. Université de Bordeaux-1, LaBRI, Talence cedex, France

    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 5125)

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

Included in the following conference series:

Conference proceedings info: ICALP 2008.

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 149.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 199.00
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 (73 papers)

  1. Front Matter

    Download chapter PDF

  3. Track A: Algorithms, Automata, Complexity, and Games

    1. Complexity: Boolean Functions and Circuits

      1. The Complexity of Boolean Formula Minimization
        • David Buchfuhrer, Christopher Umans
        Pages 24-35
      2. Optimal Cryptographic Hardness of Learning Monotone Functions
        • Dana Dachman-Soled, Homin K. Lee, Tal Malkin, Rocco A. Servedio, Andrew Wan, Hoeteck Wee
        Pages 36-47
      3. On Berge Multiplication for Monotone Boolean Dualization
        • Endre Boros, Khaled Elbassioni, Kazuhisa Makino
        Pages 48-59
      4. Diagonal Circuit Identity Testing and Lower Bounds
        • Nitin Saxena
        Pages 60-71

    2. Data Structures

      1. Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity
        • Yitong Yin
        Pages 72-83
      2. Constructing Efficient Dictionaries in Close to Sorting Time
        • Milan Ružić
        Pages 84-95
      3. On List Update with Locality of Reference
        • Susanne Albers, Sonja Lauer
        Pages 96-107
      4. A New Combinatorial Approach for Sparse Graph Problems
        • Guy E. Blelloch, Virginia Vassilevska, Ryan Williams
        Pages 108-120

    3. Random Walks and Random Structures

      1. How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
        • Chen Avin, Michal Koucký, Zvi Lotker
        Pages 121-132
      2. Networks Become Navigable as Nodes Move and Forget
        • Augustin Chaintreau, Pierre Fraigniaud, Emmanuelle Lebhar
        Pages 133-144
      3. Fast Distributed Computation of Cuts Via Random Circulations
        • David Pritchard
        Pages 145-160
      4. Finding a Maximum Matching in a Sparse Random Graph in <i>O</i>(<i>n</i>) Expected Time
        • Prasad Chebolu, Alan Frieze, Páll Melsted
        Pages 161-172

    4. Design and Analysis of Algorithms

      1. Function Evaluation Via Linear Programming in the Priced Information Model
        • Ferdinando Cicalese, Eduardo Sany Laber
        Pages 173-185
      2. Improved Approximation Algorithms for Budgeted Allocations
        • Yossi Azar, Benjamin Birnbaum, Anna R. Karlin, Claire Mathieu, C. Thach Nguyen
        Pages 186-197
      3. The Travelling Salesman Problem in Bounded Degree Graphs
        • Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
        Pages 198-209
      4. Treewidth Computation and Extremal Combinatorics
        • Fedor V. Fomin, Yngve Villanger
        Pages 210-221
Back to top

Other volumes

  1. Automata, Languages and Programming

  2. Automata, Languages and Programming

Keywords

About this book

The two-volume set LNCS 5125 and LNCS 5126 constitutes the refereed proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP 2008, held in Reykjavik, Iceland, in July 2008. The 126 revised full papers presented together with 4 invited lectures were carefully reviewed and selected from a total of 407 submissions. The papers are grouped in three major tracks on algorithms, automata, complexity and games, on logic, semantics, and theory of programming, and on security and cryptography foundations. LNCS 5125 contains 70 contributions of track A selected from 269 submissions as well as 2 invited lectures. The papers are organized in topical sections on complexity: boolean functions and circuits, data structures, random walks and random structures, design and analysis of algorithms, scheduling, codes and coding, coloring, randomness in computation, online and dynamic algorithms, approximation algorithms, property testing, parameterized algorithms and complexity, graph algorithms, computational complexity, games and automata, group testing, streaming, and quantum, algorithmic game theory, and quantum computing.

Editors and Affiliations

  • School of Computer Science, Reykjavik University, Reykjavík, Iceland

    Luca Aceto

  • Department of Computer Science, IT-Parken, University of Aarhus, ÅrhusN, Denmark

    Ivan Damgård

  • Department of Computer Science, University of Liverpool, Liverpool, UK

    Leslie Ann Goldberg

  • School of Computer Science, Reykjavik University, Reykjavik, Iceland

    Magnús M. Halldórsson

  • Department of Computer Science, Reykjavik University, Reykjavík, Iceland

    Anna Ingólfsdóttir

  • Université de Bordeaux-1, LaBRI, Talence cedex, France

    Igor Walukiewicz

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation