Automata, Languages and Programming

1. Front Matter

   PDF

2. Invited Lectures

   1. Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects

      • Bruno Courcelle

      Pages 1-13

   2. Internet Ad Auctions: Insights and Directions

      • S. Muthukrishnan

      Pages 14-23

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

   5. Scheduling

      1. Fast Scheduling of Weighted Unit Jobs with Release Times and Deadlines

         • C. Greg Plaxton

         Pages 222-233

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.

• algorithmic game theory
• algorithms
• complexity
• data structures
• design
• logic
• programming
• scheduling
• testing

• 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

Policies and ethics