Research

Diagonal Forms over Finite Fields

Advised by Dr. Rachel Petrik

Abstract: The Chevalley-Warning Theorems imply that a polynomial over a fixed finite field will always have a nontrivial zero given that the polynomial has sufficiently many variables. In particular, the number of variables must exceed the degree of the polynomial. While this bound is sharp in general, this result can be improved for diagonal forms. We investigate the number of variables that a diagonal form of degree 15 must have to guarantee a nontrivial zero.

Spectral Graph Sampling (in progress)

Advised by Dr. Kyle Wilson and Dr. Ian Ludden

Introduction (not an abstract): For the purposes of testing algorithms on graphs, it is useful to test performances on classes of graphs in order to characterize performance. In the context of geometric computer vision, visual reconstruction problems are represented by highly-structured graphs, and solutions to these problems involve applying an algorithm to the underlying graph. Results have shown that the performance of most current solvers for these problems depends on the spectral properties of this underlying graph, so in testing these solvers, we would like classes of graphs that share similar spectral properties. However, current random graph generators do not produce graphs with similar spectral properties - they lack the type of real-world structure seen in the visual reconstruction problems. Spectral graph sampling allows us to produce random graphs that share similar spectral properties to an input graph, preserving the underlying rich structure.

Cellular Automata (in progress)

Advised by Dr. Joshua Holden

Abstract: Elementary Cellular Automata (ECA) are one-dimensional cellular automata over a possibly infinite grid of squares where each square has two possible states, and its state combined with its neighbors’ states determines its state in the next iteration based on a given rule. One such ECA rule, Rule 110, is capable of universal computation, meaning that an ECA using Rule 110 could theoretically compute anything that is computable. Stranded Cellular Automata (SCA) are motivated by ECAs but each cell is a rectangle containing two possible strands moving vertically that can either remain parallel, or cross over each other, governed by the turning rule. There is an additional crossing rule to determine how exactly the strands cross over each other. We show that two steps of an SCA can simulate certain ECA rules, and that relaxing some constraints of an SCA can simulate additional ECA rules. We also present some additional ideas for SCAs simulating ECAs that could potentially simulate Rule 110, which would show that SCAs are also capable of universal computation.