A New Upper Bound for Separating Words

A New Upper Bound for Separating Words (via Zoom)

Abstract: We prove that for any distinct strings x,y of length n, there is a DFA with n^(1/3) states that accepts x but not y. This improves Robson's 1989 bound of n^(2/5) on the "separating words problem". 

Bio: I'm a second year graduate student of Ben Green, at Oxford.