[Solved]: Solving/Optimizing a linear system in a finite field (Z/2Z)

Problem Detail: 

I'm trying to solve the following optimization problem.

A is a rectangular matrix with coefficients in the finite field Z/2Z (size less than 1000 X 1000). I have a system of the form A.X = Y (X and Y are vectors). And I'm looking for X such that the Hamming weight of Y is maximal.

In the best case, there would be a solution with Y_i = 1 for all i, and I would find it using the Gauss algorithm. But I know it's not the case.

So far, I haven't found a better algorithm than a random/greedy local search, but I'm sure I can use some maths to get a better solution. I've considered running a Gauss algorithm starting with B = (1,...,1) and somehow backtrack when a run into a contradiction (and switch the b_i that prevent me to get a solution). Could matrix factorization help somehow?

Asked By : Nemo

Answered By : Ricky Demer

(Note that a random assignment has probability at least 1/(1+$\hspace{.03 in}$(size($\hspace{.03 in}$Y$\hspace{.03 in}$)))
of making at least 1/2 of Y's entries equal 1. ​ That can be derandomized
by sequentially setting each variable to [something that forces at least
as many of Y's entries to 1 as it forces to 0, with ties broken arbitrarily].)


By this paper's proof of Theorem 5.6, for all real
numbers $\epsilon$, if ​ $0 < \epsilon$ ​ then the promise problem

Input: ​ instance of your problem in which each row of A has exactly 4 ones
must output YES if: ​ ​ ​ there is an assignment which makes more than 1-$\hspace{.03 in}\epsilon$ of Y's entries equal 1
must output NO if: ​ ​ ​ ​ for every assignment, less than ​ (1/2)$\hspace{.03 in}$+$\hspace{.03 in}\epsilon$ ​ of Y's entries equal 1

is NP-hard.


When parameterized by the number of zeros in Y, your problem is obviously in W$[\hspace{-0.02 in}$P$]$O,
but I don't know anything else about your problem's parameterized complexity.

This paper gives a possible try for your problem,
although it looks like it's just a student's "3rd Year Project Report".

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52534

3.2K people like this

 Download Related Notes/Documents