[Colloquium] Re: [CS] Xifan Yu MS Presentation/May 26, 2021

[Laszlo Babai]

The correct date of Xifan's presentation is

  Date: TUESDAY, May 25, 2021

  Time: 1 PM, CST

    -- Laci
---------------------------------------

On Mon, 24 May 2021, Jessica Garza wrote:

> This is a reminder for Xifan Yu's MS Presentation. Xifan is a student in the Bx/MS program.
>
> Please note the updated day and time.
>
> Date: Wednesday, May 25, 2021
>
> Time: 1 PM, CST
>
> Location: remote via Zoom <https://uchicago.zoom.us/j/96293823778?pwd=VlBxRm1xQzZVb2tLc25SU3B2STE0dz09 <https://uchicago.zoom.us/j/96293823778?pwd=VlBxRm1xQzZVb2tLc25SU3B2STE0dz09>>
>
> Meeting ID: 962 9382 3778
> Passcode: 589243
>
> M.S. Candidate: Xifan Yu
>
> M.S. Paper Title: Anomaly Detection on Connected Subgraphs via Constant-factor Approximation Algorithms for the Elevated Mean Problem
>
> Advisor: Lorenzo Orecchia
>
> Committee Members: Lorenzo Orecchia, Rebecca Willet, Laszlo Babai
>
>
> Abstract:
> ---------------------------------------------------------------------------------
> 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.
>
> 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.
>
> 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.
>
>
>
> Jessica Garza
> Assistant Director of Undergraduate Studies
> Department of Computer Science
> The University of Chicago
> Covid-19 Resources <https://cs.uchicago.edu/remote2020/>
>