1
I have system of linear equations $f_1, \ldots, f_m$ over binary variables $x_1,\ldots,x_n$
where $m$ is much larger than $n$. We know if all equations are correct, we can find solution easily using Gaussian elimination. Among those $m$ equations, 90% equations are correct.
For the remaining 10%,...