Computationally Speaking Seminar Series: Gray codes: Easier and Harder

Abstract: 

A Gray code is an ordering of all n-bit binary strings in which consecutive strings differ in a single bit. For example, 00, 01, 11, 10 is the binary reflected Gray code (BRGC) for n = 2. Dozens of puzzles are designed to have the BRGC as their solution, including Spin-Out by Binary Arts (n=7), The Brain by Mag-N if (n=8), as well as the venerable Towers of Hanoi and Baguenaudier (Chinese ring puzzle). While these puzzles are fun, they can also become tedious as they require an exponential number of moves, and intermediate states have only one correct move forward and one incorrect move backward. We present a more general puzzle framework which supports more moves from each state as well as "Grey code" solutions as short as n2 moves—so long as you know what you are doing. Our second topic involves computational complexity. Suppose that we are given a subset of the n-bit binary strings, and we want to know if that subset has a Gray code. In other words, we want to know if there is a Hamilton path in a particular induced subgraph of the n-cube. We show that this problem is NP-hard by a reduction from the Grid Graph Hamilton path problem. Then we use this foundational result to prove that scores of similar problems are NP-hard. This includes ordering subsets of permutations using adjacent-transpositions, and spanning trees using edge-pivots. The latter result complements the recent papers Pivot Gray Codes for the Spanning Trees of a Graph ft. the Fan by Cameron, Grubb, and Sawada.

About the Speaker: 

Aaron Williams is one of the strongest researchers in the area of combinatorial generation. He is well known for his engaging and innovative presentations. He is an Associate Professor at Williams College, USA. 3-0.