Spring 2002

* indicates Dept Colloquium speaker.

January 24, 2002

TITLE:
A new algorithm for decoding Reed-Solomon codes

SPEAKER:
Shuhong Gao

AFFILIATION: Clemson University

ABSTRACT:

We develop a simple new algorithm for decoding Reed-Solomon codes. Our method uses fast Fourier transforms and computes the message symbols directly without finding error locations or error magnitudes. Compared with the Berlekamp-Massey algorithm which was discovered in the late 1960's, the new method has a similar time complexity but requires simpler structures in both hardware and software implementations.

January 31, 2002

TITLE:
L(2,1) Colorings and its Application to the Channel Assignment Problem

SPEAKER:
John Villalpando

AFFILIATION: Clemson University

ABSTRACT:

The channel assignment problem is the problem of assigning frequencies to radio transmitters in such a way that the communications do not interfere. Two transmitters are considered to interfere with each other if they share similar frequencies and are at a prescribed distance from one another.

An L(2,1) coloring of a graph G is a non-negative labeling f of V(G) such that adjacent vertices differ in color by two and vertices at distance two differ in color. The span \lambda(G) on a graph G is the smallest k such that there exists an L(2,1) coloring using only the colors {0,1, ... , k} to color the vertices of G.

In this presentation we begin by discussing the channel assignment problem. We focus on L(2,1) colorings and their relationship to the channel assignment problem. We introduce no-hole and irreducible L(2,1) colorings, and consider the lower no-hole span $\lambda_f(G)$ and the upper no-hole span \Lambda_f(G) of a graph G. We determine the lower and upper no-hole span for paths and cycles. We finish by demonstrating the existence of an irreducible no-hole coloring on all trees that are not stars.

February 7, 2002

TITLE:
Ramanujan congruences for m-regular partition functions

SPEAKER:
David Penniston

AFFILIATION: Furman University

ABSTRACT:

The great Indian mathematician S. Ramanujan proved that the unrestricted
partition function p(n) has the remarkable property

that for every nonnegative integer n,

p(5n+4)
is divisible by 5,

p(7n+5) is divisible by 7, and

p(11n+6)
is divisible by 11.

Recently K. Ono has shown that p(n) satisfies similar "Ramanujan congruences" for every prime that is at least 5.

In this talk we focus on m-regular partitions, which are those partitions
none of whose parts is divisible by m. In particular, we will see
that for certain values of m, the m-regular partition function satisfies
Ramanujan congruences, and along the way see some (surprising?) connections
with elliptic curves, K3 surfaces and representation theory.

February 14, 2002

TITLE:
Mastermind and Static Mastermind Revisited

SPEAKER:
Wayne Goddard

AFFILIATION: University of Natal

ABSTRACT:

In Mastermind a codesetter creates an n-position secret code from a
palette of k colours and a codebreaker must determine

the code with a series of questions. In the static version, the codebreaker
must supply at one go a list of questions the answers to which must uniquely
determine the secret code. In this talk we discuss what is known about
the optimal strategies for the original game against a random opponent
and against an adversary. For static mastermind we solve it for small cases.
Possibly surprising is the solution for 4 positions and arbitrary k.

February 21, 2002

TITLE:
Robinson-Schensted-Knuth Insertion and the Jeu de Taquin

SPEAKER:
Jeff Stroomer

AFFILIATION: Xilinx, Inc.

ABSTRACT:

Most algorithms are understandable: one understands (perhaps after some
study) what makes the algorithm work. A few, however, are mysterious:
we are confident the algorithm works because we have proved it does, but
it's not clear *why* the algorithm ought to work. In this
talk we discuss two mysterious algorithms, namely Robinson-Schensted-Knuth
insertion, and Schützenberger's *jeu de taquin*. Each is
simple enough to describe in a few minutes, and can be performed by hand
with pencil and paper. Nevertheless, their results describe, in combinatorial
terms, the workings of the symmetric group, symmetric functions,
and representations of the symmetric group and general linear group.

February 28, 2002

TITLE:
Designing Self-stabilizing Algorithms

SPEAKER:
David Jacobs

AFFILIATION: CS, Clemson University

ABSTRACT:

In the usual algorithmic model, many graph problems (like finding a maximal independent set) are trivial, requiring for example, only a simple greedy loop. But in the self-stabilizing distributed model such problems are less obvious. In this model, a node can read only its own variables and those of its neighbors. This talk will explain the model, give examples of several self-stabilizing algorithms discovered by our algorithms group (for finding maximal independent sets, minimal dominating sets, colorings, maximal matchings, and maximal k-dependent sets), and discuss some proof techniques that have been found useful.

March 7, 2002

TITLE:
Binary Shift-Register Sequences: Correlation Properties andApplications

SPEAKER:
Michael Pursley

AFFILIATION: ECE, Clemson University

ABSTRACT:

Direct-sequence spread-spectrum systems employ pseudorandom and related
sequences to permit reliable communications in the presence of various
types of interference, such as multipath interference, multiple-access
interference, and interference from narrow-band emitters operating in the
same frequency band. The sequences must be selected to have good
correlation properties in order for the potential benefits of direct-sequence
spread spectrum to be realized, and the correlation properties adopted
for sequence selection must be matched to the intended applications for
the spread-spectrum system. The periodic and aperiodic correlation
properties of some well-known sequences are presented and their relevance
to system performance is described.

