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.