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

Link to this comparison view

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
 +==== 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.