  For many constraint satisfaction problems, the algorithm which chooses a
random assignment achieves the best possible approximation ratio. For instance,
a simple random assignment for {\sc Max-E3-Sat} allows 7/8-approximation and
for every $\eps >0$ there is no polynomial-time ($7/8+\eps$)-approximation
unless P=NP. Another example is the {\sc Permutation CSP} of bounded arity.
Given the expected fraction $\rho$ of the constraints satisfied by a random
assignment (i.e. permutation), there is no $(\rho+\eps)$-approximation
algorithm for every $\eps >0$, assuming the Unique Games Conjecture (UGC).
  In this work, we consider the following parameterization of constraint
satisfaction problems. Given a set of $m$ constraints of constant arity, can we
satisfy at least $\rho m +k$ constraint, where $\rho$ is the expected fraction
of constraints satisfied by a random assignment? {\sc Constraint Satisfaction
Problems above Average} have been posed in different forms in the literature
\cite{Niedermeier2006,MahajanRamanSikdar09}. We present a faster parameterized
algorithm for deciding whether $m/2+k/2$ equations can be simultaneously
satisfied over ${\mathbb F}_2$. As a consequence, we obtain $O(k)$-variable
bikernels for {\sc boolean CSPs} of arity $c$ for every fixed $c$, and for {\sc
permutation CSPs} of arity 3. This implies linear bikernels for many problems
under the "above average" parameterization, such as {\sc Max-$c$-Sat}, {\sc
Set-Splitting}, {\sc Betweenness} and {\sc Max Acyclic Subgraph}. As a result,
all the parameterized problems we consider in this paper admit $2^{O(k)}$-time
algorithms.
  We also obtain non-trivial hybrid algorithms for every Max $c$-CSP: for every
instance $I$, we can either approximate $I$ beyond the random assignment
threshold in polynomial time, or we can find an optimal solution to $I$ in
subexponential time.
