Date of Award
5-2016
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Legacy Department
Mathematical Science
Committee Member
Dr. Shuhong Gao, Committee Chair
Committee Member
Dr. Felice Manganiello
Committee Member
Dr. Gretchen Matthews
Committee Member
Dr. Michael Pursley
Abstract
Expander graphs are highly connected sparse graphs which lie at the interface of many different fields of study. For example, they play important roles in prime sieves, cryptography, compressive sensing, metric embedding, and coding theory to name a few. This thesis focuses on the connections between sparse graphs and coding theory. It is a major challenge to explicitly construct sparse graphs with good expansion properties, for example Ramanujan graphs. Nevertheless, explicit constructions do exist, and in this thesis, we survey many of these constructions up to this point including a new construction which slightly improves on an earlier edge expansion bound. The edge expansion of a graph is crucial in applications, and it is well-known that computing the edge expansion of an arbitrary graph is NP-hard. We present a simple algo-rithm for approximating the edge expansion of a graph using linear programming techniques. While Andersen and Lang (2008) proved similar results, our analysis attacks the problem from a different vantage point and was discovered independently. The main contribution in the thesis is a new result in fast decoding for expander codes. Current algorithms in the literature can decode a constant fraction of errors in linear time but require that the underlying graphs have vertex expansion at least 1/2. We present a fast decoding algorithm that can decode a constant fraction of errors in linear time given any vertex expansion (even if it is much smaller than 1/2) by using a stronger local code, and the fraction of errors corrected almost doubles that of Viderman (2013).
Recommended Citation
Dowling, Michael C. Jr., "Expander Graphs and Coding Theory" (2016). All Dissertations. 1736.
https://open.clemson.edu/all_dissertations/1736