david
• Member for 11 years, 1 month
• Last seen more than a week ago

The Sieve of Erathosthenes to find all primes up to $n$ is perhaps the best-known example of an $O(n \log \log n)$ algorithm: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes Its running time is $... View answer Accepted answer 5 votes The answer to both questions is yes. The matrix$A B - C$gives rise to a linear application over your field$\mathbb F$, which is a multivariate polynomial of total degree$d=1$. By the Schwartz-... View answer Accepted answer 2 votes It's not "obtained", but rather the bound the authors want on$\mathrm{Prob}[|u_1|\ge s]$. The Chernoff inequality says how large$s$needs to be in order to guarantee the desired upper bound. As they ... View answer Accepted answer 5 votes Here is the sketch of a proof I know. Let us draw$s = \max\left(\frac{4M}{\varepsilon},\frac{c}{\varepsilon} \log\frac{1}{\delta}\right)$samples from the unkown distribution (where$c$isconstant), ... View answer Accepted answer 6 votes The paper "Random low-degree polynomials are hard to approximate" by Ben-Eliezer, Hod, and Lovett answers your question. They show strong bounds on the correlation of random polynomials of degree$d$... View answer Accepted answer 14 votes Mergesort satisfies all three requirements (when merging is performed in place). See Pardo, L.T., "Stable sorting and merging with optimal space and time bounds", SIAM J. Comput. 6 (1977), ... View answer 8 votes There seems to be a typo; I assume you mean to find$u \in \{0,1\}^n$which is not the sum of$(\log n)^{O(1)}$vectors among$v_1,\dots, v_m$(not$n$). It's not clear to me if any constant in$...

Intuitively, the theorem says that a line is not a finite union of points, a plane is not a finite union of lines, etc. The simplest proof is to observe, for example, that a finite union of lines has ...