Anders Yeo
Simultaneously Satisfying Linear Equations Over F_2: Parameterized Above Average
| DATE: | Friday, September 2, 2011 |
ABSTRACT
In this talk we will mainly be considering the parameterized problem MaxLin2-AA. In MaxLin2-AA, we are given a system of variables x_1,... ,x_n and equations of the form x_{i_1}*x_{i_2}*... *x_{i_r} = b, where {x_{i_1},x_{i_2},...,x_{i_r}} is a subset of {1,2,...,n} and all x_i and b belong to {-1, 1}. Furthermore each equation has a positive integral weight, and we want to decide whether it is possible to simultaneously satisfy equations of total weight at least W/2+k, where W is the total weight of all equations and k is the parameter (if k=0, the possibility is assured).
In this talk we begin by (briefly) explaining what it means to parameterize a problem above average and why this seems a natural parameterization. We will motivate why MaxLin2-AA is of interest and outline how to obtain a kernel with at most O(k^2 log k) variables, which solves an open problem of Mahajan et al. (2006). Finally we will mention a number of open problems and conjectures.
Given at WorKer 2011 – The Third Workshop on Kernelization (slides are linked there).
