Skip to main content
SpringerLink
Log in
Book cover

Complexity of Computer Computations

Proceedings of a symposium on the Complexity of Computer Computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department

  • Conference proceedings
  • © 1972

Overview

Editors:
  1. Raymond E. Miller
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. James W. Thatcher
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Jean D. Bohlinger

    1. Mathematical Sciences Department, IBM Thomas J. Watson Research Center, Yorktown Heights, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: The IBM Research Symposia Series (IRSS)

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

Licence this eBook for your library

Institutional subscriptions

Table of contents (15 papers)

  1. Front Matter

    Pages i-x
    Download chapter PDF

  2. Evaluation of Rational Functions

    • Volker Strassen
    Pages 1-10

  3. Solving Linear Equations by Means of Scalar Products

    • Michael O. Rabin
    Pages 11-20

  4. Simple Proofs of Lower Bounds for Polynomial Evaluation

    • Edward M. Reingold, A. Ian Stocks
    Pages 21-30

  5. On Obtaining Upper Bounds on the Complexity of Matrix Multiplication

    • Charles M. Fiduccia
    Pages 31-40

  6. Efficient Iterations for Algebraic Numbers

    • Michael S. Paterson
    Pages 41-52

  7. Parallel Iteration Methods

    • Shmuel Winograd
    Pages 53-60

  8. The Computational Complexity of Iterative Methods for Systems of Nonlinear Equations

    • Richard Brent
    Pages 61-71

  9. The Computational Complexity of Elliptic Partial Differential Equations

    • Martin H. Schultz
    Pages 73-83

  10. Reducibility among Combinatorial Problems

    • Richard M. Karp
    Pages 85-103

  11. Permuting Information in Idealized Two-Level Storage

    • Robert W. Floyd
    Pages 105-109

  12. An n log n Algorithm to Distribute n Records Optimally in a Sequential Access File

    • Vaughan R. Pratt
    Pages 111-118

  13. Toward a Lower Bound for Sorting Networks

    • David C. Van Voorhis
    Pages 119-129

  14. Isomorphism of Planar Graphs (Working Paper)

    • J. E. Hopcroft, R. E. Tarjan
    Pages 131-152

  15. Efficiency of Equivalence Algorithms

    • Michael J. Fischer
    Pages 153-167

  16. Panel Discussion

    • Raymond E. Miller, James W. Thatcher, Jean D. Bohlinger
    Pages 169-185

  17. Back Matter

    Pages 187-225
    Download chapter PDF
Back to top

Keywords

About this book

The Symposium on the Complexity of Computer Compu­ tations was held at the IBM Thomas J. Watson Research Center in Yorktown Heights, New York, March 20-22, 1972. These Proceedings contain all papers presented at the Symposium together with a transcript of the concluding panel discussion and a comprehensive bibliography of the field. The Symposium dealt with complexity studies closely re­ lated to how computations are actually performed on computers. Although this area of study has not yet found an appropriate or generally accepted name, the area is recognizable by the signif­ icant commonality in problems, approaches, and motivations. The area can be described and delineated by examples such as the following. (1) Determining lower bounds on the number of operations or steps required for computational solutions of specific problems such as matrix and polynomial calculations, sorting and other combinatorial problems, iterative com­ putations, solving equations, and computer resource allocation. (2) Developing improved algorithms for the solution of such problems which provide good upper bounds on the number of required operations, along with experimental and v vi PREFACE theoretical evidence concerning the efficiency and numer­ ical accuracy of those algorithms. (3) Studying the effects on the efficiency of computation brought about by variations in sequencing and the intro­ duction of parallelism.

Editors and Affiliations

  • Mathematical Sciences Department, IBM Thomas J. Watson Research Center, Yorktown Heights, USA

    Jean D. Bohlinger

Bibliographic Information

  • Book Title: Complexity of Computer Computations

  • Book Subtitle: Proceedings of a symposium on the Complexity of Computer Computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department

  • Editors: Raymond E. Miller, James W. Thatcher, Jean D. Bohlinger

  • Series Title: The IBM Research Symposia Series

  • DOI: https://doi.org/10.1007/978-1-4684-2001-2

  • Publisher: Springer New York, NY

  • eBook Packages: Springer Book Archive

  • Copyright Information: Plenum Press, New York 1972

  • Softcover ISBN: 978-1-4684-2003-6Published: 14 April 2012

  • eBook ISBN: 978-1-4684-2001-2Published: 13 March 2013

  • Edition Number: 1

  • Number of Pages: X, 225

  • Topics: Science, Humanities and Social Sciences, multidisciplinary

Publish with us

Policies and ethics

Back to top

Search

Navigation