**Biography for Michael B. Pursley**

Michael Pursley was a faculty member in the Department of Electrical and Computer Engineering and the Coordinated Science Laboratory at the University of Illinois during 1974-93. Since then he has been the Holcombe Professor of Electrical and Computer Engineering at Clemson University. He has held visiting faculty positions at UCLA and the Caltech.

Dr. Pursley is a Fellow of the Institute of Electrical and Electronics Engineers (IEEE), he has served on the Board of Governors of the IEEE Information Theory Society, and he served as president of the Information Theory Society. He was a member of the Editorial Board of the Proceedings of the IEEE for the period 1984-1991. He is currently a member of Editorial Advisory Board for the International Journal of Wireless Information Networks, and a senior editor for the IEEE Journal of Selected Areas in Communications.

Dr. Pursley was awarded an IEEE Centennial Medal in 1984, and in 1996
he received the Ellersick Award of the IEEE Communications Society.
In 2000 he received an IEEE Millennium Medal. He has also received several
awards from Clemson University for research and scholarly achievement.

March 14, 2002

TITLE:
Some families of finite commutative rings and their applications to Coding
Theory

SPEAKER:
Gilberto Bini

AFFILIATION: University of Michigan, Ann Arbor

ABSTRACT:

In the last decade, some nonlinear binary error-correcting codes have been viewed more easily as images of codes over Galois rings. In particular, the formal duality between binary Kerdock codes and Preparata codes has been interpreted as ordinary duality over the ring of integers modulo 4. In this talk, we shall give an overview on various significant properties of two families of finite commutative rings, i.e., the Galois rings and the Quasi-Galois rings. Additionally, some applications to Coding Theory will be discussed.

March 15, 2002

TITLE:
The Number Theory of Partitions

SPEAKER:
Ken Ono

AFFILIATION: University of
Wisconsin at Madison

ABSTRACT:

At first glance, the stuff of partitions seems like child's play. After
all, *4=3+1=2+2=2+1+1=1+1+1+1*, and so *p(4)=5*. We will discuss
classical works of Hardy, Ramanujan and Rademacher on asymptotics and congruences
and conclude with more recent works. Recently we have learned quite a bit
about congruences for the number of partitions and have learned of new
connections with deep and subtle questions in arithmetical algebraic geometry.

March 26, 2002

TITLE:
Metric Geometry Induced by a Field

SPEAKER:
Arthur Sherk

AFFILIATION: University of Toronto

ABSTRACT:

Let *K* be an *n*-fold extension of a field *F*. That
is to say, *K* is an *n*-dimensional vector space over *F*,
and *K* itself is a field. Using the Norm and Trace mappings of *K*
onto *F*, we define measures of length and angle, thus turning *K*
into a metric geometry, which we call *G(K)*.

The classical example is *G(C)*, where *C* is the field of
Complex Numbers. It is well-known that *G(C)* is Euclidean Plane
Geometry.

In this talk, we examine *G(K)*, where K is a quadratic extension
of the finite field *GF(q)* (*q* odd), finding *G(K)* to
be the "natural" finite equivalent of Euclidean Plane Geometry. We then
study *G(K)*, where *K* is a cubic extension of *GF(q)*
( *q* and *6* relatively prime). In this case, *G(K)* does
not resemble Euclidean Geometry at all, but is a reasonable finite equivalent
of classical Elliptic Geometry.

March 28, 2002

TITLE:
Computing Linear Programming Relaxations of Discrete Sets: A Special
Case yielding the Convex Hull

SPEAKER:
Warren Adams

AFFILIATION: Clemson University

ABSTRACT:

Given a polyhedral set, a fundamental problem in integer programming is to obtain an explicit algebraic characterization of the convex hull of binary points that lie within the set. Such a characterization reduces a 0-1 optimization problem to a much simpler linear program. One method for accomplishing this is a reformulation-linearization technique (rlt). As the name suggests, the method is a two-step procedure that first reformulates the problem through the construction of redundant nonlinear inequalities, and subsequently linearizes the resulting program by casting it in a higher dimensional space through a substitution of variables. Depending on the manner in which the reformulation is computed, different polyhedral outer approximations of the set of desired 0-1 points are obtained. The tightest approximation is the convex hull. Unfortunately, the representation yielding the convex hull can have both an exponential number of constraints and variables. This talk gives an intuitive review of the rlt and then focuses on a discrete problem arising in cryptography. The motivating challenge is to factor an integer into the product of primes. A variant of this problem has been considered in the literature. For this variant, the convex hull is characterized and the exponential number of facets provided. We show how this characterization is readily available in terms of a straightforward application of the rlt. In fact, we give a representation in a higher-variable space whose projection onto the space of the original variables gives the convex hull and all its facets. The higher-dimensional polytope is polynomial in size in terms of the number of variables and constraints.

