Personal tools
You are here: Home Graduate Study Algorithmic Analysis and Complexity Lower Bounds

Algorithmic Analysis and Complexity Lower Bounds

Recently, intriguing connections have been discovered between design and analysis of algorithms for various hard computational problems and complexity lower bounds. On the one hand, it is known from work of Williams that algorithms for Circuit-Satisfiability beating brute force search imply non-trivial circuit lower bounds, and on the other hand ideas from complexity theory have been used to design and analyze new and improved algorithms for Satisfiability and other NP-hard problems. In this project, we will seek to tighten these connections, with the goal of obtaining improved algorithms and new complexity lower bounds. Students wishing to work on this project should ideally have previous exposure to algorithms and complexity theory.

 

Potential Supervisor

Rahul Santhanam

Document Actions