We have numbers from $$$\ a_1, \ldots, a_n$$$, where each number is between $$$(0 \leq a_i < 2^k)$$$. We're trying to find a sequence of these numbers $$$(1 \leq i_1 < i_2 < \ldots < i_T \leq n)$$$ , where $$$T$$$ is $$$(T \geq 1)$$$ , and when we combine them using XOR $$$(a_{i_1} \oplus \ldots \oplus a_i)$$$, the result is $$$0$$$. This problem is well-known and can be solved using Gaussian Elimination technique($$$\mathcal{O}(\frac{nk^2}{w} + \frac{k^3}{w})$$$) in $$$(O(k^2))$$$ time.
But what if we want to find the smallest number of elements $$$T$$$ (still with $$$(T \geq 1.)$$$)? So far, I've only thought of a method that takes about $$$(O^*(n^k))$$$ time by trying all subsets with sizes up to $$$k$$$ and checking if their XOR sum is $$$0$$$.
Can we find a faster way, maybe something like $$$(O(\text{polylog}(n, k)))$$$? Any help would be appreciated, thank you.
You can find it in $$$O(n2^k)$$$ with dp where
dp[i][j]is the minimum positive number of numbers in the firstinumbers to get an xor ofj(or -1 if it is impossible). Transitions are $$$O(1)$$$ since you can either use or ignore an element.You can use FWHT and raise the polynomial (freq[ai]*x^ai :: for all i) to a power of T.
The first (T) that would give you a non-zero coefficient to x^0 will be the answer.
You can get (T) by binary search or multiply the polynomial by itself until you find an answer because (T) will not go higher than log(max(ai))
Not true, P^2 would always have a non-zero coefficient to x^0. It might be possible to use something similar though. O(K^2 * 2^K) should be doable somehow.
You can first find XOR basis and then do meet-in-the-middle, which gives you $$$O(nk + 2^{k/2})$$$.