Subblock reuse - Githubissues

andrebreis / cascade-study

4 stars 3 forks source link

Subblock reuse #26

Closed andrebreis closed 5 years ago

andrebreis commented 5 years ago

It should be an optimization to keep track of the used subblocks and their known or inferred values to skip unnecessary communication rounds (asking for known parities)

andrebreis commented 5 years ago

Solution - make all computation on knowledge input.

Have a dictionary of block -> value
On block input, try every possible XOR combination with every existing known block and save the new knowledge (recursively, every "block save" should do this process again)
To retrieve just lookup the dictionary. Get the bit value or None if it does not exist

andrebreis commented 5 years ago

More scalable approach - Use a parity check matrix.

Each row in the matrix is (c_1 c_2 c_3 ... c_n | p_l) and p_l = c_1*b_1 + c_2*b_2+....+c_n*b_n
To check if a parity is known check if the vector is in the span of the matrix (can be computed by a linear combination of the matrix's rows)
If it's not - add it to the matrix

andrebreis commented 5 years ago

Closed by #34