BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Applications of Discrete Harmonic Analysis\, Probabilistic Method 
 and Linear Algebra in Fixed-Parameter Tractability and Kernelization - Gut
 in\, B (Royal Holloway)
DTSTART:20110621T130000Z
DTEND:20110621T140000Z
UID:TALK31799@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:et $P$ be a decision problem (answers are yes or no). A parame
 terized\nproblem $Pi$ is a set of pairs $(x\,k)$ where $x$ is an instance 
 of $P$ and\n$k$ (usually an integer) is the parameter. One example is the 
 $k$-Vertex\nCover problem\, where for a given graph $G$ we are to decide w
 hether there is\na set of $k$ vertices covering all edges of $G.$\n\nA ker
 nelization of $Pi$ is a polynomial time algorithm 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 the s
 ize of\n$x'$. For example\, there is a kernelization of $k$-Vertex Cover r
 educing each\npair ($G\,k$) into ($H\,k$)\, where $H$ has at most $2k$ ver
 tices and $k^2$\nedges.\n\nA parameterized problem is fixed-parameter trac
 table if it can be solved in\ntime $O(f(k)|x|^{O(1)})$ for some function $
 f$ in $k$. It is well-known that\na parameterized problem is fixed-paramet
 er tractable iff it is decidable and\nadmits a kernelization.\n\nWe'll dis
 cuss applications of Discrete Harmonic Analysis\, Probabilistic\nMethod an
 d Linear Algebra to some parameterized problems. We'll mainly\ndiscuss Max
 Lin2-AA: given a system of linear equations over GF(2) in which\neach equa
 tion has a positive integral weight\, decide whether there is an\nassignme
 nt to the variables that satisfies equations of total weight at least\n$W/
 2+k\,$ where $W$ is the total weight of all equations of the system.\nSolv
 ing an open question of Mahajan\, Raman and Sikdar (2006\,2009)\, we'll sh
 ow\nthat MaxLin2-AA is fixed-parameter 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://arxiv.org/abs/1104.1135\nIt is still unkn
 own whether MaxLin2-AA admits a kernel with a polynomial\nnumber of equati
 ons (rather than variables)\, but we can prove that such a\nkernel exists 
 for a number of special cases of MaxLin2-AA. Here we apply\nProbabilistic 
 Method and Discrete Harmonic Analysis. In particular\, we use\nthe well-kn
 own (4\,2)-Hypercontractive Inequality as well as its new version.\n
LOCATION:Seminar Room 2\, Newton Institute Gatehouse
END:VEVENT
END:VCALENDAR