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

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

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 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$...

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$ ...

Johne, what is your problem? You're trying to argue about things no one ever claimed. No one said that the parity lower bound poses some fundamental limit to computing XOR with circuits other than ...

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

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

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

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