Meeting Agenda - 2000.05.24
Meeting Agenda - 2000.05.24
Michael McCool 
Rasterization Revisited
Rasterization is a critical component of forward-projection high-performance rendering systems. The OpenGL conceptual model is in fact based on a rasterization algorithm that introduces some unnecessary limitations.
In particular, rasterization based on edge-plane tests, as opposed to edge tracking, is highly parallelizable, does not require hither or yon clips, resolves on-edge conditions consistently, is consistent with efficient hyperbolic interpolation, and has a relatively simple setup.
Wednesday, 24 May 2000 at 3:30
Computer Science - Algorithms and Complexity Group: Seminar
Title: "A Polynomial-Time Approximation Scheme for the Closest
Substring Problem"
Speaker: Bin Ma, Computer Science, University of Waterloo
Location: DC1304
Abstract:
We consider the following problem:
Closest Substring: Given $n$ strings $s_1$,$s_2$,...,$s_n$ over an
alphabet $\Sigma$, and an integer $L$, find a length $L$ substring
$t_i$ of each $s_i$ and a length $L$ string $s$, minimizing
$d=max_{i=1..n} d(s,t_i)$.
This problem was proved NP-hard, so it does not have a polynomial-time
algorithm unless P=NP. We present a polynomial-time approximation
scheme for it.
The problem is useful in drug-target search, etc.
b3ma@wh.math.uwaterloo.ca
Combinatorics and Optimization
Seminar
Wednesday, 24 May 2000 at 10:30AM
** MOVED TO ** Thursday, 25 May 2000 at 3:00PM
-------
Cryptography Seminar - Security Analysis for Implicit Certificates
Daniel Brown
Dept. of Combinatorics & Optimization, University of Waterloo
ABSTRACT
Standard (explicit) certificates authentiacte user's public keys with
a digital signature of a certificate authority. Implicit
certificates also authenticate user's public keys but do not directly
use a digital signature. In an implicit certificate the public key is
first reconstructed, then used and lastly authenticated.
Authentication takes place only after the reconstructed public key is
used successfully in another public key cryptographic scheme. This
talk will look at a particular implicit certificate scheme and a
formal proof of its security.
Friday, 26 May 2000 at 2:00PM
Computer Science - Databases Group: Seminar
Title: "Applications of AML"
Speaker: Arun Marathe, Computer Science, University of Waterloo
Location: DC1331, ICR Boardroom
Abstract:
I shall present several applications of the Array Manipulation
Language (AML) that we have designed to manipulate array data.
Applications include wavelet reconstruction, JPEG-based still image
compression, and several queries from the satellite image processing
domain. Array manipulations in these and other queries are highly
structured and it will be seen how AML captures such regularities.
I shall also present query evaluation times for these Queries (except
JPEG) on an iterator-based AML evaluator. For fun, I shall compare
these times with running times of the C++ programs that I wrote for
the same queries.
Combinatorics and Optimization
Colloquium
Friday, 26 May 2000 at 3:30PM
Math & Computer, Room 5158
-------
Tutte Colloquium - Recent progress on the crossing number
Prof. Bruce Richter
Dept. of Combinatorics & Optimization, University of Waterloo
ABSTRACT
More than 25 years ago, Harary, Kainen and Schwenk conjectured that
the crossing number of the Cartesian product of an $m$-cycle with an
$n$-cycle is $(m-2)n$, for $3\le m\le n$. Progress has been slow,
with $cr(C_5\times C_5)=15$ only being proved in 1995, fifteen years
after $C_4\times C_n$ was shown to be 2n. In this talk, some general
results about planar configurations related to drawings of $C_m\times
C_n$ will be described, together with applications to the crossing
numbers of $C_6\times C_n$ and $C_7\times C_n$.
Pure Mathematics
Seminar
Monday, 29 May 2000 at 3:30PM
MC 5158A
-------
The Model Theory of Algebraically Closed Fields
Dan Cook
Department of Pure Mathematics, University of Waterloo
ABSTRACT
Model theory (a branch of mathematical logic) can express properties
of algebraic subsets of complex n-space. To begin with, if F is an
algebraically closed field, the first-order definable subsets of F^n
are precisely the constructible subsets of algebraic geometry.
I shall introduce the Morley rank of a first-order formula, and show a
characterization of Morley rank in the setting of algebraically closed
fields. In this case, the Morley rank of a formula is equal to the
topological dimension of the constructible set which it defines.
Pure Mathematics
Colloquium
Tuesday, 30 May 2000 at 3:30PM
MC 5136
-------
Algebraic aspects of discrete tomography
Professor R. Tijdeman
Mathematical Institute, University of Leiden, The Netherlands
ABSTRACT
Discrete tomography concerns the reconstruction of 0-1-arrays from all
the line sums in a few directions. Techniques for discrete tomography
are being used in medical sciences. Usually the system is
underdetermined and additional conditions like convexity of the 1's
are needed to make the reconstruction possible. We first analyze the
set of solutions over the integers having the required line sums. This
leads to an approximate solution which differs from the original
configuration by at most a prescribed amount. By additional techniques
we have developed an algorithm which at least for small sizes yields
satisfactory results. This is joint work with Lajos Hajdu (Debrecen).
Refreshments will be provided at the talk. Everyone is welcome to attend.