{"616529":{"#nid":"616529","#data":{"type":"event","title":"SCS Recruiting Seminar: Avishay Tal","body":[{"value":"\u003Cp\u003ETITLE: Title: \u003Cem\u003ESparse Polynomial Approximations and their Applications to\u003Cbr \/\u003E\r\nQuantum Advantage, Parallel Computation, and Pseudorandomness\u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EABSTRACT:\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis talk is motivated by three seemingly unrelated questions:\u003Cbr \/\u003E\r\n1. For which tasks do quantum algorithms outperform classical computation?\u003Cbr \/\u003E\r\n2. Can parallel computing accelerate all computational tasks, or are some tasks inherently sequential?\u003Cbr \/\u003E\r\n3. Can we de-randomize every algorithm while increasing its space by at most a constant factor?\u003C\/p\u003E\r\n\r\n\u003Cp\u003EWe make progress on all three questions by exploiting a common phenomenon at the core of their analysis: in all cases, the studied computational devices can be well-approximated by sparse polynomials. As one of the results, we show that relative to an oracle, quantum algorithms can perform decision tasks that are outside the polynomial-time hierarchy (that captures P, NP, coNP and their generalizations). This settles one of the big open questions in the area of quantum complexity.\u003C\/p\u003E\r\n\r\n\u003Cp\u003ELooking forward, we conjecture that several other computational devices can be well-approximated by sparse polynomials. Proving our conjecture would resolve several big open questions in computational complexity that have remained open since the 1980s.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EBIO:\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cbr \/\u003E\r\nAvishay Tal is a Motwani Postdoctoral Research Fellow at Stanford University, hosted by Omer Reingold. Prior to that, he was a postdoctoral researcher at the Institute for Advanced Study, hosted byAvi Wigderson. He obtained his Ph.D. in 2015 from the Weizmann Institute of Science, under the guidance of Ran Raz. His research interests include complexity theory, analysis of Boolean functions, quantum computing, pseudorandomness, and learning theory.\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Sparse Polynomial Approximations and their Applications to Quantum Advantage, Parallel Computation, and Pseudorandomness"}],"uid":"34541","created_gmt":"2019-01-16 19:25:47","changed_gmt":"2019-01-16 19:27:07","author":"Tess Malone","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2019-01-22T11:00:00-05:00","event_time_end":"2019-01-22T12:00:00-05:00","event_time_end_last":"2019-01-22T12:00:00-05:00","gmt_time_start":"2019-01-22 16:00:00","gmt_time_end":"2019-01-22 17:00:00","gmt_time_end_last":"2019-01-22 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"hg_media":{"616530":{"id":"616530","type":"image","title":"Avishay Tal","body":null,"created":"1547666770","gmt_created":"2019-01-16 19:26:10","changed":"1547666770","gmt_changed":"2019-01-16 19:26:10","alt":"Avishay Tal","file":{"fid":"234663","name":"AvishayTal.jpg","image_path":"\/sites\/default\/files\/images\/AvishayTal.jpg","image_full_path":"http:\/\/www.tlwarc.hg.gatech.edu\/\/sites\/default\/files\/images\/AvishayTal.jpg","mime":"image\/jpeg","size":348301,"path_740":"http:\/\/www.tlwarc.hg.gatech.edu\/sites\/default\/files\/styles\/740xx_scale\/public\/images\/AvishayTal.jpg?itok=xNC7-pNx"}}},"media_ids":["616530"],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"}],"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":"78771","name":"Public"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003ETess Malone, Communications Officer\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022mailto:tess.malone@cc.gatech.edu\u0022\u003Etess.malone@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E\r\n","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}