Meeting Agenda
Wednesday, January 7, 1998
- Location:
- DC1304
- Time:
- 1:30
- Chair:
- Ian Stewart
1. Adoption of the Agenda - additions or deletions
2. Coffee Hour
Coffee hour this week:
- ??
- Coffee hour next week:
- ??
3. Next meeting
- Date:
- Wednesday, January 14, 1998
- Location:
- DC1304
- Time:
- 1:30
- Chair:
- Teresa Yeung (switched with Clara Tsang)
- Technical presentation:
- Faramarz Samavati
4. Forthcoming
- Chairs:
-
- Ion Vasilian (21st)
- Tali Zvi (28th)
- Balasingham Balakumaran (Feb 4th)
- Tech Presenters:
-
- Ian Stewart (21st)
- Tali Zvi (28th) (switched with Teresa)
- Teresa Yeung (Feb 4th) (switched with Tali)
5. Technical Presentations
- Presenter:
- Navid Sadikali
- Title:
- On the Real - Take 2
- Abstract:
- In a previous talk, I made some observations about the idea of
"realism" in computer graphics. The crux of the talk was that
much of what we do in CG is supported by a tenuos set of terms
that fails subjective. Finding a standard from which we can
validate our work was found to be next to impossible.
In this talk, I wish to examine concept of realism from the perspective
of art history. I shall try to demonstrate that artists have never
looked at the goal of depiction as the quest for matching the
real world. Rather, a realistic image is one that has the potential
capacity to evoke the real scene. The distinction between these
two ideas will be made clear.
6. General Discussion Items
- The Eurographics submission deadline is January 9, 1998. Please see
http://www.eg98.gpcg.pt/submissions/ for requirements.
- SIGGRAPH deadline (for North America) is January 14, 1998.
7. Action List
8. Director's Meeting
9. Seminars
THEORY SEMINAR - Wednesday, January 7, 1998 --> TODAY
C. K. Poon, City University of Hong Kong, will speak on
``A Parallel Algorithm for Finding a Minimum Spanning
Forest''.
TIME: 3:30-4:30 p.m.
ROOM: DC 1304
ABSTRACT
Finding a minimum spanning forest of a given graph is
one of the most well studied problems in computer
science.
In this talk, we present a randomized EREW PRAM
algorithm to find a minimum spanning forest in a
weighted undirected graph. On an n-vertex graph the
algorithm runs in
1+epsilon
o((log n) )
expected time for any epsilon >0 and performs linear
expected work. This is the first linear work, polylog
time algorithm on the EREW PRAM for this problem.
This also gives parallel algorithms that perform
expected linear work on two more realistic models of
parallel computation, the QSM and the BSP.
Joint work with Prof. Vijaya Ramachandran (U of Texas
at Austin)
Biography:
Dr. C.K. Poon obtained his Ph.D. in U of Toronto in
1995. Then he was at U of Texas at Austin as a
postdoctoral fellow for a year before joining the City
U of Hong Kong as a Research Assistant Professor. His
major research interest is in computational complexity,
data structures and algorithms.
------------------------------------------------------
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