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

ignougroup
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