skip to content

Applications of Discrete Harmonic Analysis, Probabilistic Method and Linear Algebra in Fixed-Parameter Tractability and Kernelization

Tuesday 21st June 2011 - 14:00 to 15:00
INI Seminar Room 2
Let $P$ be a decision problem (answers are yes or no). A parameterized problem $\Pi$ is a set of pairs $(x,k)$ where $x$ is an instance of $P$ and $k$ (usually an integer) is the parameter. One example is the $k$-Vertex Cover problem, where for a given graph $G$ we are to decide whether there is a set of $k$ vertices covering all edges of $G.$ A kernelization of $\Pi$ is a polynomial time algorithm that maps an instance $(x,k)\in \Pi$ to an instance $(x',k')\in \Pi$ (kernel) such that (i) $(x,k)$ is a yes-instance iff $(x',k')$ is a yes-instance, (ii) $k'\leq h(k)$ and $|x'|\leq g(k)$ for some functions $h$ and $g$, where $|x'|$ is the size of $x'$. For example, there is a kernelization of $k$-Vertex Cover reducing each pair ($G,k$) into ($H,k$), where $H$ has at most $2k$ vertices and $k^2$ edges. A parameterized problem is fixed-parameter tractable if it can be solved in time $O(f(k)|x|^{O(1)})$ for some function $f$ in $k$. It is well-known that a parameterized problem is fixed-parameter tractable iff it is decidable and admits a kernelization. We'll discuss applications of Discrete Harmonic Analysis, Probabilistic Method and Linear Algebra to some parameterized problems. We'll mainly discuss MaxLin2-AA: given a system of linear equations over GF(2) in which each equation has a positive integral weight, decide whether there is an assignment to the variables that satisfies equations of total weight at least $W/2+k,$ where $W$ is the total weight of all equations of the system. Solving an open question of Mahajan, Raman and Sikdar (2006,2009), we'll show that MaxLin2-AA is fixed-parameter tractable and admits a kernel with at most $O(k^2\log k)$ variables. Here we use Linear Algebra. This is a very recent result, see It is still unknown whether MaxLin2-AA admits a kernel with a polynomial number of equations (rather than variables), but we can prove that such a kernel exists for a number of special cases of MaxLin2-AA. Here we apply Probabilistic Method and Discrete Harmonic Analysis. In particular, we use the well-known (4,2)-Hypercontractive Inequality as well as its new version.
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons