Parity in computing is whether the count of 1s in a binary string is even or odd, e.g. ’101′ has two 1s ⇒ even parity (to output 0 for even parity, XOR all bits like 1^0^1 .. to output 1 for this, XOR that result with 1).
The parity problem (if I understand it correctly) sounds like trying to find out the minimum amount of data samples per input length a learning algorithm ought to need to figure out that a mapping between a binary input and a single bit output is equal to computing XOR parity and not something else (e.g. whether an integer is even/odd, or if there is a pattern in wannabe-random mapping, …), and the conclusion seems to be that you need exponentially more samples for linearly longer input .. unless you can figure out from other clues that you need to calculate parity in which case you just implement parity for any input size and you don’t need any additional sample data.
(FTR: I don’t understand the math here, I am just pattern matching to the usual way this kind problems go)
I started reading, but I can’t understand what the parity problem is, in the section that ought to define it.
I guess, the parity problem is finding the set S given black-box access to the function, is it?
Parity in computing is whether the count of 1s in a binary string is even or odd, e.g. ’101′ has two 1s ⇒ even parity (to output 0 for even parity, XOR all bits like
1^0^1.. to output 1 for this, XOR that result with 1).The parity problem (if I understand it correctly) sounds like trying to find out the minimum amount of data samples per input length a learning algorithm ought to need to figure out that a mapping between a binary input and a single bit output is equal to computing XOR parity and not something else (e.g. whether an integer is even/odd, or if there is a pattern in wannabe-random mapping, …), and the conclusion seems to be that you need exponentially more samples for linearly longer input .. unless you can figure out from other clues that you need to calculate parity in which case you just implement parity for any input size and you don’t need any additional sample data.
(FTR: I don’t understand the math here, I am just pattern matching to the usual way this kind problems go)