BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Isaac Newton Institute Seminar Series
SUMMARY:Applications of Discrete Harmonic Analysis\, Proba
bilistic Method and Linear Algebra in Fixed-Parame
ter Tractability and Kernelization - Gutin\, B (Ro
yal Holloway)
DTSTART;TZID=Europe/London:20110621T140000
DTEND;TZID=Europe/London:20110621T150000
UID:TALK31799AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/31799
DESCRIPTION:et $P$ be a decision problem (answers are yes or n
o). A parameterized\nproblem $Pi$ is a set of pair
s $(x\,k)$ where $x$ is an instance of $P$ and\n$k
$ (usually an integer) is the parameter. One examp
le is the $k$-Vertex\nCover problem\, where for a
given graph $G$ we are to decide whether there is\
na set of $k$ vertices covering all edges of $G.$\
n\nA kernelization of $Pi$ is a polynomial time al
gorithm that maps an instance\n$(x\,k)in Pi$ to an
instance $(x'\,k')in Pi$ (kernel) such that (i) $
(x\,k)$\nis a yes-instance iff $(x'\,k')$ is a yes
-instance\, (ii) $k'leq h(k)$ and\n$|x'|leq g(k)$
for some functions $h$ and $g$\, where $|x'|$ is t
he size of\n$x'$. For example\, there is a kerneli
zation of $k$-Vertex Cover reducing each\npair ($G
\,k$) into ($H\,k$)\, where $H$ has at most $2k$ v
ertices and $k^2$\nedges.\n\nA parameterized probl
em is fixed-parameter tractable if it can be solve
d in\ntime $O(f(k)|x|^{O(1)})$ for some function $
f$ in $k$. It is well-known that\na parameterized
problem is fixed-parameter tractable iff it is dec
idable and\nadmits a kernelization.\n\nWe'll discu
ss applications of Discrete Harmonic Analysis\, Pr
obabilistic\nMethod and Linear Algebra to some par
ameterized problems. We'll mainly\ndiscuss MaxLin2
-AA: given a system of linear equations over GF(2)
in which\neach equation has a positive integral w
eight\, decide whether there is an\nassignment to
the variables that satisfies equations of total we
ight at least\n$W/2+k\,$ where $W$ is the total we
ight of all equations of the system.\nSolving an o
pen question of Mahajan\, Raman and Sikdar (2006\,
2009)\, we'll show\nthat MaxLin2-AA is fixed-param
eter tractable and admits a kernel with at most\n$
O(k^2log k)$ variables. Here we use Linear Algebra
.\n\nThis is a very recent result\, see http://arx
iv.org/abs/1104.1135\nIt is still unknown whether
MaxLin2-AA admits a kernel with a polynomial\nnumb
er of equations (rather than variables)\, but we c
an prove that such a\nkernel exists for a number o
f special cases of MaxLin2-AA. Here we apply\nProb
abilistic Method and Discrete Harmonic Analysis. I
n particular\, we use\nthe well-known (4\,2)-Hyper
contractive Inequality as well as its new version.
\n
LOCATION:Seminar Room 2\, Newton Institute Gatehouse
CONTACT:Mustapha Amrani
END:VEVENT
END:VCALENDAR