Computational Complexity (10w5028)
Organizers
Paul Beame (University of Washington)
Stephen Cook (University of Toronto)
Russell Impagliazzo (University of California San Diego)
Valentine Kabanets (Simon Fraser University)
Avi Wigderson (Institute for Advanced Study)
Description
The Banff International Research Station will host the "Computational Complexity" workshop from August 1st to August 6th, 2010.
Computational complexity is a field of research whose main objective is to understand the power and limitation of efficient computation. The area was born in the 1960's, when it was realized that some problems solvable in principle on a computer may not be solvable in practice, as they may not have any efficient algorithmic solution.
Complexity theory has witnessed quite remarkable progress since its inception, with new methods developed, some questions resolved, and many more important open questions formulated. Despite this progress, many basic questions about efficient computation remain unresolved. One of the main open questions is the famous "P versus NP" problem, considered one of the most important challenges for mathematical research in the 21st century. The proposed workshop will bring together the top experts on computational complexity from around the world to examine some recent methods and tools developed in complexity theory, and propose new directions of research.
The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the US National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnología (CONACYT).
