String shuffle: Circuits and graphs
We show that shuffle, the problem of determining whether a string w can be composed from an order preserving shuffle of strings x and y , is not in AC0 AC 0 , but it is in AC1 AC 1 . The fact that shuffle is not in AC0 AC 0 is shown by a reduction of parity to shuffle and invoking the seminal result of Furst et al., while the fact that it is in AC1 AC 1 is implicit in the results of Mansfield. Together, the two results provide a lower and upper bound on the complexity of this combinatorial problem. We also explore an interesting relationship between graphs and the shuffle problem, namely what types of graphs can be represented with strings exhibiting the anti-Monge condition.
string shuffle circuit complexity lower bounds monge