I wrote my undergraduate thesis on the Graph Isomorphism problem, and within that, the “Paths” invariant, which is incredibly powerful test for discerning between potentially isomorphic graphs in cubic (and fully paralellizable) time.
The main findings of my thesis were that:
Unlike was theorized by XXX, copaths graphs exist, and finding them is easily done through some mapreduces, or on a GPU.
Measuring discriminatory power to value ratio of invariants within graph isomorphism is possible and can help us devise better algorithms for practical isomorphism detection.
Paths as an invariant does not need to be calculated past N.
Since I did the paths stuff earlier than expected, I started working on Random Graph theory and found that:
Random Graph generators almost all are random matrix generators. This understates the frequency of highly auto-isomorphic graphs by one-to-factorial odds.
We can create a better random graph generator to evaluate random graph algorithms, and doing so changes the running time bounds that we have been able to determine for the algorithm.
This thesis was successfully defended in May of 2016, and recieved highest honors in Computer Science.