Investigate "false positive herding" #3
Description
Let u be a random element of U \ R. Heuristically, each bit of h(u) · X is uniformly random. The element u is a false positive if all of the bits of h(u) · X are equal to 0.
False positive herding is a strategy for skewing the distribution of the bits of h(u) · X such that false positives are more rare.
Here's how it works: Suppose we want the final X to have k columns. We'll solve H · X̂ = 0|R| x (k+C) for some small constant C. When we're building the exact filter, we'll assign a score to each column of X̂. We'll then obtain X by deleting the C columns of X̂ that have the worst score.
There are many possible ways to score the columns of X̂. One example: let T be the matrix with rows given by h(u) for u in U \ R.
To compute the score of column i, compute T · X̂ over GF(2). Sum down columns as integers.