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: <8803141628.AA02721@isabella.csri.toronto.edu>
Organization: University of Toronto, CSRI
Distribution: ut
Date: Mon, 14 Mar 88 11:28:40 EST


This week's speaker will be Philippe Derome, who will discuss the topic
``How to search fast a multikey table with no pointers.''
The meeting will be held in Wallberg 144 from 11:00-12:00 
on Thursday, March 17.

This talk is a presentation of a paper to be published in STOC 88 by
Fiat, Naor, Sch\"{a}ffer, Schmidt, and Siegel. The data structure is an array
of n records with k keys. The queries specify the value of one key,
and the algorithm returns the record, if found, in O(log n), where the
constant is cklog k and c is independent of k and n. If m records
satisfy the query, the algorithm finds them in O(tlog n).

Please note that we still need a volunteer for food this Thursday, plus
volunteers for both speakers and feeders in some subsequent weeks.  Let me
know when you are willing to volunteer . . .