Computational Complexity (13w5010)


(University of Washington)

(University of California San Diego)

Valentine Kabanets (Simon Fraser University)

(University of Toronto)

(Institute for Advanced Study)


The Banff International Research Station will host the "Computational Complexity" workshop from July 7th to July 12th, 2013.

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

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 U.S. National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnología (CONACYT).