# Subset of numbers whose XOR has least Hamming weight

I'm given $n$ numbers (let's say of some 100 bits or so). Is there a way to find a non-empty subset xor of these $n$ numbers which has the least Hamming weight (no. of set bits) in better than $O(2^n)$ complexity? I was thinking of some trie based implementation but don't think that will work at all. Would a dynamic programming approach work by any chance? If possible, a hint would be nice!

Your problem is known as calculating the minimal distance of a (binary) linear code, and is NP-hard, as shown by Vardi. It is even NP-hard to approximate within any constant factor, as shown by Dumer, Miccancio and Sudan.

• Just making sure here - calculating the minimal distance of a (binary) linear code is finding the minimum no. of set bits in the XORs of each nonempty subset of the binary representations? – Indo Ubt May 20 '17 at 21:09
• Yes, that's the same thing. – Yuval Filmus May 20 '17 at 21:14
• Also, are there better algorithms (better than O(2^n)) used for calculating these distances? – Indo Ubt May 20 '17 at 21:19
• That's possible, but unfortunately I'm not aware of any. Now that you know what to look for, you can find out on your own. – Yuval Filmus May 20 '17 at 21:22