clarke@csri.toronto.edu (Jim Clarke) (02/27/89)
--------------------------------------------------
* CHANGE OF LOCATION & TIME OF SEMINAR *
Please note that the Theory Seminar on Friday, March 3 to be
given by Victor Shoup will take place in Room RS211, Roseburgh
Building at 11 a.m. instead of 10 a.m. in SF 4102.
--------------------------------------------------
(GB = Galbraith Building, 35 St. George Street)
SUMMARY:
GRAPHICS SEMINAR - Tuesday, March 14, 3:00 p.m. in Room GB 120 -- Don Mitchell
"Reconstruction Filters in Computer Graphics"
THEORY SEMINAR - Thursday, March 16, 3 p.m. in Room GB 244 -- Lance Fortnow
"Probabilistic Computation and Linear Time"
---------------------
GRAPHICS SEMINAR - Tuesday, March 14, 3:00 p.m. in Room GB 120
Don Mitchell
ATT Bell Labs, Murray Hill
"Reconstruction Filters in Computer Graphics"
Problems of signal processing arise in image synthesis because of
transformations between continuous and discrete representations
of 2D images. We will discuss mainly the problem of reconstruct-
ing samples into a continuous representation. The general problem
of designing a filter will be discussed, and a family of piece-
wise cubic filters will be used as examples. Two particular cu-
bic filters will be shown to have good behaviour for antialiasing
or image quality. It will also be shown that using derivatives of
the amplitude can greatly reduce aliasing.
THEORY SEMINAR - Thursday, March 16, 3 p.m. in Room GB 244
Lance Fortnow
MIT
"Probabilistic Computation and Linear Time"
In 1965 in the seminal paper in complexity theory, Hartmanis and
Stearns showed that there are languages that can be recognized in
quadratic deterministic time but can not be recognized in linear
deterministic time. Eight years later Cook obtained similar
results for non-deterministic time. We look at the same question
for probabilistic computation with some surprisingly different
results.
We show, relativized to an oracle, that probabilistic polynomial
time (BPP) is contained in probabilistic linear time. Thus any
proof of a separation of probabilistic linear time and BPP would
likely require new techniques. Since the result of Hartmanis and
Stearns and the result of Cook relativize to all oracles, our
result shows a rare collapse of a complexity time hierarchy not
apparent in deterministic and non-deterministic computation.
We also show several other results relating probabilistic and
linear time computation.
This research is joint work with Mike Sipser.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
clarke@csri.toronto.edu or clarke@csri.utoronto.ca
or ...!{uunet, pyramid, watmath, ubc-cs}!utai!utcsri!clarke