EPFL

Algo+LMA

This shows you the differences between two versions of the page.

en:group:seminars:20090625 [2016/06/23 11:26] |
en:group:seminars:20090625 [2016/06/23 11:26] (current) |
||
---|---|---|---|

Line 1: | Line 1: | ||

+ | ---- dataentry seminar ---- | ||

+ | date_dt : 2009-06-25 | ||

+ | title : The extended k-tree algorithm | ||

+ | speaker : Lorenz Minder | ||

+ | affiliation : EECS, UC Berkeley | ||

+ | time : 10h15-11h15 | ||

+ | room : BC229 | ||

+ | table : seminars | ||

+ | =================== | ||

+ | template:datatemplates:seminar | ||

+ | ----------------------- | ||

+ | |||

+ | |||

+ | ==== abstract ==== | ||

+ | Given k = 2^q random lists of n-bit vectors, L_1, ..., L_k, each list | ||

+ | containing m vectors, we wish to find an XOR x_1 + ... + x_k (with x_i | ||

+ | in L_i) equalling to zero. This problem has numerous applications for | ||

+ | example in coding theory and in cryptography. The problem is likely to | ||

+ | have a solution if m > 2^{n/k}, and the classical time/space tradeoff | ||

+ | solves it in time O(2^{n/2} poly(log(m), n, k)). However, if the list | ||

+ | size m is much larger, specifically if m >= 2^{n / (q + 1)}, the k-tree | ||

+ | algorithm due to Wagner finds a solution with high probability in | ||

+ | (essentially linear) time O(2^{n/(q + 1)} poly(log(m), n, k)). | ||

+ | |||

+ | In this talk, we give a natural algorithm that specializes to the usual | ||

+ | time/space tradeoff if m = 2^{n/k}, and to the unmodified k-tree | ||

+ | algorithm if m = 2^{n/(q + 1)}, but is faster than its competitors for | ||

+ | intermediate values of m. We will also show that this extended k-tree | ||

+ | algorithm has a reasonably low failure probability. Finally, we will | ||

+ | discuss a generalization of this algorithm to the case where the base | ||

+ | field is not F_2, but an arbitrary finite field. |