<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div class=""><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class="">This is an announcement of Xifan Yu's MS Presentation. Xifan is a student in the Bx/MS program.</div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class=""><br class=""></div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class="">Zoom details will follow.</div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class=""><br class=""></div><div class=""><font color="#000000" class=""><span style="caret-color: rgb(0, 0, 0);" class="">————————————————————————————————————————————————————————————————————</span></font></div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class=""><span class=""><br class=""></span></div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class=""><span class=""><b class="">Date:</b> Wednesday, May 26, 2021</span></div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class=""><span class=""><br class=""></span></div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class=""><span class=""><b class="">Time:</b> 10 AM, CST</span></div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class=""><span class=""><br class=""></span></div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class=""><span class=""><b class="">Location:</b> remote via Zoom</span></div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class=""><br class=""></div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class=""><b class="">M.S. Candidate:</b> Xifan Yu</div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class=""><br class=""></div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class=""><b class="">M.S. Paper Title:</b> Anomaly Detection on Connected Subgraphs via Constant-factor Approximation Algorithms for the Elevated Mean Problem</div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class=""><br class=""></div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class=""><b class="">Advisor:</b> Lorenzo Orecchia</div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class=""><br class=""></div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class=""><b class="">Committee Members:</b> Lorenzo Orecchia, Rebecca Willet, Laszlo Babai</div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class=""><br class=""></div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class=""><br class=""></div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class=""><b class="">Abstract:</b></div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class="">---------------------------------------------------------------------------------</div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class="">In this paper, we study the Elevated Mean problem and the anomaly detection problem. In the anomaly detection problem, there is a network with a certain measure of behaviors of the nodes, and the task is to distinguish whether the nodes behave as usual or an anomalous cluster exists based on observations of the nodes in the network. The anomaly detection problem has a wide range of applications such as sensor network intrusion detection and disease outbreak detection. For concreteness, we formulate the anomaly detection problem as a hypothesis testing problem, and assume the potential anomalous cluster forms a connected induced subgraph of the network.</div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class=""><br class="">The paper is structured into two parts. In the first part, we study the Elevated Mean problem, which is closely related to designing decision rules for the anomaly detection problem. We present two constant-factor approximation algorithms for the Elevated Mean problem and the k-Elevated Mean problem via black-box reductions to the Quota Prize-Collecting Steiner Tree problem and the Budget Prize-Collecting Steiner Tree problem. </div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class=""><br class="">Using the constant-factor approximations for the Elevated Mean problem and the k-Elevated Mean problem in the first part, we show a polynomial time decision rule T_EM following the generalized likelihood ratio test schema based on the scan statistics of the Elevated Mean problem in the second part. Besides being polynomial time solvable, the strength of this decision rule also lies in its generality of detecting anomalous clusters among the class of connected induced subgraphs, without assuming parameters such as the shape or the internal conductance of the anomalous cluster as the previous work did. We also prove separability results using the rule T_EM.</div><div style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);" class="">------------------------------------------------------------------------------------------</div></div><div class=""><br class=""></div><div class=""><br class=""></div><br class=""><div class="">
<div dir="auto" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div>Jessica Garza<br class="">Assistant Director of Undergraduate Studies<br class="">Department of Computer Science<br class="">The University of Chicago<br class=""><a href="https://cs.uchicago.edu/remote2020/" class="">Covid-19 Resources</a></div></div>
</div>
<br class=""></body></html>