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 AC0AC0, but it is in AC1AC1. The fact that shuffle is not in AC0AC0 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 AC1AC1 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.