clarke@csri.toronto.edu (Jim Clarke) (03/17/89)
(SF = Sandford Fleming Building, 10 King's College Road)
(GB = Galbraith Building, 35 St. George Street)
SUMMARY:
AI SEMINAR - Monday, April 3, 11 a.m. in Room SF 3201 -- Ernest Davis
"Reasoning about Perception and Knowledge"
SYSTEMS SEMINAR - Tuesday, April 4, 2 p.m. in Room GB 244 -- Paolo Atzeni
"Updating Databases in the Weak Instance Model"
THEORY SEMINAR - Thursday, April 6, 3 p.m. in Room GB 244 -- Peter Hajnal
"An omega (n^(4/3)) Lower Bound on the Randomized
Decision Tree Complexity of Graph Properties"
--------------------
AI SEMINAR - Monday, April 3, 11 a.m. in Room SF 3201
Ernest Davis
Courant Institute
"Reasoning about Perception and Knowledge"
To plan the use of a perceptual system, an intelligent creature
should be able to reason about what he will perceive, and what
knowledge he will gain from his perceptions. This talk presents
a formal model of knowledge acquisition through visual
perception. The model supports commonsense inferences about
perception and knowledge such as, "If Jim can see that Paul is
looking directly at a bus, then Jim knows that Paul knows that
there is a bus in front of him," or "If Fred is inside a closed
room and Joanne is outside, then Joanne cannot be sure what Fred
is doing." The chief technical innovation of the model is a
distinction between physically possible states of the world and
epistemically possible worlds. The theory also supports
reasoning about the limits of visual acuity.
SYSTEMS SEMINAR - Tuesday, April 4, 2 p.m. in Room GB 244
Paolo Atzeni
Universita degli Studi di Napoli
"Updating Databases in the Weak Instance Model"
Database updates have recently received much more attention than
in the past. In this trend, a solid foundation is provided to
the problem of updating databases through interfaces based on the
weak instance model. Insertions and deletions of tuples are
considered. As a preliminary tool, a lattice on states is
defined, based on the information content of the various states.
Potential results of an insertion are states that contain at
least the information in the original state and that in the new
tuple. sometimes there is no potential result, and in the other
cases there may be many of them. We argue that the insertion is
deterministic if the state that contains the information common
to all the potential results (the greatest lower bound, in the
lattice framework) is itself a potential result. Effective
characterizations for the various cases exist.
A symmetric approach is followed for deletions, with fewer cases,
since there are always potential results; determinism is
characterized consequently.
THEORY SEMINAR - Thursday, April 6, 3 p.m. in Room GB 244
Peter Hajnal
Department of Mathematics, M.I.T.
"An omega (n^(4/3)) Lower Bound on the Randomized
Decision Tree Complexity of Graph Properties"
We prove that for any nontrivial monotone graph property P, a
randomizing solver must expect to query at least cn^(4/3)
entries of the adjacency matrix of any graph G on n vertices
in order to obtain sufficient information to decide whether or
not G has property P, where c is an absolute constant.
(Without randomization, omega (n^2) queries are necessary
[R. Rivest S. Vuillemin, 1975].) The best previous lower bound
was cn^(5/4) [V. King, 1988]. Our proof follows Yao's
approach and improves it in a different direction from King's
lower bound. At the heart of the proof are a duality argument
combined with a new packing lemma for bipartite graphs.
--
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