david
  • Member for 11 years, 1 month
  • Last seen more than a week ago
Algorithms with run-time $O(n\log \log n)$
11 votes

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
Freivalds matrix multiplication with non binary random vector
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
The random densification technique-JL lemma
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
Online to batch sample complexity
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
What's the bias of random polynomials with low degree over GF(2)?
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
Optimal comparison-based stable sorting in constant space
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
Algorithmic Vector Problem
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 $...

View answer
On $n$ dimensional manifolds and lattices
Accepted answer
5 votes

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

View answer
Algorithm to sort pairs of numbers
3 votes

Let X(a, b) denote the binary variable indicating whether pair (a, b) should be swapped. Consider any couple of distinct pairs (a, b) and (c, d) and write a binary constraint on the variables X(a, b) ...

View answer
Practical consequences of $Parity \notin AC^0$
6 votes

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

View answer