Meeting Agenda

Wednesday, July 2^nd, 1997

Location:

DC 1304

Time:

13:30

Chair:

Wilkin Chau

1. Adoption of the Agenda - additions or deletions

2. Coffee Hour

Coffee hour this week:

???

Coffee hour next week:

???

3. Next meeting

Date:

July 9^th, 1997

Location:

DC 1304

Time:

13:30

Chair:

Blair Conrad

Technical presentation:

Wilkin Chau

4. Forthcoming

Chairs:

1. Bill Cowan (7/16)
2. Itai Danan (7/23)
3. Matthew Davidchuk(7/30)

Tech Presenters:

1. Blair Conrad (7/16)
2. Bill Cowan (7/23)
3. Itai Danan (7/30)

5. Technical Presentation

Presenter:

Richard Bartels

Title:

A Report on "Metropolis Light Transport" by Eric Veach and Leonidas Guibas

Abstract:

The report will give a brief overview of a new Monte Carlo method for solving the light transport problem inspired by the Metropolis sampling method in computational physics.
This is taken from a paper that will appear in the SIGGRAPH '97 proceedings.

6. General Discussion Items

7. Action List

• Japanese Visitors
• Alias Visit Visit

8. Director's Meeting

9. Seminars

• CSGSA Celebrity Lecture Series
  Computational Genetics, Physiology, Metabolism,
  Neural Systems, Learning, Vision, and Behavior
  or
  PolyWorld: Life in a New Context
  
  Larry Yaeger
  Wednesday, July 2nd at 2:30 in DC1302
  
  ABSTRACT
  I will discuss a computer model of living organisms and the ecology they exist in, called PolyWorld. PolyWorld attempts to bring all the principle components of real living systems into a single artificial (man-made) living system. PolyWorld brings together biologically motivated genetics, simple simulated physiologies and metabolisms, Hebbian learning in arbitrary neural network architectures, a visual perceptive mechanism, and a suite of primitive behaviors in artificial organisms grounded in an ecology just complex enough to foster speciation and inter-species competition. Predation, mimicry, sexual reproduction, and even communication are all supported in a straightforward fashion. The resulting survival strategies, both individual and group, are purely emergent, as are the functionalities embodied in their neural network "brains". Complex behaviors resulting from the simulated neural activity are unpredictable, and change as natural selection acts over multiple generations.

  In many ways, PolyWorld may be thought of as a sort of electronic primordial soup experiment, in the vein of Urey and Miller's classic experiment, only commencing at a much higher level of organization. I also see PolyWorld as a means to begin exploring Artificial Life as a path toward Artificial Intelligence, utilizing the same key elements that led to natural intelligence: the evolution of nervous systems in an ecology.

  I will discuss the design principles employed in PolyWorld, the "species" that have evolved in various simulations, and the group and individual behaviors observed in these simulations. I will also at least briefly address the difficult issues around deciding when "Life" is actually present in a system.




• COMPUTER SCIENCE COLLOQUIUM SERIES
  Combining Neural Networks and Context-Driven Search for On-Line, Printed Handwriting Recognition in the Newton
  
  Larry Yaeger
  Thursday, July 3rd at 2:30 in DC1302
  
  ABSTRACT
  While on-line handwriting recognition is an area of long-standing and ongoing research, the recent emergence of portable, pen-based computers has focused urgent attention on usable, practical solutions. I will discuss a combination and improvement of classical methods to produce robust recognition of hand-printed English text, for a recognizer shipping in new models of Apple Computer's Newton MessagePad and eMate. Combining an artificial neural network (ANN), as a character classifier, with a context-driven search over segmentation and word recognition hypotheses provides an effective recognition system. Long-standing issues relative to training, generalization, segmentation, models of context, probabilistic formalisms, etc., need to be resolved, however, to obtain excellent performance. I will present a number of recent innovations in the application of ANNs as character classifiers for word recognition, including integrated multiple representations, normalized output error, negative training, stroke warping, frequency balancing, error emphasis, and quantized weights. User-adaptation and extension to cursive recognition pose continuing challenges.



• Pure and Applied Math and C+O Club Seminar
  Matching in Graphs and Linear Algebra
  
  Bill Cunningham
  Combinatorics and Optimization Department
  Friday, July 4, 1997, 11:30 a.m. MC4041
  
  ABSTRACT
  A perfect matching in a graph is a set of disjoint edges joining the vertices in pairs. This is one of the most basic notions in graph theory.

  The talk will emphasize the surprising connections between matching and linear algebra (including linear programming). Linear algebra can be used both to characterize the graphs that have perfect matchings, and to construct algorithms for finding them.




• CS Theory Seminar
  The Equivalence of Pebbles and Sensing Heads for Finite Automata and Related Simulations
  
  Holger Petersen
  Institut fuer Informatik, Universitaet Stuttgart
  Wed, July 9, 1997, 3:30-4:30 p.m. DC1304
  
  ABSTRACT
  It is well-known that logarithmic space bounded complexity classes can be characterized by string- processing devices that access a finite number of positions of their input in a read-only fashion. Several variants have been defined. Sometimes the pointer values can be compared, other models are equipped with a single pointer, but can temporarily mark a bounded number of symbols.

  In this talk I will show that the latter two models are equivalent. More precisely, automata with k pointers that can be compared are equivalent with respect to language recognition to automata that mark at most k positions. I will also describe other related simulation techniques.

  Some of these results will be presented at the conference ``Fundamentals of Computation Theory'' in Krakow later this year.

10. Lab Cleanup (until 14:30 or 5 minutes)