This paper is dedicated to the 60th Birthday of Michael R. Fellows

1 Introduction

2 Basics on Parameterized Algorithms and Complexity

3 Probabilistic and Harmonic Analysis Tools

4 Parameterizations of MaxSat

5 Boolean Max r-CSPs Above Average
5.1 Basic Results for Max-Lin2-AA and Max r-Lin2-AA
5.2 Max-r-Lin2-AA
5.3 Max-r-CSPs AA

6 MaxLin2-AA and MaxSat-AA

7 Ordering CSPs
7.1 2-Linear Ordering
7.2 Betweenness
7.3 3-Linear Ordering
7.4 (2,3)-Linear Ordering-AA