Reducing from Graph Isomorphism to Code Equivalence using Matroids

We study the relationship of isomorphism problems on error-correcting codes and graphs. Specifically, we give two different reductions from the Graph Isomorphism problem (GI) to the Code Equivalence problem (CE) that improve on the parameters of previous such reductions. We give two reductions between these problems. Our main reduction gives a substantial improvement over previous reductions, and uses matroids as an important technical tool. More precisely, the reduction of Petrank and Roth (IEEE Transactions on Information Theory, 1997) maps graphs with n vertices and m edges to codes of dimension m and block length n + 3m. We improve this to dimension n + 2 and block length m. Our second reduction more directly improves on the strategy used by Petrank and Roth, mapping to codes of the same dimension but of reduced block length n + 2m.

MAJOR ADVISOR: Huck Bennett
COMMITTEE: Amir Nayyeri
COMMITTEE: Bella Bose
GCR: Adam Branscum