Very happy to have received a grant from the Royal Society to travel between CI and King’s College London

I am very pleased to have received a grant from the British Royal Society to travel between CI and King’s College London over the next two years. This grant will enable collaboration in the field of String Algorithms between CI and King’s College, and it is a joint effort with Maxime Crochemore and Costas Iliopoulos.

The Royal Society is a Fellowship of the world’s most eminent scientists and is the oldest scientific academy in continuous existence. We aim to expand the frontiers of knowledge by championing the development and use of science, mathematics, engineering and medicine for the benefit of humanity and the good of the planet.

A new paper: String Shuffle, with Neerja Mhaskar

Title: String Shuffle: Circuits and Graphs

Authors: Neerja Mhaskar and Michael Soltys

Abstract: 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, but it is in AC1. The fact that shuffle is not in AC0 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 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.