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

Automata, Languages, and Programming

39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I

Editors:

  1. Artur Czumaj

    1. Department of Computer Science and Centre for Discrete Mathematics and its Applications, University of Warwick, Warwick, UK

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Kurt Mehlhorn

    1. Max-Planck-Institut für Informatik, Saarbrücken, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Andrew Pitts

    1. Computer Laboratory, University of Cambridge, UK

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Roger Wattenhofer

    1. ETH Zurich, Switzerland

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • Up-to-date results
  • Fast-track conference proceedings
  • State-of-the-art research

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

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 2012.

Sections

Buy it now

eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.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 (71 papers)

  1. Front Matter

    PDF

  2. Track A – Algorithms, Complexity and Games

    1. Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method

      • Dimitris Achlioptas, Ricardo Menchaca-Mendez
      Pages 1-12

    2. The NOF Multiparty Communication Complexity of Composed Functions

      • Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen
      Pages 13-24

    3. Quantum Strategies Are Better Than Classical in Almost Any XOR Game

      • Andris Ambainis, Artūrs Bačkurs, Kaspars Balodis, Dmitrijs Kravčenko, Raitis Ozols, Juris Smotrovs et al.
      Pages 25-37

    5. Polynomial-Time Isomorphism Test for Groups with No Abelian Normal Subgroups

      • László Babai, Paolo Codenotti, Youming Qiao
      Pages 51-62

    6. Clustering under Perturbation Resilience

      • Maria Florina Balcan, Yingyu Liang
      Pages 63-74

    7. Secretary Problems with Convex Costs

      • Siddharth Barman, Seeun Umboh, Shuchi Chawla, David Malec
      Pages 75-87

    8. Nearly Simultaneously Resettable Black-Box Zero Knowledge

      • Joshua Baron, Rafail Ostrovsky, Ivan Visconti
      Pages 88-99

    10. On Quadratic Programming with a Ratio Objective

      • Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran, Aravindan Vijayaraghavan
      Pages 109-120

    11. De-amortizing Binary Search Trees

      • Prosenjit Bose, Sébastien Collette, Rolf Fagerberg, Stefan Langerman
      Pages 121-132

    12. Efficient Sampling Methods for Discrete Distributions

      • Karl Bringmann, Konstantinos Panagiotou
      Pages 133-144

    13. Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints

      • Niv Buchbinder, Joseph (Seffi) Naor, R. Ravi, Mohit Singh
      Pages 145-156

    15. Testing Coverage Functions

      • Deeparnab Chakrabarty, Zhiyi Huang
      Pages 170-181

    17. A Dependent LP-Rounding Approach for the k-Median Problem

      • Moses Charikar, Shi Li
      Pages 194-205

    18. Node-Weighted Network Design in Planar and Minor-Closed Families of Graphs

      • Chandra Chekuri, Alina Ene, Ali Vakilian
      Pages 206-217
Back to top

Other Volumes

  1. Automata, Languages, and Programming

  2. Automata, Languages, and Programming

Back to top

About this book

This two-volume set of LNCS 7391 and LNCS 7392 constitutes the refereed proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP 2012, held in Warwick, UK, in July 2012. The total of 123 revised full papers presented in this volume were carefully reviewed and selected from 432 submissions. They are organized in three tracks focussing on algorithms, complexity and games; logic, semantics, automata and theory of programming; and foundations of networked computation.
Back to top

Keywords

Back to top

Editors and Affiliations

  • Department of Computer Science and Centre for Discrete Mathematics and its Applications, University of Warwick, Warwick, UK

    Artur Czumaj

  • Max-Planck-Institut für Informatik, Saarbrücken, Germany

    Kurt Mehlhorn

  • Computer Laboratory, University of Cambridge, UK

    Andrew Pitts

  • ETH Zurich, Switzerland

    Roger Wattenhofer

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