DiscoverDiscrete AnalysisApplications 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 Kernelization

Applications of Discrete Harmonic Analysis, Probabilistic Method and Linear Algebra in Fixed-Parameter Tractability and Kernelization

Update: 2011-06-24
Share

Description

Let P be a decision problem (answers are yes or no). A parameterized problem Π 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 Π is a polynomial time algorithm that maps an instance (x,k)∈Π to an instance (x′,k′)∈Π (kernel) such that (i) (x,k) is a yes-instance iff (x′,k′) is a yes-instance, (ii) k′≤h(k) and |x′|≤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 k2 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(k2logk) 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.
Comments 
In Channel
Positive projections

Positive projections

2011-07-0759:13

loading
00:00
00:00
1.0x

0.5x

0.8x

1.0x

1.25x

1.5x

2.0x

3.0x

Sleep Timer

Off

End of Episode

5 Minutes

10 Minutes

15 Minutes

30 Minutes

45 Minutes

60 Minutes

120 Minutes

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 Kernelization

Steve Greenham