{"643480":{"#nid":"643480","#data":{"type":"event","title":"ARC Colloquium: Shalev Ben-David (Univ. of Waterloo)","body":[{"value":"\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EShalev Ben-David (Univ. of Waterloo)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, April 19, 2021\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EVirtual via Bluejeans - 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle: \u003C\/strong\u003EForecasting Algorithms, Minimax Theorems, and Randomized Lower Bounds\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003EI will present a new approach to randomized lower bounds, particularly in the setting where we wish to give a fine-grained analysis of randomized algorithms that achieve small bias. The approach is as follows: instead of considering ordinary randomized algorithms which give an output in {0,1} and may err, we switch models to look at \u0026quot;forecasting\u0026quot; randomized algorithms which output a confidence in [0,1] for whether they think the answer is 1. When scored by a proper scoring rule, the performance of the best forecasting algorithm is closely related to the bias of the best (ordinary) randomized algorithm, but is more amenable to analysis.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EAs an application, I\u0026#39;ll present a new\u0026nbsp;minimax\u0026nbsp;theorem for randomized algorithms, which can be viewed as a strengthening of Yao\u0026#39;s\u0026nbsp;minimax\u0026nbsp;theorem. Yao\u0026#39;s\u0026nbsp;minimax\u0026nbsp;theorem guarantees the existence of a hard distribution for a function f such that solving f against this distribution (to a desired error level) is as hard as solving f in the worst case (to that same error level). However, the hard distribution provided by Yao\u0026#39;s theorem depends on the chosen error level. Our\u0026nbsp;minimax\u0026nbsp;theorem removes this dependence, giving a distribution which certifies the hardness of f against all bias levels at once. In recent work, we used this\u0026nbsp;minimax\u0026nbsp;theorem to give a tight composition theorem for randomized query complexity.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nBased on joint work with Eric Blais.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/cs.uwaterloo.ca\/people-profiles\/shalev-ben-david\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022http:\/\/arc.gatech.edu\/node\/121\u0022\u003Ehttp:\/\/arc.gatech.edu\/node\/121\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003EClick here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu \u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Forecasting Algorithms, Minimax Theorems, and Randomized Lower Bounds - Virtual via Bluejeans at 11:00am"}],"uid":"27544","created_gmt":"2021-01-27 15:00:58","changed_gmt":"2021-04-09 11:55:37","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2021-04-19T12:00:00-04:00","event_time_end":"2021-04-19T13:00:00-04:00","event_time_end_last":"2021-04-19T13:00:00-04:00","gmt_time_start":"2021-04-19 16:00:00","gmt_time_end":"2021-04-19 17:00:00","gmt_time_end_last":"2021-04-19 17:00:00","rrule":null,"timezone":"America\/New_York"},"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":""}}}