# Differences

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

 — en:group:seminars:20090625 [2016/06/23 11:26] (current) 2009/06/19 13:52 mahdi created 2009/06/19 13:52 mahdi created 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. 