DIMACS - Graduate Student Combinatorics Seminar

Title: DeBruijn Sequences

Speaker: Ross Berkowitz, Rutgers University

Date: Wednesday, October 1, 2014 12:10pm

Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ


Let's say somebody asks you to construct a sequence of ones and zeros with the following property: You will be given a window through which you look at 10 consecutive bits of your sequence, and you must be able to identify where in the sequence these 10 bits lay. How long can you make such a sequence? We will answer this question along with further considerations including: how quickly can you locate the 10 bit subsequence in the original string, how would you proceed if instead of an n-bit string you are to construct an nxn matrix, and if time permits how much can you do when your window is dirty, and some of the data is misreported.

See: http://math.rutgers.edu/~nhf12/GCS/