COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Applications of Discrete Harmonic Analysis, Probabilistic Method and Linear Algebra in Fixed-Parameter Tractability and Kernelization

## Applications of Discrete Harmonic Analysis, Probabilistic Method and Linear Algebra in Fixed-Parameter Tractability and KernelizationAdd to your list(s) Download to your calendar using vCal - Gutin, B (Royal Holloway)
- Tuesday 21 June 2011, 14:00-15:00
- Seminar Room 2, Newton Institute Gatehouse.
If you have a question about this talk, please contact Mustapha Amrani. Discrete Analysis et $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 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^2log 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. This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 2, Newton Institute Gatehouse
Note that ex-directory lists are not shown. |
## Other listsM&EM: The Medieval & Early Modern Workshop Computer Laboratory Security Group meeting presentations Computer Laboratory Computer Architecture Group Meeting## Other talksDesigning Active Macroscopic Heat Engines Magnetic van der Waals Materials: Potentials and Applications “This object has been temporarily removed” A novel aspect of Macrophage biology: learning from the great opportunist HIV-1 CANCELLED in solidarity with strike action: Permanent Sovereignty over Natural Resources and the Unsettling of Mainstream Narratives of International Legal History The power of parenting support |