Connections Between Algorithm Design and Complexity Theory

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

Complexity theory, through such concepts as NP-completeness, distinguishes between computational problems that have relatively efficient solutions and those that are intractable. Complexity theory has the potential to become a real guide for algorithm design, identifying precisely what algorithmic performance is obtainable. A fundamental model of computation is the Boolean circuit, composed of interconnected logic gates. Complexity theory studies the capabilities of Boolean circuits when limits are placed on circuit size and circuit depth.  Recently, in what seems to be a paradox, breakthroughs on lower bounds in circuit  complexity  have been derived from the discovery of remarkably efficient algorithms.  The precise time complexity of SATISFIABILITY and other NP-complete problems is now linked to progress on a variety of fundamental questions in the theory of computation, many in surprising and counter-intuitive ways. These connections involve the exact complexity of basic polynomial-time solvable problems such as matrix multiplication and triangle detection. The workshop, which will be open to the public,  will gather researchers from computational complexity and algorithm design to discuss and extend these new developments.  This workshop will foster discussions that could lead to new algorithmic ideas for basic problems (often utilizing techniques from lower bounds), as well as new circuit lower bounds (utilizing improved algorithms). Students will be encouraged to participate in the workshop.