Skip to main content
SpringerLink
Log in
Book cover

Automata, Languages and Programming

37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I

  • Conference proceedings
  • © 2010

Overview

Editors:
  1. Samson Abramsky

    1. Oxford University Computing Laboratory, Oxford, UK

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Cyril Gavoille

    1. Université de Bordeaux (LaBRI) & INRIA, 351, cours de la Libération, Talence Cedex, France

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Claude Kirchner

    1. INRIA, Centre de Recherche Bordeaux – Sud-Ouest, 351 cours de la Libération, Talence Cedex, France

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Friedhelm Meyer auf der Heide

    1. Heinz Nixdorf Institute, University of Paderborn, Paderborn, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  5. Paul G. Spirakis

    1. University of Patras and RACTI, Patras, Greece

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

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

Included in the following conference series:

Conference proceedings info: ICALP 2010.

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 (62 papers)

  1. Front Matter

    Download chapter PDF

  2. Invited Talks

    1. Local Search: Simple, Successful, But Sometimes Sluggish

      • Burkhard Monien, Dominic Dumrauf, Tobias Tscheuschner
      Pages 1-17

    2. When Conflicting Constraints Can Be Resolved – The Lovász Local Lemma and Satisfiability

      • Emo Welzl
      Pages 18-18

  3. Session 1-Track A. Combinatorial Optimization

    1. Plane Spanners of Maximum Degree Six

      • Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Ljubomir Perković
      Pages 19-30

    2. The Positive Semidefinite Grothendieck Problem with Rank Constraint

      • Jop Briët, Fernando Mário de Oliveira Filho, Frank Vallentin
      Pages 31-42

    3. Cycle Detection and Correction

      • Amihood Amir, Estrella Eisenberg, Avivit Levy, Ely Porat, Natalie Shapira
      Pages 43-54

    4. Decomposition Width of Matroids

      • Daniel Král’
      Pages 55-66

  4. Session 2-Track A1. Game Theory

    1. The Cooperative Game Theory Foundations of Network Bargaining Games

      • MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Nicole Immorlica, Hamid Mahini
      Pages 67-78

    2. On the Existence of Pure Nash Equilibria in Weighted Congestion Games

      • Tobias Harks, Max Klimm
      Pages 79-89

    3. On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions

      • Allan Borodin, Brendan Lucier
      Pages 90-101

    4. Mean-Payoff Games and Propositional Proofs

      • Albert Atserias, Elitza Maneva
      Pages 102-113

  5. Session 2-Track A2. Security

    1. Online Network Design with Outliers

      • Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi, Piotr Sankowski
      Pages 114-126

    2. Efficient Completely Non-malleable Public Key Encryption

      • Benoît Libert, Moti Yung
      Pages 127-139

    3. Polynomial-Space Approximation of No-Signaling Provers

      • Tsuyoshi Ito
      Pages 140-151

    4. From Secrecy to Soundness: Efficient Verification via Secure Computation

      • Benny Applebaum, Yuval Ishai, Eyal Kushilevitz
      Pages 152-163

  6. Session 3-Track A1. Data Structures

    1. Mergeable Dictionaries

      • John Iacono, Özgür Özkan
      Pages 164-175

    2. Faster Algorithms for Semi-matching Problems (Extended Abstract)

      • Jittat Fakcharoenphol, Bundit Laekhanukit, Danupon Nanongkai
      Pages 176-187

    3. Clustering with Diversity

      • Jian Li, Ke Yi, Qin Zhang
      Pages 188-200

    4. New Data Structures for Subgraph Connectivity

      • Ran Duan
      Pages 201-212

  7. Session 3-Track A2. Sorting & Hashing

    1. Tight Thresholds for Cuckoo Hashing via XORSAT

      • Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, Michael Rink
      Pages 213-225
Back to top

Other volumes

  1. Automata, Languages and Programming

  2. Automata, Languages and Programming

Keywords

Editors and Affiliations

  • Oxford University Computing Laboratory, Oxford, UK

    Samson Abramsky

  • Université de Bordeaux (LaBRI) & INRIA, 351, cours de la Libération, Talence Cedex, France

    Cyril Gavoille

  • INRIA, Centre de Recherche Bordeaux – Sud-Ouest, 351 cours de la Libération, Talence Cedex, France

    Claude Kirchner

  • Heinz Nixdorf Institute, University of Paderborn, Paderborn, Germany

    Friedhelm Meyer auf der Heide

  • University of Patras and RACTI, Patras, Greece

    Paul G. Spirakis

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation