### tofael1104's blog

By tofael1104, 4 weeks ago,

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.

• +11

 » 4 weeks ago, # | ← Rev. 2 →   -19 Ignore this. I misunderstood the problem.
 » 4 weeks ago, # | ← Rev. 2 →   0 I remember a problem that was something like this. You can do the multiplication of (1 + x^a_i * y) mod y^(size of base + 1), where y^i * y^j = y^(i+j) and x^i * x^j = x^(i xor j). This instantly already gives us a O(2^k * k^2) solution I think, maybe k^something higher instead of k^2. The problem had a more specific setting, iirc it was finding the number of subsets of size multiple of M (with M <= 20) that had xor 0. Perhaps someone remembers the exact problem and is able to link it, I think it's a problem from a camp that tdas participated and asked about the problem to me during upsolving, which would mean some Petrozavodsk camp or Osijek from maybe 2-3 years ago.
•  » » 4 weeks ago, # ^ |   +10
 » 4 weeks ago, # | ← Rev. 3 →   +5 According to this paper, the problem is NP-hard, so if n and k are large you're out of luck. However, you can do a bit better ($\mathcal O\left(n 2^k\right)$) with a simple DP: for each $0 \le i \le n$, $0 \le a < 2^k$, let $dp_{i,a}$ be the minimum positive number of the first $i$ elements you need to get an XOR of a. $dp_{0,a} = \infty$, $dp_{i,a_i} = 1$, and otherwise $dp_{i,a} = \min \left ( dp_{i-1,a},1+dp_{i-1,a \oplus a_i} \right )$. The answer is $dp_{n,0}$.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Ignore this. I misunderstood the problem.