Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Thursday, September 10, 2015, 12:15 pm

Duration: 30 minutes

Location: CAB G61

Speaker: Jerri Nummenpalo

Efficient computation of middle levels Gray codes

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login