## Topics in computational complexity and the analysis of algorithms

62. R. P. Brent,
* Topics in computational complexity
and the analysis of algorithms*,
Report TR-CS-80-14, Department of Computer Science,
ANU, October 1980, 375 pp.
## Abstract

[From the Introduction]
The theme of this collection of papers is the derivation of rigorous
bound on the cost of certain computations. Cost may be measured in
several different ways. For example, in
[37,
39,
45,
50]
we identify cost with the number of arithmetic operations performed on
integers or real numbers, in
[32,
34]
we consider the number of Boolean operations, and in
[12,
14,
16]
we count function and derivative evaluations. In
[3,
15,
18,
22]
it is more appropriate to consider the time required to evaluate
an expression on a parallel machine, and in
[55,
60]
we introduce an area-time product which is motivated by practical
cost measures for VLSI circuits.

Most of the papers are concerned with upper bounds,
which are established by exhibiting an algorithm and analysing its
performance. In
[16,
55]
nontrivial lower bounds are established. Proofs of lower bounds
are generally more difficult than those for upper bounds, since it is
necessary to consider all possible algorithms for the problem at hand,
rather than just one carefully selected algorithm. The aim when
establishing upper and lower bounds is, of course, to bring them as
close together as possible, but this is difficult unless the "trivial"
lower bound is almost attainable, as in
[3].

The collection is divided into the following sections.

- Introduction and bibliography.
- Parallel evaluation of arithmetic expressions
[15,
22,
18].
- Circuits for arithmetic operations
[3,
60,
55].
- Continuous models for discrete algorithms
[37,
13].
- Algorithms for manipulating formal power series
[45,
39,
50].
- The complexity of algorithms for solving nonlinear equations
[16,
27,
12,
14].
- Asymptotically fast algorithms for high-precision computations
[28,
32,
34].

## Comments

This is a selection of papers submitted for the degree of Doctor of Science
at Monash University (degree awarded 1981).
The papers included are
[3,
12,
13,
14,
15,
16,
18,
22,
27,
28,
32,
34,
37,
39,
45,
50,
55,
60].

## Acknowledgement

Thanks to David Kuck, H. T. Kung,
Kiyoshi Maruyama, Joe Traub, Shmuel Winograd and Phil Wolfe
for permission to include some of our joint papers in this collection.
Specifically, these joint papers are:
- Brent, Kuck and Maruyama [15],
- Brent and Kung
[39,
45,
55,
60],
- Brent and Traub [50],
- Brent, Winograd and Wolfe [16].

## Excerpts

These are gif page images, mainly 768×1056 pixels:
rubber stamp;

title page;

copyright notice;

acknowledgements;

contents;

introduction:
9,
10,
11,
12,
13,
14;

bibliography:
15,
17,
18,
19,
20,
21,
22,
23,
24,
25,
26.

other sections: see the papers mentioned in the abstract above.

All the above gif files are available in a single
pdf file (1346K).

Go to next publication

Return to Richard Brent's index page