Algorithmic Analysis and Complexity Lower Bounds

Rahul Santhanam ( University of Edinburgh )

Algorithmists strive to design and analyse efficient algorithms for natural computational problems. Complexity theorists, on the other hand, seek to understand the limitations of algorithms, namely to show or give evidence that certain computational problems cannot be solved within a bounded set of resources. These endeavours seem opposed - the first involves finding constructive techniques, the second involves proving impossibility results. However, in recent years, there have been indications of deep and surprising connections between the two endeavours.

I will discuss these connections in the context of algorithms for the NP-hard Boolean Satisfiability problem and its variants. I will survey recent work which uses complexity-theoretic ideas to design and analyze improved algorithms, and on occasion exploits the improved algorithms to get new complexity consequences. In a more speculative vein, I will discuss the possible relevance of complexity-theoretic ideas in broader algorithmic domains, such as algorithms for graph problems.