{"663664":{"#nid":"663664","#data":{"type":"event","title":"ARC Colloquium: Viswanath Nagarajan (University of Michigan) ","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EViswanath Nagarajan (University of Michigan)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EApril 3, 2023\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EKlaus 1116 - 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle\u003C\/strong\u003E: Stochastic Score Classification and Halfspace Intersection\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\n\u003Cstrong\u003EAbstract\u003C\/strong\u003E: In sequential testing, we have a complex system with several components, each of which is \u0022working\u0022 or \u0022failed\u0022 with some independent probability. We are interested in evaluating the system status, which is a function of the statuses of its components. The goal is to design a policy that minimizes the expected cost of testing. Prior work has mainly focused on simple functions like k-of-n and halfspaces. We consider more general \u0022score classification\u0022 functions, and provide the first constant-factor approximation algorithm. Our result improves over a previous logarithmic approximation ratio. Moreover, our policy is non adaptive: it just involves performing tests in an a-priori fixed order. Finally, in computational experiments on random instances, we observe that the cost of our algorithm is typically within 50% of an information-theoretic lower bound.\u0026nbsp;\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E---\u003C\/p\u003E\r\n\r\n\u003Cp\u003E---------------------------------------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/viswa.engin.umich.edu\/\u0022\u003ESpeaker\u0027s Webpage\u003C\/a\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003Cem\u003E and \u003Ca href=\u0022http:\/\/arc.gatech.edu\/node\/121\u0022\u003Ehttp:\/\/arc.gatech.edu\/node\/121\u003C\/a\u003E \u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":"","format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003ETitle: Stochastic Score Classification and Halfspace Intersection\u003C\/p\u003E\r\n","format":"limited_html"}],"field_summary_sentence":[{"value":"Title: Stochastic Score Classification and Halfspace Intersection: Klaus 1116 at 11:00 AM"}],"uid":"35702","created_gmt":"2022-12-06 18:23:02","changed_gmt":"2023-03-31 15:45:29","author":"mb121","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2023-04-03T11:00:00-04:00","event_time_end":"2023-04-03T12:00:00-04:00","event_time_end_last":"2023-04-03T12:00:00-04:00","gmt_time_start":"2023-04-03 15:00:00","gmt_time_end":"2023-04-03 16:00:00","gmt_time_end_last":"2023-04-03 16:00:00","rrule":null,"timezone":"America\/New_York"},"location":"Klaus 1116","extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"177814","name":"Postdoc"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}