Skip to main content
SpringerLink
Log in
Book cover
  • Conference proceedings
  • © 2006

Automata, Languages and Programming

33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I

Editors:

  1. Michele Bugliesi

    1. Dipartimento di Informatica, Università Ca’ Foscari, Venice

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Bart Preneel

    1. Interdisciplinary Institute for BroadBand Technology (IBBT), Belgium

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Vladimiro Sassone

    1. ECS, University of Southampton, UK

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Ingo Wegener

    1. FB Informatik, Univ. Dortmund, Dortmund, Germany

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

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

Conference series link(s): ICALP: International Colloquium on Automata, Languages, and Programming

Conference proceedings info: ICALP 2006.

Sections

Buy it now

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

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

Table of contents (62 papers)

  1. Front Matter

    PDF

  2. Invited Lectures

    1. Additive Approximation for Edge-Deletion Problems (Abstract)

      • Noga Alon, Asaf Shapira, Benny Sudakov
      Pages 1-2

  3. Graph Theory I

    1. Testing Graph Isomorphism in Parallel by Playing a Game

      • Martin Grohe, Oleg Verbitsky
      Pages 3-14

    2. The Spectral Gap of Random Graphs with Given Expected Degrees

      • Amin Coja-Oghlan, André Lanka
      Pages 15-26

    3. Embedding Bounded Bandwidth Graphs into ℓ1

      • Douglas E. Carroll, Ashish Goel, Adam Meyerson
      Pages 27-37

    4. On Counting Homomorphisms to Directed Acyclic Graphs

      • Martin Dyer, Leslie Ann Goldberg, Mike Paterson
      Pages 38-49

  4. Quantum Computing

    3. Self-testing of Quantum Circuits

      • Frédéric Magniez, Dominic Mayers, Michele Mosca, Harold Ollivier
      Pages 72-83

    4. Deterministic Extractors for Independent-Symbol Sources

      • Chia-Jung Lee, Chi-Jen Lu, Shi-Chun Tsai
      Pages 84-95

  5. Randomness

    1. Gap Amplification in PCPs Using Lazy Random Walks

      • Jaikumar Radhakrishnan
      Pages 96-107

    2. Stopping Times, Metrics and Approximate Counting

      • Magnus Bordewich, Martin Dyer, Marek Karpinski
      Pages 108-119

  6. Formal Languages

    2. P-completeness of Cellular Automaton Rule 110

      • Turlough Neary, Damien Woods
      Pages 132-143

    3. Small Sweeping 2NFAs Are Not Closed Under Complement

      • Christos A. Kapoutsis
      Pages 144-156

    4. Expressive Power of Pebble Automata

      • Mikołaj Bojańczyk, Mathias Samuelides, Thomas Schwentick, Luc Segoufin
      Pages 157-168

  7. Approximation Algorithms I

    3. A Push-Relabel Algorithm for Approximating Degree Bounded MSTs

      • Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, Kunal Talwar
      Pages 191-201

    4. Edge Disjoint Paths in Moderately Connected Graphs

      • Satish Rao, Shuheng Zhou
      Pages 202-213
Back to top

Other Volumes

  1. Automata, Languages and Programming

  2. Automata, Languages and Programming

Back to top

Keywords

Back to top

Editors and Affiliations

  • Dipartimento di Informatica, Università Ca’ Foscari, Venice

    Michele Bugliesi

  • Interdisciplinary Institute for BroadBand Technology (IBBT), Belgium

    Bart Preneel

  • ECS, University of Southampton, UK

    Vladimiro Sassone

  • FB Informatik, Univ. Dortmund, Dortmund, Germany

    Ingo Wegener

Back to top

Bibliographic Information

Back to top

Publish with us

Policies and ethics

Back to top
Access via your institution

Buy it now

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

Search

Navigation