Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, September 10, 2015, 12:15 pm
Duration: 30 minutes
Location: CAB G61
Speaker: Jerri Nummenpalo
For any integer n > 0 a middle levels Gray code is a cyclic listing of all bitstrings of length 2n + 1 that have either n or n + 1 entries equal to 1 such that any two consequtive bitstrings in the list differ in exactly one bit. The question whether such a Gray code exists has spun a line of intensive research during the last 30 years, and has been answered affirmatively only recently [T. Mütze. Proof of the middle leveles conjecture. arXiv:1404.442, 2014]. This recent proof, albeit constructive, does not directly imply an efficient algorithm for computing the middle levels Gray code.
In this talk we provide an algorithm, that given a bitstring of length 2n+1 and an integer k, computes the next k bitstrings in a middle levels Gray code in time O(nk +n^2) time and O(n) space. Note that if k is at least linear in n, the time bound is linear per bitstring.
This is joint work with Torsten Mütze.
Automatic MiSe System Software Version 1.4803M | admin login