An O(n log n) Algorithm for the Generalized Birthday Problem
06 February 1997
In the combinatorial version of the generalized birthday problem, w 1's and n - w 0's are randomly arranged in either a line or a cycle; k sub m is defined to be the largest number of 1's appearing within any m consecutive positions. In the binomial version, each point is independently 1 with probability p and 0 with probability of 1 - p. Current algorithms for computing Pr (k sub m