clarke@csri.toronto.edu (Jim Clarke) (02/01/88)
(SF = Sandford Fleming Building, 10 King's College Road)
(GB = Galbraith Building, 35 St. George Street)
(WB = Wallberg Building, 184 College Street)
SUMMARY:
NUMERICAL ANALYSIS SEMINAR, Tues., February 9, 10 am, WB242 -- Daniel B. Szyld:
"A Parallel, Hybrid Algorithm for the Generalized Eigenvalue Problem
Ax = lambda Bx"
A.I. SEMINAR, Tuesday, February 9, 2 pm, SF1105 -- David Weir:
"Characterizing Mildly Context-Sensitive Grammatical Formalisms"
THEORY SEMINAR, Thursday, February 11, 3 pm, GB244 -- Steven Rudich:
"Lower Bounds on the Strength of Cryptographic Assumptions"
----------------------
NUMERICAL ANALYSIS SEMINAR, Tuesday, February 9, 10 am, WB242
Daniel B. Szyld
Duke University
"A Parallel, Hybrid Algorithm for the Generalized
Eigenvalue Problem Ax = lambda Bx"
We present a parallel algorithm for computing all eigenvalues, and their
corresponding eigenvectors, in a specified interval for the generalized
eigenproblem, Ax = lambda Bx, where A and B are banded, real, sym-
metric and B is positive definite. The method consists of two major
steps: Isolation and Extraction. Eigenvalues are isolated in parallel,
using the Sturm sequence property of leading principal minors of A - muB.
Concurrently, eigenvalues and eigenvectors are computed accurately
using a superlinear method which combines inverse and Rayleigh quotient
iterations and guarantees that the eigenvalue found lies in the desired
interval. Results obtained from implementation of this algorithm on a
shared memory MIMD architecture are presented.
A.I. SEMINAR, Tuesday, February 9, 2 pm, SF1105
Dr. David Weir
University of Pennsylvania
"Characterizing Mildly Context-Sensitive
Grammatical Formalisms"
Recent research suggests that Context-Free Grammars (CFG's) lack the neces-
sary expressive power on which to base a linguistic theory. This has led
computational linguists to consider grammatical formalisms whose generative
power exceeds CFG's, but to only a limited extent. We investigate the
mathematical and computational properties of several of these formalisms,
comparing them on the basis of their weak generative capacity, and aspects
of their strong generative capacity. In particular, we consider properties
of their structural descriptions (or tree sets); and the types of dependen-
cies (nested, crossed, etc.) that can be exhibited by each formalism.
Our work on structural descriptions leads us to characterize a class of
formalisms called Linear Context-Free Rewriting Systems (LCFRS's), which
includes a wide range of grammatical formalisms with restricted power. We
prove that all members of this family generate only semilinear languages
that can be recognized in polynomial time.
We show the weak equivalence of several LCFRS's that are notationally quite
different (Tree Adjoining Grammars, Head Grammars, and Linear Indexed Gram-
mars). These formalisms produce languages exhibiting nested and serial
dependencies, in addition to limited crossed-serial dependencies, which
occur in certain natural languages (e.g., Dutch). By formalizing the rela-
tionship between crossed-serial dependencies and the nested dependencies
produced by CFG's we define an infinite hierarchy of formalisms (belonging
to LCFRS's). These formalisms exhibit increasingly complex dependencies and
generate more complex structural descriptions, yet maintain the desirable
linguistic and computational properties of Context-Free Grammars.
THEORY SEMINAR, Thursday, February 11, 3 pm, GB244
Mr. Steven Rudich
University of California at Berkeley
"Lower Bounds on the Strength
of Cryptographic Assumptions"
A SECRET KEY EXCHANGE PROTOCOL is a protocol whereby Alice and Bob agree
(with high probability) on a secret, but where an eavesdropper, Eve,
overhearing their entire conversation, cannot compute this secret with any
polynomial probability. Such protocols are known to exist given the
existence of one-way functions with special properties, such as trapdoor or
Diffie-Hellman functions. We give strong evidence that such a protocol
cannot be proved secure based solely on the assumption that a pseudo-random
one-way function exists.
There are two approaches one might take to provide such evidence. An
information-theoretic approach would model a pseudo-random function by a
black-box for a purely random function; all parties involved would have
access to this black-box. A second approach would be to construct an ora-
cle relative to which a pseudo-random one-way function existed, but no pro-
tocol was secure. This would show that the assumption that a one-way func-
tion exists is not sufficient to prove the correctness of a protocol using
techniques which relativize.
Our approach combines both of the above. We first show that no protocol
can be information-theoretically secure, giving a general strategy for Eve
to break the scheme. We then show that, if P=NP, and if Alice and Bob are
polynomial-time machines, Eve's strategy can actually be implemented in
polynomial-time. THUS, FOR ANY SECRET KEY EXCHANGE PROTOCOL WHICH USES A
ONE-WAY FUNCTION AS A BLACK BOX, PROVING THE PROTOCOL IS SECURE IS AS HARD
AS PROVING P<>NP. As a corollary, we get an oracle as in the second
approach above: take any oracle relative to which P=NP, and add another
oracle at random.
This is joint work with Russell Impagliazzo.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
BITNET,CSNET: clarke@csri.toronto.edu CDNNET: clarke@csri.toronto.cdn
UUCP: {allegra,cornell,decvax,linus,utzoo}!utcsri!clarke