<div dir="ltr"><div><div><div style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem"><span style="color:rgb(34,34,34);font-size:large;word-spacing:0px">******************************</span><span style="color:rgb(34,34,34);font-size:large;word-spacing:0px">******************************</span><span style="color:rgb(34,34,34);font-size:large;word-spacing:0px">**************************</span><b><br></b></font></div><div style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem"><b><br></b></font></div><div style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem"><b>Date:</b> February 9, Wednesday</font></div><div style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem"><b>Time: </b>12:30pm CT</font></div><div style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem"><b>Location: </b>JCL 390</font></div><div dir="auto" style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><b><font style="font-size:1.125rem"><br></font></b></div><div dir="auto" style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><b><font style="font-size:1.125rem">Speaker: Neng Huang (University of Chicago)</font></b></div><div dir="auto" style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font size="4"><br></font></div><b style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem">Title:</font></b><span style="background-color:rgb(248,248,248);color:rgb(29,28,29);font-family:Slack-Lato,appleLogo,sans-serif;font-size:15px;font-variant-ligatures:common-ligatures"> </span><font size="4"><b>Decision Tree Complexity of String Matching</b></font></div><div><b style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem"><br></font></b></div><div><span style="font-size:16px;word-spacing:1px;color:rgb(49,49,49)"><font style="font-size:1.125rem"><b>Zoom: </b>[<a href="https://uchicago.zoom.us/j/92270537164?pwd=cXRxaWl2QXhWZjFBU29TbVorYy84dz09" target="_blank">link</a>]</font></span></div><div><br></div><div><div dir="auto"><font style="color:rgb(49,49,49);word-spacing:1px"><b style="font-size:1.125rem">Abstract:</b><font size="4"> </font></font><font size="4">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.</font></div></div></div><div dir="auto"><font size="4"><br></font></div><div><font size="4"><b>Note</b>: </font><span style="font-size:large">In line with current departmental guidance, </span><span style="font-size:large">lunch</span><span style="font-size:large"> will not be served at the talk.<br><br>[<a href="https://orecchia.net/event/theory-lunch/" target="_blank">Theory Lunch Webpage</a>]<br>[<a href="https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America/Chicago" target="_blank">Theory Lunch Calendar</a>]</span></div><div dir="auto"><font size="4"><br></font></div><div dir="auto"><span style="font-size:large">******************************</span><span style="font-size:large">******************************</span><span style="font-size:large">**************************</span></div></div>