Given an array of $$$n$$$ numbers $$${a_i}$$$ with $$$a_i \lt 2^{23}$$$, find the smallest $$$k$$$ such that there exist indices $$$0 \leq i_1 \lt \dots \lt i_k \leq n - 1$$$ for which $$$a_{i_1} \oplus \dots \oplus a_{i_k} = 0$$$.
I thought this was a well-known problem, but I couldn't find it. Maybe it can be solvable using Xor-Basis?(Or smth like meet-in-the-middle)
My dumbest solution is: If $$$\binom{n}{4} \gt 2^{23}$$$, then it is clear that an answer exists and has length $$$\leq 8$$$. It can be found in some sense by taking the $$$l$$$-th power of the Xor-Convolution(with $$$l \leq 8$$$)
Otherwise, $$$n \lt 120$$$, and we can write a solution in $$$O(n 2^m)$$$ using naive dp(Here $$$m = 23$$$)
I think there is definitely a solution that is much simpler and better than this.
You can add a 0 to the set and do the xor power. You can do binary search by adding the 0 to the set, so the solution is O(K * 2^K * logK). You can also not do the inverse, instead do the inverse just for the sets of xor 0. This results in O(2^K * (K + logK)) solution. Just gotta live with having the chance of the number of sets be multiple of the mod used fucking shit up. It's possible to not have to worry about this with the previous O(K * 2^K * logK) solution.
Your solution seems better to me though. Smart thinking for the N choose 4 thing.
sorry, I would like to understand your solution, could you elaborate on "You can add a 0 to the set and do the xor power. You can do binary search by adding the 0 to the set, so the solution is O(K * 2^K * logK)"? I don't understand what it means, how do you binary search?
Your solution when the answer is small uses xor convolution, right? Add 0 to the set and use the same xor convolution solution. Since 0 is in the set, once a number is obtainable it's always obtainable, so you can do binary search to replace a factor of bits with a factor of log(bits).
This is k-subset sum on $$$\mathbb{F}_2^{23}$$$ (or alternatively finding the smallest linearly dependent subset since the field is $$$\mathbb{F}_2$$$). There is a paper on these and similar problems here. I don't have the time to read it thoroughly so I don't know if it's relevant to practically solving this problem.
Edit: in the specific case of vectors over $$$\mathbb{F}_2$$$ it is also known as "Maximum-Likelihood Decoding"/"Weight Distribution", it is also discussed here and here.
EDIT: Nevermind, I just realized the k-subsets don't have a proper basis and so can't be handled in this way.