CECM Colloquium/Discrete Math Seminar

**Wednesday March 28, 2001
in K9509, SFU
**

2:30 - 3:20

Dr William Evans, UBC

Talks on "Recovering lines with fixed linear probes"

3:30 - 4:20

Dr Petr Lisonek, SFU

Talks on "Classification of Binary Linear Codes with Small Codimension"

Abstracts Below

**Dr. Evans's Abstract:**
Suppose the only access we have to an arrangement of $n$ input lines is
to "probe" the arrangement with vertical lines. A probe returns a set
of {\em probe points} which are the intersections of the probe's
vertical line with all input lines. We assume that none of the input
lines is vertical, so a probe line intersects every input line. Our
goal is to reconstruct the set of input lines using a small number of
probe lines. Our task is made more difficult by the fact that we want
one set of probe lines that will allow us to reconstruct any input
arrangement of $n$ lines.

I'll talk about two probe models and some of the algorithms for
reconstructing an arrangement from probe points, but I'll spend most of
the time talking about some new bounds on the number of probe lines that
are needed to enable unique reconstruction.

**Dr. Lisonek's Abstract:**
We will use the natural correspondence between linear codes and
multisets of points in finite projective spaces to develop an
algorithm for the classification of all binary linear codes
with given length and dimension up to isomorphism. Special attention
will be paid to the classification of codes with small codimension
and to their applications in statistical experiment design.