In the Max Acyclic Subdigraph problem we are given a digraph $D$ and ask whether $D$ contains an acyclic subdigraph with at least $k$ arcs. The problem is NP-complete and it is easy to see that the problem is fixed-parameter tractable, i.e., there is an algorithm of running time $f(k)n$ for solving the problem, where $f$ is a computable function of $k$ only and $n=|V(D)|$. The last result follows from the fact that the average number of arcs in an acyclic subdigraph of $D$ is $m/2$, where $m$ is the number of arcs in $D$. Thus, it is natural to ask another question: does $D$ have an acyclic subdigraph with at least $m/2 +k$ arcs?
Mahajan, Raman and Sikdar (2006, 2009), and by Benny Chor (prior to 2006) asked whether this and other problems parameterized above the average are fixed-parameter tractable (the problems include Max $r$-SAT, Betweenness, and Max Lin). Most of there problems have been recently shown to be fixed-parameter tractable.
Methods involved in proving these results include probabilistic inequalities, harmonic analysis of real-valued
functions with boolean domain, linear algebra, and algorithmic-combinatorial arguments. Some new results obtained in this research are of potential interest for several areas of discrete mathematics and computer science. The examples include a new variant of the hypercontractive inequality and an association of Fourier expansions of real-valued functions with boolean domain with weighted systems of linear equations over $F^n_2$.
I’ll mention results obtained together with N. Alon, R. Crowston, M. Jones, E.J. Kim, M. Mnich, I.Z. Ruzsa, S. Szeider, and A. Yeo.