The Computer Science Colloquium

Edward Hirsch and Alexander Kulikov
(Russian Academy of Sciences, St. Petersburg)

"Efficient Approaches to Proving Upper Bounds for NP-hard Problems"

In the talk we will discuss interesting approaches to designing efficient exact algorithms for NP-hard problems. These include splitting algorithms and automated analysis of their running time, local search algorithms, and combined complexity measures for estimating the running time of recursive algorithms. We will give the main ideas of the proofs of currently best known upper bounds for well-known NP-hard problems such as satisfiability, maximum satisfiability, maximum cut, maximum independent set. We will also formulate several open problems in this area.

The Colloquium is supported by generous contributions from the Bloomberg, Information Builders, Inc. and Netlogic, Inc.