clarke@utcsri.UUCP (Jim Clarke) (03/09/87)
(SF = Sandford Fleming Building, 10 King's College Road)
(GB = Galbraith Building, 35 St. George Street)
SUMMARY:
Tuesday, March 17, 11 am, SF1101 -- Brian Kernighan
``Little Languages"
Tuesday, March 17, 2 pm, GB221 -- Glen Entis
``3D Computer Animation for Broadcast Television"
Tuesday, March 17, 3 pm, GB120 -- Alex Borgida
``Class Hierarchies with Contradictions: Semantics and Type Theory"
Thursday, March 19, 2 pm, GB248 -- Umeshwar Dayal
(Title to be announced)
Thursday, March 19, 3 pm, GB220 -- Josh Cohen Benaloh
``Verifiable Secret-Ballot Elections"
Friday, March 20, 2 pm, GB221 -- Andrew Goldberg
``Solving Minimum-Cost Flow Problems by Successive Approximation"
--------------------
COLLOQUIUM, Tuesday, March 17, 11 am, SF1101
Dr. Brian Kernighan
AT&T Bell Laboratories
``Little Languages"
A ``little language" is a specialized notation for a limited task, and
a processor to implement it. A little language is often a highly effective
way to define the user interface of a program and to organize and implement
it.
In this talk, we will examine a variety of little languages, focusing
on when to use them, how to design them, and how to build them.
GRAPHICS SEMINAR, Tuesday, March 17, 2 pm, GB221
Mr. Glen Entis
Pacific Data Images
``3D Computer Animation for Broadcast Television"
A lecture illustrated with videotape will present an overview of how
3D computer animation is used to produce graphics for broadcast television.
Special emphasis will be placed on how design and aesthetic criteria affect
the technical process.
A.I./SYSTEMS SEMINAR, Tuesday, March 17, 3 pm, GB120
Professor Alex Borgida
Rutgers University
``Class Hierarchies with Contradictions:
Semantics and Type Theory"
SYSTEMS SEMINAR, Thursday, March 19, 2 pm, GB248
Dr. Umeshwar Dayal
Computer Corporation of America
Title: TO BE ANNOUNCED
THEORY SEMINAR, Thursday, March 19, 3 pm, GB220
Professor Josh Cohen Benaloh
Yale University
``Verifiable Secret-Ballot Elections"
Privacy in secret-ballot elections has traditionally been attained by
using a ballot box or voting booth to disassociate voters from ballots.
Although such a system might achieve privacy, there is often little confi-
dence in the accuracy of the announced tally. This talk describes a prac-
tical scheme for conducting secret-ballot elections in which the outcome of
election is verifiable by all participants and even by non-participating
observers. All communications are public, yet the privacy of votes remains
intact.
The tools developed here to conduct such elections have additional
independent applications. Cryptographic capsules allow a prover to con-
vince verifiers that either statement A or statement B is true without
revealing substantial information as to which. Secret sharing homomor-
phisms enable computation on shared (secret) data and give a method of dis-
tributing shares of a secret such that each shareholder can verify the vali-
dity of all shares.
THEORY SEMINAR, Friday, March 20, 2 pm, GB221
Professor Andrew Goldberg
M.I.T.
``Solving Minimum-Cost Flow Problems
by Successive Approximation"
We introduce a framework for solving minimum-cost flow problems. Our
approach is to measure the quality of a solution by the amount that the
complementary slackness conditions are violated. We show how to extend
techniques developed for the maximum flow problem to improve the quality of
a solution. This framework allows us to achieve O(min(n**3, n**5/3 *
m**2/3, n*m*log(n))*log(nC)) running time. (Here n is the number of nodes
in the input network, m is the number of edges, and C is the absolute value
of the biggest cost.) This significantly improves the previous bounds. We
believe that our results are interesting from both theoretical and practi-
cal viewpoints.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
{allegra,cornell,decvax,linus,utzoo}!utcsri!clarke