patternMinor
Solving/Optimizing a linear system in a finite field (Z/2Z)
Viewed 0 times
linearsolvingfinitefieldsystemoptimizing
Problem
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?
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?
Solution
(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".
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".
Context
StackExchange Computer Science Q#52534, answer score: 4
Revisions (0)
No revisions yet.