Presented by:

G Gutin [Royal Holloway]

Date:

Tuesday 21st June 2011 - 14:00 to 15:00

Venue:

INI Seminar Room 2

Event:

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.

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

If it doesn't, something may have gone wrong with our embedded player.

We'll get it fixed as soon as possible.