-- The newer FT-mollification construction of "Bounded Independence
Fools Degree-2 Theshold Functions" by Diakonikolas/Kane/Nelson
implies that Omega(1/eps^p)-wise independence fools Indyk's median
estimator (the log(1/eps)'s go away), and is also simpler. Also,
the new FT-mollification yields a simpler proof of
anticoncentration; you no longer need the complex analysis and
weird "-\int_{-\infty}^x \sin^4/y^3 dy" function of Section
A.4. (2/18/2010)
-- Recall the algorithm used the p-stable sketch of Indyk: Ax if the vector
being updated is x, where A is a k x n matrix with p-stable entries. We
set k = Theta(1/eps^2). We showed that rather than having the A_{i,j}
be i.i.d., each row need only have t-wise independent entries, and the
rows need only be pairwise independent. This naively gives an update
time of O(k*t), to evaluate each of the k different hash functions. For
Indyk's median estimator we showed t = O(1/eps^p), and we gave a
"log-cosine estimator" with t = O(log(1/eps)/loglog(1/eps)).
In fact, the update time can just be made O(k + t). Thus, the
log-cosine estimator does not improve the update time, since we already
have t = o(k) for the median estimator. The reason is due to a trick
that was recently exploited in [Kane-Nelson-Porat-Woodruff, CoRR
abs/1007.4191] which I'll explain here. Each row needs a random hash
function from a t-wise independent family mapping [n] into [q], where q
= poly(mM/eps) fits in a machine word. This can be achieved by picking
a random polynomial over F_q of degree t-1. Across rows, these
polynomials only need to be pairwise-independent. Thus, if the
polynomial corresponding to row i is P_i, we can set P_i = A*i + B,
where A, B are independent random polynomials of degree t-1 over F_q.
It's easy to check the P_i are now pairwise independent (view the
coefficient vectors of A,B as elements of the field F_{q^t}, then note
we're just evaluating a random degree-1 polynomial over this field to
get the P_i). Thus, to evaluate our k different hash functions, rather
than spending Theta(t) time for each of k rows, we just evaluate A,B
each in Theta(t) time, then spend an additional O(1) time per row for a
total of O(k + t) time. (8/4/2010)