String Matching: Communication, Circuits, and Learning

Alexander Golovnev, Mika Göös, Daniel Reichman +1

String matching is the problem of deciding whether a given $n$-bit string contains a given $k$-bit pattern. We study the complexity of this problem in three settings. Communication…