Edit: Actually I should have been more careful. Maybe the optimal way to solve this is to approach it as a series of $k'-$XOR sum problems (Generalized birthday due to Wagner) for increasing $k'.$ And if no $k'-$XOR sum solution exists for $k'<k,$ then it is just the $k-$XOR sum problem that we have!

Original Question:

The $k-$XOR Sum problem in its zero-sum form is:

Given the list $[x_i: 1\leq i\leq n]$ with $x_i \in \mathbb{F}_2^d,$ find $k$ entries that XOR sum to $0\in \mathbb{F}_2^d.$

For $k=2,$ this is the birthday problem which can be solved with time complexity $O(n \log n)$ (and storage $O(n)$) by sorting the list, for example, and scanning looking for adjacent duplicate values. I don't care about logarithmic factors too much here, and one could argue that hash sorting would make this essentially linear.

For $k=3,$ the obvious complexity of essentially $O(n^2)$ has barely been improved (form all pairs of sums and search for the sum in the sorted list) as far as I know.

What if we have a hard instance of the zero sum XOR-knapsack. That is, we don't have a "small" $k'<k$ for which the $k'-$XOR sum has a solution. What is the complexity then?

Note that if $k\geq d+1,$ then any collection of $k$ vectors are linearly dependent so we need to restrict $k$ to be below this value. Doing this, is it known whether there is a better than $$O\left[\binom{n}{\lceil k/2\rceil}\right]$$ i.e., essentially brute force search algorithm which splits the sum into two almost equal term sums and looks for a collision?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.