Decision Tree Complexity of String Matching

Neng Huang University of Chicago


String matching is one of the most fundamental problems in computer science. A natural problem is to determine the number of characters that need to be queried in a string in order to decide if this string contains a certain pattern as a substring. When the alphabet is binary, this is equivalent to the decision tree complexity of string matching. In this talk, I will describe a formula that answers this question for almost every pattern.

Feb 9, 2022 12:30 PM — 1:30 PM
Theory Lunch
JCL 390

Join via Zoom