clarke@utcsri.UUCP (Jim Clarke) (05/16/85)
ACTIVITIES FOR THE WEEK COMMENCING MAY 27, 1985
(SF = Sandford Fleming Building, 10 King's College Road)
COLLOQUIUM - Tuesday, May 28, 11:00 a.m., SF 1101
Ben Moskowski
Cambridge University
"Application of Interval Temporal Logic"
What do sequential computer programs, digital circuits and distri-
buted networks have in common? One answer is time. With this in mind
we present Interval Temporal Logic (ITL), a formalism that augments
standard predicate logic with operators for reasoning about intervals of
time. Within ITL we have specified and compared digital circuits rang-
ing from delay elements up to the AM2901 ALU bit slice developed by
Advanced Micro Devices, Inc. Furthermore, due to its expressiveness and
generality, ITL can directly capture various control structures found in
sequential and parallel computations. It has been used therefore to
reason about computer programs and simple message-passing systems.
We describe ITL and then show how it can express various functional
and timing-dependent aspects of hardware and software in a unified
manner. We also discuss Tempura, a programming language based on ITL.
THEORETICAL ASPECTS SEMINAR - Tuesday, May 28, 3 p.m., SF 1101
Ramamohan Paturi
Pennsylvania State University
"Probabilistic Communication Complexity"
We study unbounded error probabilistic communication complexity. Our
results include:
- one way and two way complexities by at most 1
- certain functions like equality and the verification of Hamming
distance have upper bounds that are considerably better than their
counterparts in deterministic, nondeterministic, and bounded error
probabilistic models
- there exists a function which requires O(log n) information
transfer
As an application, we prove that a certain language requires
O(log n) time to be recognized by a 1-tape (unbounded error) probabilis-
tic Turing machine. This bound is optimal. (Previous lower bound
results by Yao [15] require acceptance by bounded error computation. We
believe that this is the first nontrivial lower bound on the time
required by unbounded error probabilistic Turing machines.) We indicate
how to apply the lower bounds on the time of Turing machines to lower
bounds on the communication complexity of linear array of processors in
deterministic, nondeterministic, and unbounded error probabilistic
models.
Keywords: communication complexity, probabilistic communication
complexity, arrangements of hyperplanes, probabilistic 1-tape Turing
machines, distributed computing, lower bounds, arrays of processors.