Re: Memory-hard proof-of-work with fast verification and tunable tradeoff resilience
given a list of binary vectors X1, X2,..XN and number k find i1,i2,..ik such that Xi1 + Xi2 +.. + Xik =0.
The non-trivial algorithm for it was developed by Wagner in 2001 and has been studied extensively since then.
Binary matrix kernel, Krylov subspaces and block Lanczos algorithm.The non-trivial algorithm for it was developed by Wagner in 2001 and has been studied extensively since then.
Did I just deprived myself one more time of possible mining profit?
EDIT: Responded too fast, overlooked that K is fixed. Well, may be first find kernel (note that block Lanczos method allows to calculate the matrix on the fly instead of storing it), then search for linear combination of nullspace vectors with Hamming weight K. Interesting puzzle.