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

**Gutin, G ***(Royal Holloway)*

Tuesday 21 June 2011, 14:00-15:00

Seminar Room 2, Newton Institute Gatehouse

#### Abstract

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 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.

#### Presentation

#### Video

**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.

## Comments

Start the discussion!