The original investigations in the rlt are joint work with Hanif Sherali
of Virginia Tech, and the more recent advances in cryptography were performed
in collaboration with Robin Lougee-Heimer of IBM TJ Watson Research Center
and Shuhong Gao of Clemson University.

April 4, 2002

TITLE:
Explicit towers of function fields over finite fields

SPEAKER:
Hiren Maharaj

AFFILIATION: Clemson University

ABSTRACT:

Explicit towers of function fields over finite fields make it possible to explicitly construct asymptotically good sequences of algebraic geometric codes. By concatenation with short block codes, these codes have asymptotic performance close to or exceeding the Gilbert-Varshamov bound. The first family of such towers was discovered in 1995 by Garcia and Stichtenoth. Today, the search for further families of towers is still on. This introductory talk will explain why this is the case and also how one may go about finding towers.

April 11, 2002

TITLE:
Meet-Tolerance Graphs

SPEAKER:
Robert E. Jamison

AFFILIATION: Clemson University

ABSTRACT:

Let $S_1, S_2, S_3, ..., S_d$ denote finite sets. For any integral tolerance t with $0 < t < d$, define the meet-tolerance graph $MG_t(S_1, S_2, S_3, ..., S_d) $ as follows. The vertices are all vectors $[x_1, x_2, ..., x_d]$ where $x_i \in S_i$. Two vectors are adjacent iff they agree in at least $t$ coordinates.

The sets S_i will be called the (coordinate) {\em stacks}. We may picture the meet-tolerance graph by imagining the stacks as lined up side by side with a vertex represented by a choice of one element from each stack. The vertices thus represent the choice functions for the set system $[ S_1, S_2, S_3, ..., S_d ]$. Two such functions are adjacent iff they agree in at least t places. For $t = 1$, the meet-tolerance graphs are the co-categorical products of complete graphs (independents sets). These have been studied (sometimes in the complementary form) by Lovasz, Nesetril, Novick, Perkel, Putr, Rall, and others.

For $t = d-1$, the meet-tolerance graphs are box (Cartesian) products of complete graphs, called Hamming graphs by Bandelt and Mulder. For any integer $0 < p < t,$ it is easy to check that the $p$th power of the Hamming graph $MG_{d-1}(s_1, s_2, ..., s_d)$ is just $MG_{d-p}(s_1, s_2, ... , s_d)$. Here the $p$th power of a graph $G$ has $v$ and $w$ adjacent iff $distG(v,w) \leq p$. Thus the meet-tolerance graphs are just powers of Hamming graphs. For the purposes of the present investigation, however, it seems more natural to view the case $t=1$ as the base case with larger tolerances as generalizations ending in the Hamming graphs as an extreme case rather than the other way around.

This talk will survey meet-tolerance graphs, outline their origins in
number theory, discuss the independence number $\alpha(G)$ , the chromatic
number $\chi(G)$, and the clique number $\omega(G)$, and indicate their
close connection with finite geometries.

April 18, 2002

TITLE:
Galois module structure of the group of p-th power classes of a cyclic
field

SPEAKER:
John Swallow

AFFILIATION: Davidson College

ABSTRACT:

Let p be a prime. In Galois theory over a field K containing a primitive pth root of unity, field extensions L generated by a pth root of an element of K, say L=K(b^(1/p)), correspond to subgroups of order p of a certain group, namely the multiplicative group of pth power classes of the field K. We denote this by K*/K*^p, where K* is the group of nonzero elements of K. This correspondence is known as Kummer theory.

In this talk we consider the notion of "Kummer closure extensions":
the normal closures of Kummer extensions L/K when K is itself a Galois
extension of a field F. The case of cyclic Galois extensions K/F
of degree p^n is of

particular interest. Waterhouse has determined the possible Galois
groups for such extensions, and in joint work with Minac and Schultz we
extend his result to determine the Galois group of the "maximal Kummer
extension of K", that is, the Galois group of K({b^(1/p): b in K*}) over
F. This Galois group was essentially determined

by Faddeev for local fields, and, surprisingly, the general case displays
the same local flavor.

April 25, 2002

TITLE:
Binary codes of triangular graphs and permutation decoding

SPEAKER:
J. D. Key

AFFILIATION: Clemson University

ABSTRACT:

For any n, the triangular graph T(n) is the line graph of the complete graph K_n, i.e. the vertices are the 2-subsets of Omega ={1,2,..,n} and vertices {a,b} and {c,d} are adjacent if they have one letter from Omega in common. Thus the valency is 2(n-1).

If A is an adjacency matrix for T(n) the row span of A over the field GF(2) of order 2 forms a binary code with parameters [n(n-1)/2,n-1,n-1]_2 for n odd and [n(n-1)/2,n-2,2(n-1)]_2 for n even, and we take n >4 to avoid trivial cases. The weight enumerator of the code is known for any n and the minimum weight of the dual code is 3.

The automorphism group of the graph and code is S_n for n > 4 except for n=6 when the code has the larger group PGL_4(2) acting. We obtain explicit permutation decoding sets in S_n for these codes.

This is joint work with J. Moori and B.~G. Rodrigues of the University
of Natal-Pietermaritzburg.

Back to ADM Seminar Page