New answers tagged linear-algebra
2
You can get a square-root speed-up with a time-space tradeoff if you are working in $\mathbb{F}_2$.
The matrix $M$ is a no-instance iff there exists a non-zero vector $v$ of Hamming weight $\le k$ (i.e., with at most $k$ non-zero coordinates) such that $Mv=0$. This is equivalent to saying that there exist $t,u$ of Hamming weight $\le k/2$ such that $Mt=Mu$ (...
Top 50 recent answers are included
