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

Add to your list(s) Download to your calendar using vCal

• Gutin, B (Royal Holloway)
• Tuesday 21 June 2011, 14:00-15:00
• Seminar Room 2, Newton Institute Gatehouse.

If you have a question about this talk, please contact Mustapha Amrani.

Discrete Analysis

et $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^2log k)$ variables. Here we use Linear Algebra.

This is a very recent result, see http://arxiv.org/abs/1104.1135 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.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 2, Newton Institute Gatehouse
• bld31

Note that ex-directory lists are not shown.