Newsgroups: ut.theory
Path: utzoo!utgpu!jarvis.csri.toronto.edu!csri.toronto.edu!nishi
From: nishi@csri.toronto.edu (Naomi Nishimura)
Subject: student seminar
Message-ID: <8803071951.AA09442@stclair.csri.toronto.edu>
Organization: University of Toronto, CSRI
Distribution: ut
Date: Mon, 7 Mar 88 14:51:15 EST

This week's speaker will be Richard Cleve.  He will be speaking on
"A Model of Reversible Computation and its Applications." The meeting will 
be held in Wallberg 144 from 11:00-12:00 on Thursday, March 10.  
The following is Richard's description of his talk.

This will be a practice of my interview talk.  I'm hoping to get constructive
criticism from the people who are present at Thursday's seminar.

We introduce a model of computation which is reversible in a strong sense.
Using the setting of this model, we prove that any log-depth algebraic
formula can be evaluated by a straight-line program which uses a constant
number of registers.  This can be viewed as an extension of a result of
Barrington about Boolean formulas to general algebraic formulas.

We also observe that programs in our reversible model of computation
correspond to a special class of block ciphers (which includes the Data 
Encryption Standard).  We prove that if it is possible to generate pseudo-
random functions that are in a complexity class called "DET" (slightly
stronger than nondeterministic-log-space) then it is possible to generate
polynomial-length block ciphers in this special class which are secure.

Finally, we relate our reversible model of computation to that of Bennett,
who considers reversibility as a way of reducing the thermodynamic cost 
of computation.