-- 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)