| Problem-Definition. Assume you have an integer interval $I = [0,n]$ and a set $Z$ that consists of tuples $(x,s(x))$, with $x \in_R I$ and $s(x) = \text{sign}(\sin(2x\pi/p))$. Find the secret parameter $p$. |
Formulated in words, the set $Z$ contains randomly distributed integers from $I$ enriched with the information if a certain (but fixed) sinus wave travels above or below that integer (i.e. the sign value) and your goal is to find that particular sine wave.
Heuristically, $\log p$ points should be sufficient, and in the first part on this topic, i described an easy instance of this problem that indeed finds $p$ using only $\mathcal{O}(\log p)$ points. Then i showed what causes the algorithm to fail if the problem instance gets a little bit more complicated. The algorithm then fails because the solution space falls apart (this could be very well shown visually if the solution spaces are drawn on a unity disk) and keeping track all the scattered solution spaces is too inefficient.
