CGL Meeting Agenda

Wednesday, January 14, 1998

Location:
DC1304
Time:
1:30
Chair:
Teresa Yeung

1. Adoption of the Agenda - additions or deletions

2. Coffee Hour

Coffee hour this week:
Marryat Ma
Coffee hour next week:
??

3. Next meeting

Date:
Wednesday, January 21, 1998
Location:
DC1304
Time:
1:30
Chair:
Ion Vasilian
Technical presentation:
Ian Stewart

4. Forthcoming

Chairs:
  1. Tali Zvi (28th)
  2. Balasingham Balakumaran (Feb 4th)
  3. Shalini Aggarwal (Feb 11th)
Tech Presenters:
  1. Tali Zvi (28th) (switched with Teresa)
  2. Ion Vasilian (4th)
  3. Clara Tsang (11th)
  4. Teresa Yeung (18th)

5. Technical Presentations

Presenter:
Faramarz Samavati
Title:
Reverse Subdivision and Multiresolution Curves and Surfaces
Abstract:
 Multiresolution modeling has useful properties. For such modeling, a
suitable method is necessary for converting a high resolution model to
one with a low resolution (decomposition). We propose an effective 
method which may be employed for curves, surfaces and images by 
reverse subdivision.  The method we present is more practical than 
the existing ones.  For example, The B-spline wavelets of this method
 have smaller support and simpler representations than the ones
 previously used for multiresolution.

6. General Discussion Items

7. Action List

8. Director's Meeting

9. Seminars

THEORY SEMINAR - Wednesday, January 14, 1998


John  Tromp,  CWI,  Amsterdam,  will  speak on ``Mutual
Search''.

TIME:                3:30-4:30 p.m.

ROOM:                DC 1304

ABSTRACT

We  define a new type of search problem called ``mutual
search'',  where  k  players  arbitrarily spread over n
nodes  are  required  to  locate  each other by sending
``Anybody  at  node  i?''  query  messages (for example
processes in a computer network).

If  the  messages  are  not delivered in the order they
were  sent  (for  example  when the communication delay
time  is  arbitrary)  then two players require at least
n-1 messages.

In  an  asynchronous  network,  where  the messages are
delivered  in  the order they were sent, 0.88n messages
suffice.   In  a  synchronous  network  0.586n messages
suffice  and  0.536n messages are required in the worst
case.

We  exhibit a simple randomized algorithm with expected
worst-case  cost  of 0.5n messages, and a deterministic
algorithm  for k >= 2 players with a cost well below n for
all k=o(sqrt n ).

The   graph-theoretic   framework   we   formulate  for
expressing  and  analyzing  algorithms for this problem
may be of independent interest.

------------------------------------------------------

10. Lab Cleanup