Course Identification

The course will explore theoretical foundations for coping with computational problems that are difficult to solve on worst case instances,  but apparently easier to solve on instances that one encounters in practice. We shall discuss approaches for modeling the input generation in non-worst case scenarios (parameterized complexity, random models, semi-random models), principles for the design of algorithms in these models (the more sophisticated ones involve algebraic techniques, linear and semidefinite programming), and methods for the analysis of these algorithms (including some spectral graph theory). 

Upon successful completion of the course, the student will become familiar with current research directions that concern handling of difficult computational problems, and will acquire techniques for designing and analyzing algorithms.

The course will be based on selected chapters from the upcoming book "Beyond Worst Case Analysis of Algorithms", edited by Tim Roughgarden.