* indicates Dept Colloquium speaker.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.