{"52833":{"#nid":"52833","#data":{"type":"event","title":"CS Faculty Candidate Seminar -  Alexander Razborov","body":[{"value":"\u003Cp\u003E\u003Ca href=\u0022http:\/\/www.mi.ras.ru\/~razborov\/\u0022\u003EAlexander Razborov\u003C\/a\u003E\u003Cbr \/\u003ESteklov Mathematical Institute and IAS\u003C\/p\u003E\n\u003Cp\u003E\u0022Grand Challenges in Complexity Theory\u0022\u003Cbr \/\u003E\u003C\/p\u003E\n\u003Cp\u003EAbstract:\u00a0 Modern complexity theory is a vast, loosely defined area. Its methods and methodology can be successfully applied whenever one has a set of tasks, a class of admissible solutions, and numerical characteristics to measure the ``quality\u0027\u0027 of a solution. This talk will focus on two specific scenarios: classical computational complexity and proof complexity. The story we will tell, however, is highly representative of the methods that have been tried in the field at large, with its mixed bag of successes, setbacks, and promising directions.\u003C\/p\u003E\n\u003Cp\u003EI will try to reveal some of the tight, beautiful and unexpected connections existing between different branches of complexity theory. I will discuss the \u0022grand challenges\u0027\u0022 of the field, including \u0022P vs NP\u0022 and questions about the power of classical proof systems.\u003C\/p\u003E\n\u003Cp\u003EThis talk will assume no prior knowledge in theoretical computer science.\u003C\/p\u003E\n\u003Cp\u003EBio:\u00a0 Professor Alexander A. Razborov graduated from the Moscow State University (department for mathematics and mechanics) in 1985 and in the same year entered the graduate school of the Steklov Mathematical Institute of the Russian Academy of Sciences. He defended his PhD thesis (``On systems of equations in free groups\u0027\u0027) in 1987, and his doctoral thesis (``Lower Bounds in the Boolean Complexity\u0027\u0027) in 1991.\u003C\/p\u003E\n\u003Cp\u003EProfessor Razborov joined faculty of the Steklov Mathematical Institute in 1989 and have been working there since that. In 1999-2000 he was a Visiting\u003C\/p\u003E\n\u003Cp\u003EResearcher at the Department of Computer Science of Princeton University, and in 2000-2008 he is holding a visiting position at the Institute for Advanced Study, Princeton.\u003C\/p\u003E\n\u003Cp\u003EDuring his career, Professor Razborov worked in various areas including mathematical logic, computational complexity, proof complexity and\u003Cbr \/\u003Ecombinatorics. Among other things, his contributions include:\u003C\/p\u003E\n\u003Col\u003E\n\u003Cli\u003EThe first description of solutions of equations in a free group.\u003C\/li\u003E\n\u003Cli\u003ESolving the analogue of the P vs. NP question for a number\u003C\/li\u003E\n\u003Cli\u003Eof restricted models of computation.\u003C\/li\u003E\n\u003Cli\u003ETheory of Natural Proofs and closely related theory of feasible provability of major open problems in Complexity Theory, accompanied by many concrete lower bounds for the corresponding proof systems.\u003C\/li\u003E\n\u003Cli\u003ELower bounds in quantum communication complexity.\u003C\/li\u003E\n\u003Cli\u003EThe theory of Flag Algebras in Extremal Combinatorics.\u003C\/li\u003E\n\u003C\/ol\u003E\n\u003Cp\u003EProfessor Razborov is a member of Academia Europea (since 1993), and a corresponding member of the Russian Academy of Sciences (since 2000). He is a recipient of the Nevanlinna prize awarded by the International Mathematical Union (1990) and of the Goedel Prize (awarded jointly by EATCS and ACM, 2007).\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27154","created_gmt":"2010-02-11 15:57:56","changed_gmt":"2016-10-08 01:50:13","author":"Louise Russo","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2008-02-05T10:00:00-05:00","event_time_end":"2008-02-05T11:00:00-05:00","event_time_end_last":"2008-02-05T11:00:00-05:00","gmt_time_start":"2008-02-05 15:00:00","gmt_time_end":"2008-02-05 16:00:00","gmt_time_end_last":"2008-02-05 16:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"47223","name":"College of Computing"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"Shanita Williams","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}