ACM-MIT Press Doctoral Dissertations Superior Research and
          Exceptional Writing
ORDER DIRECTLY FROM MIT PRESS

The Award Series

The Association for Computing Machinery and The MIT Press have established
an awards program to recognize and encourage superior research and
exceptional writing by doctoral candidates, judged by a distinguished
committee selected by ACM.  Winning dissertations will be published
annually by The MIT Press.

    For further details and information on the Award, write:  THE DOCTORAL
DISSERTATION AWARD, ACM, 11 W. 42nd Street, New York, NY 10036.

    To order these publications, please use The MIT Press Order Form provided 
on page of this catalog.

Full Abstraction and Semantic Equivalence by Ketan Mulmuley
is the winner of the 1986 Award.

Full Abstraction and Semantic Equivalence demonstrates an original theory that 
uses the same inclusive predicates to show semantic equivalence and to construct
fully abstract, extensional submodels.
    Contents: Introduction to Domain Theory. The Problem of Inclusive Predicate Existence. Fully Abstract Submodels of Typed Lambda Calculi. Fully Abstract
Submodels in the Presence of Reflexive Types. A Mechanizable Theory for
Existence Proofs. IPL Implementation. Conclusion.
    Ketan Mulmuley is a Miller Fellow in the Department of Electrical
 Engineering and Computer Science at the University of California, Berkeley, 224 pp.  $25.00  0-262-13227-3


Computational Limitations for Small Depth Circuits by Johan Torkel Hastad is 
the winner of the 1986 Award.

Proving lower bounds on the amount of resources needed to compute specific
functions is one of the most active branches of theoretical computer science.
Significant progress has been made recently in proving lower bounds in two
restricted models of Boolean circuits.  One is the model of small depth
circuits, and in this book John Torkel Hastad has developed very powerful
techniques for proving exponential lower bounds on the size of small dept
circuits' computing functions.
    Contents: Introduction. Small Depth Circuits. Outline of Lower Bound Proofs. Main Lemma. Lower Bounds for Small Depth Circuits. Functions Requiring Depth 
k to Have Small Circuits. Applications to Relativized Complexity: How Well
Can We Compute Parity in Small Depth? Is Majority Harder Than Parity?
Conclusions.

    Johan Hastad is a postdoctoral fellow in the Department of Mathematics
at MIT, 104 pp.  $20.00.  0-262-08167-9

Bulldog: A Compiler for VLIW Architectures by John R. Ellis is the winner of the 1985 Award.

Bulldog demonstrates that a symbiosis of new Very Long Instruction Word (VLIW)
architectures and new compiling technology is practicable.
VLIW architectures are reduced-in-struction-set machines with a large number of parallel, pipelined functional units but only a single thread of control.
    These machines offer the promise of an immediate order-of-magnitude
increase in speed for general purpose scientifice computing. However, a
traditional compiler can't find enough parallelism in scientific programs 
to utilize a VLIW effectively. The Bulldog compiler described here uses several new compilation techniques: trace scheduling to find more parallelism,
memory-reference and memory bank disambiguation to increase memory bandwidth,
and new code-generation algorithms.
    Although originally developed for VLIWs, many of the ideas in Bulldog could be applied to pipelined reduced-instruction-set architectures such as MIPS.
Ellis's experiments indicate that speed improvements of from thirty to eight
percent are possible for scientific code on such machines.

John R. Ellis received his doctorate from Yale University and is currently
Principal Software Engineer, Digital Equipment Corporation Systems Research 
Center, Palo Alto, CA, 320 pp. $32.50.  0-262-05034-X 

Reduced Instruction Set Computer Architectures for VLSI by Mangolis G.H. Katevenis is the winner of the 1984 Award.