[Theory] [Theory Lunch] Neng Huang (U. of Chicago), Wednesday 2/9, 12:30pm-1:30pm, JCL 390.

[Antares Chen]

************************************************************
**************************

*Date:* February 9, Wednesday
*Time: *12:30pm CT
*Location: *JCL 390

*Speaker: Neng Huang (University of Chicago)*

*Title:* *Decision Tree Complexity of String Matching*

*Zoom: *[link
<https://uchicago.zoom.us/j/92270537164?pwd=cXRxaWl2QXhWZjFBU29TbVorYy84dz09>
]

*Abstract:* 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.

*Note*: In line with current departmental guidance, lunch will not be
served at the talk.

[Theory Lunch Webpage <https://orecchia.net/event/theory-lunch/>]
[Theory Lunch Calendar
<https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America/Chicago>
]

************************************************************
**************************
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20220207/47b0037a/attachment-0001.html>