I have supervised some undergraduate research and honors projects over the years. Below is a list of the projects, along with a brief abstract and links where appropriate.
Quantum Key Distribution – Max Taylor & Joshua Mwandu (2016)
This project looked at the BB84, a quantum key distribution scheme developed by Charles Bennett and Gilles Brassard in 1984. The project focused on understanding the mathematical tools used to understand quantum coding techniques along with an understanding of the protocol.
This project was part of the Dahlgren Undergraduate Research Collaboration and was co-sponsored by Navy Scientist (and UMW alumnus) Jacob Farinholt.
Clifford Embeddings: a problem in quantum coding theory – Alaina Morello (2014)
Error correcting codes allow information to be transmitted over noisy channels in a way that the original message can be recovered if the data was corrupted. Fault tolerant quantum computation would allow the information to be encoded and decoded imperfectly and still retain its original state. Quantum computers in actual existence are limited to a small amount of operations on a few qubits but large scale quantum computers promise to provide computational capabilities believed to be infeasible under our current classical systems, as indicated by Shor’s fast factoring algorithm and Grover’s search algorithm, for example. Our work focuses on a particular technique for performing quantum coding theory and reduces to a problem in abstract algebra.
This project was part of the Dahlgren Undergraduate Research Collaboration and was co-sponsored by Navy Scientist (and UMW alumnus) Jacob Farinholt.
Anti-blocking sets – Kelly Scott (2012)
Anti-blocking sets are found in finite projective planes and are characterized by the property that they are not a subset of a blocking set. Because a blocking set S contains by definition at least one point from every line in a finite projective plane π, we can conclude that an antiblocking set must then be missing a point from at least one of these lines. Therefore, we can quickly determine that an anti-blocking set must be a subset of the complement of a line and furthermore, in the case that more than one line is not blocked, we are able to provide a complete characterization. In Section 4 we establish a connection between anti-blocking sets and Besicovitch sets in affine spaces, a topic which has been studied recently, in order to find a minimum anti-blocking set. We end with an original construction of an anti-blocking set including a pencil of conics.
Kelly’s thesis was extended and published in the Journal of Combinatorical Designs.
c-Dominating sets for families of graphs – Kelsie Snyder (2011)
The topic of domination in graphs has a rich history, beginning with chess enthusiasts in the 1850s determining how many queens are necessary to dominate an entire chessboard and continuing to current problems involving computer communication networks, social network theory, and other similar problems. We define a dominating set of a graph G to be a set of vertices of G such that every vertex of G is either in the set or adjacent to a vertex in the set. The domination number for a graph G is the size of a minimum dominating set. Determining the domination number of graphs can prove highly useful in solving many types of problems, and recent studies of dominating sets reflect this.
We focus on describing various families of graphs in terms of bounds on the domination number. Although the computation of dominating sets for arbitrary graphs is an NP-complete problem, it is possible to compute certain bounds on the domination number for certain families of graphs. We examine families of graphs, specifically the family of grids, and determine the bounds on domination number for these families.
Kelsie’s honors thesis was published in the spring 2011 issue of Metamorphosis, a journal of research and creativity at public liberal arts colleges.
Deletion-correcting properties for classes of error-correcting codes – Carrie Lowry (Fall 2009)
This thesis deals with the correction of errors that occur during the transmission of data. Have you ever received an email from an acquaintance that was digitally unreadable? Or have you tried to buy something online and the transfer of data fails to go through? In this paper we will look at classes of codes that will be able to correct the deletion of bits. We start by looking at classes of codes that will stand the deletion of a single unit of data. Our focus is on the deletion correcting properties of classes of optical orthogonal codes constructed using the techniques of finite geometry.
The weight enumerator for a class of LDPC codes generated by hyperovals – Katie Hunsburger (2009)
The weight enumerator for a class of LDPC codes is explored. The class was originally examined during the Jepson Summer Science institute in 2008 (described below). In this project, small weight codewords are described both geometrically and algebraically. For smaller codes, it is shown that all codewords can be represented geometrically through a variety of constructions that involve hyperovals. These results are then extended to arbitrary fields of even characteristic.
Designing codes to fit Your needs: a closer look at the Bose-Chaudhuri-Hocquenghem (BCH) codes – Jake Farinholt (2009)
In this project, Jake looks at the algebraic methods for constructing a class of linear error-correcting codes known as BCH codes. These codes are interesting in that one can choose the desired minimum distance first. We look at the algebraic techniques and the consequences on the length and dimension for a prescribed minimum distance.
Jake’s thesis is published in the Spring 2011 issue of The Pi Mu Epsilon Journal.
Cryptography based on determining sets – Christine Exley (2009)
We examine a cryptographic protocol that involves special sets of points, called determining sets in a finite projective plane. The original protocol was discovered in the late 1990s and is patented. Our investigation looks at different methods for constructing determining sets and thereby offering different ways of implementing the cryptographic algorithm.
Coding and cryptography with hyperovals of PG(2,2s) – Catherine Castleberry and Katie Hunsburger (SSI 2008)
A hyperoval of the projective plane PG(2,q), q even, is a collection of q+2 points, no three collinear. In this project, we use hyperovals to construct several families of secret sharing schemes and binary linear codes. The secret sharing schemes use either the nucleus of the underlying conic (used to create the regular hyperoval) or the coefficients of the quadratic form as the secret. The codes are generated by incidence matrices arising from the points and the secant or skew lines. We are able to prove many results about minimum distances and dimensions of our codes.
The results of this project were published in the Bulletin of the Institute of Combinatorics and its Applications.
Teaching geometry with The Geometer’s Sketchpad – Liz Liskom (2008)
Liz investigated the popular software package called The Geometer’s Sketchpad and ways that geometry and algebra concepts can be taught using this software. She created sketches which can be used to demonstrate and explore concepts in algebra and geometry. Some sketches link geometry and algebra in untraditional ways. Moreover, she developed sketches which enable students to discover mathematical concepts.
Investigation of a min-max scheduling problem – Ryan Johnson (2007)
We investigate a combinatorial problem that arises naturally in the scheduling of groups. Suppose n = jk students are to be broken into j groups of size k over a period of days, subject to the constraint that no two students work together in a group more than once. We wish to determine m(j,k), the minimum number of days for a maximal schedule. In this project, we determined that m(j,2) = j or j+1 depending on the parity of j. Generalizations for larger values of k are also explored.
Codes generated by matrix expansions – Chris Meyer (2006)
A new class of error-correcting codes is created from a matrix operation. The matrix operation takes a point-block incidence and produces a new point-block incidence with some desirable properties, including a doubling of the girth of the initial matrix’s Tanner graph. A specific example is created using PG(2,q), and the results are generalized to any point-block incidence structure. These codes are analyzed mathematically and through simulation via belief propagation decoding.
Chris’s thesis was published in vol. 7 (2001) issue of the Moorhead Electronic Journal of Applicable Mathematics.
LDPC codes generated by conics in the classical projective plane – Sean Droms and Chris Meyer (SSI 2005)
We construct various classes of low-density parity-check codes using point-line incidence structures in the classical projective plane PG(2,q). Each incidence structure is based on the various point and line classes created by the geometry of a conic in the plane. For each class, we provide various properties about dimension and minimum distance. In addition, we test the effectiveness of our codes by simulating the shorter length codes under iterative probabilistic decoding.
The results of this project were published in the journal Designs, Codes and Cryptography.
An elementary solution to the ménage problem – Amanda Passmore (2005)
The ménage problem asks for the number of ways to seat n husbands and their n wives at a circular table, alternating men and women, so that no one is seated next to his or her spouse. In this project, we explore a solution to the problem that involves only elementary counting techniques, including the principle of inclusion/exclusion.
A new class of codes from finite geometry – Jennifer Stovall (2005)
Here we consider the construction of a class of LDPC codes generated by the affine portion of a generalized quadrangle. The construction involves the set of affine lines of AG(4,q) meeting the “hyperplane at infinity” in a point of a fixed elliptic quadric. The resulting low-density codes perform well under iterative probabilistic decoding as is exhibited through simulation results.
Jenny’s thesis was published in of The Pi Mu Epsilon Journal.
On Codes Generated from Quadratic Surfaces of PG(3,q) – Amanda Passmore and Jennifer Stovall (SSI 2004)
In this project, we consider a construction of some low-density parity-check codes generated from the two non-degenerate quadratic surfaces in PG(3,q). In the first construction, we consider the points and ruling lines of a hyperbolic quadric. In the second construction, we use the points and lines skew to an elliptic quadric. In both constructions, we look at the bipartite incidence graph and corresponding incidence matrix. This matrix is used as the parity check matrix for a code and these codes are examined mathematically and through computer simulation under iterative probabilistic decoding.
The results of this project were published in the Rose-Hulman Undergraduate Research Journal.
Combinatorial Designs and Scheduling Golf – Monika Rut (UIC, 2003)
In this project, we considered ways of arranging 12 golfers into 3 groups of 4 golfers each in such a way that every golfer plays with every other golfer in some sort of regular way. One best possible solution arises from a combinatorial design with parameters 3-(12,4,1). Unfortunately, no such design exists. This led us to a search for a “best possible” configuration of the golfers.