# Solving/Optimizing a linear system in a finite field (Z/2Z)

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?

• Your problem is likely NP-hard, probably also NP-hard to approximate. But perhaps there are subexponential algorithms that give reasonable results for your dimensions. – Yuval Filmus Jan 31 '16 at 22:33
• I don't need to solve it exactly, but I'm sure I can do better than my current solution. – Nemo Jan 31 '16 at 22:54
• You might want to look into the block Lancosz algorithm for finding solutions. – Pseudonym Feb 1 '16 at 1:04
• Block lancosz algorithm - does that give poly time bounds even in case of sparse number of entries? – user3483902 Mar 21 '18 at 19:42

(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,