# Complexity of XOR-Knapsack

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' 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' 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?