29 votes

When does randomization speed up algorithms and it "shouldn't"?

I don’t know whether randomization “should” or “shouldn’t” help, however, integer primality testing can be done in time $\tilde O(n^2)$ using randomized Miller–Rabin, while as far as I know, the best ...
20 votes

Examples of successful derandomization from BPP to P

$SL = L$. $RL$ stands for randomized logspace and $RL=L$ is a smaller version of the problem $RP=P$. A major stepping stone was the proof of Reingold in '04 ("Undirected S-T Connectivity in Logspace")...
  • 7,090
19 votes

When does randomization speed up algorithms and it "shouldn't"?

An old example is volume computation. Given a polytope described by a membership oracle, there's a randomized algorithm running in polynomial time to estimate its volume to a $1+\epsilon$ factor, but ...
18 votes

Which randomized algorithms have exponentially small error probability?

Impagliazzo and Zuckerman proved (FOCS'89, see here) that if a BPP algorithm uses $r$ random bits to achieve a correctness probability of at least 2/3, then, applying random walks on expander graphs, ...
18 votes
Accepted

Generalizing the "median trick" to higher dimensions?

What you're looking for is almost the same a robust central tendency: a way of reducing a cloud of data points to a single point, such that if many of the data points are close to some "ground truth" ...
16 votes

Examples of successful derandomization from BPP to P

There is basically only one interesting problem in BPP not known to be in P: Polynomial Identity Testing, given an algebraic circuit is the polynomial it generates identically zero. Impagliazzo and ...
15 votes
Accepted

What is the proof of this nonstandard version of Azuma's inequality?

I can't find a reference, so I'll just sketch the proof here. Theorem. Let $X_1, \cdots, X_n$ be real random variables. Let $a_1, \cdots, a_n, b_1, \cdots, b_n$ be constants. Suppose that, for all $i ...
  • 2,783
14 votes

Generalizing the "median trick" to higher dimensions?

This is a neat question and I've thought about it before. Here's what we came up with: You run your algorithm $n$ times to get outputs $x_1, \cdots, x_n \in \mathbb{R}^d$ and you know what with high ...
  • 2,783
13 votes

Examples of successful derandomization from BPP to P

Besides polynomial identity testing, one other very important problem known to be in BPP but not in P is approximating the permanent of a non-negative matrix or even the number of perfect matchings in ...
13 votes

Can true randomness (provably) be replaced with Kolmogorov randomness for RP?

I think the question being asked here is roughly "is there a sense in which we can replace the sequence of random bits in an algorithm with bits drawn deterministically from an appropriately long ...
12 votes

Johnson and Lindenstrauss lemma for hamming space

Consider the $n$ vectors $e_1,\ldots,e_n$ of weight $1$, and the zero vector $e_0$. The Hamming distance between $e_0$ to any $e_i$ is $1$. Let $\varphi$ be a map into a Hamming cube of dimension $m$, ...
  • 14.1k
11 votes

When does randomization speed up algorithms and it "shouldn't"?

i dont know if this answers your question (or at least part of it). But for real-world examples where randomisation can provide a speed-up is in optimisation problems and the relation to the No Free ...
  • 571
11 votes
Accepted

Is there a randomized complexity class analogous to $\mathsf{P/Poly}$?

Suppose you have a circuit which takes as input an advice string and a random string. (So this circuit would be in $BPP/Poly$ or something like that.) You can convert this into a purely deterministic ...
  • 3,468
10 votes
Accepted

Randomness and small circuits complexity classes

Most nonuniform complexity classes—$\mathrm{NC^1}$ included—are closed under the $\mathrm{BP}$ operator by the same argument as $\mathrm{BPP\subseteq P/poly}$: using the Chernoff–Hoeffding bound, the ...
10 votes

Can we fast generate perfectly uniformly mod 3 or solve NP problem?

I will use numbers starting from $0$ rather than $1$, as I find it much more natural. Here are two classes of problems we can solve in this way: Functions in TFNP (i.e., single-valued total NP search ...
9 votes
Accepted

Exact formula for the number of spanning trees of a rectangle

According to https://www.cse.ust.hk/~golin/pubs/ANALCO_05.pdf there is no closed-form formula known. According to http://arxiv.org/pdf/cond-mat/0004341v1.pdf the number is asymptotic (for $n$ and $m$ ...
9 votes
Accepted

Is there a linear time algorithm for integer multiplication verification?

There is a linear time randomized algorithm, that is of complexity $O(\log n)$: Cf M. Kaminski, A note on probabilistically verifying integer and polynomial products, J. ACM 36(1), pp. 142–149, Jan. ...
  • 4,400
8 votes

What is the minimum over all distributions of unit vectors of the variance of the dot product of the vectors?

I will present an equivalent but simpler-looking formulation of the problem, and show a lower bound of (n/k − 1) / (n−1). I also show a connection to an open problem in quantum information. [Edit in ...
  • 16.3k
8 votes

Randomized Polynomial Hierarchy?

Clearly, $\mathrm{RPH}\subseteq\mathrm{BPP}$. On the other hand, $\mathrm{BPP}=\mathrm{ZPP^{promiseRP}}$ (Buhrman&Fortnow, pdf), so the only way the hierarchy didn’t collapse to (at most) the ...
8 votes
Accepted

Finding a positive point for a collection of polynomials

Yes, your problem is NP-hard, by reduction from THREE-SATISFIABILITY. THREE-SATISFIABILITY: Instance: Boolean variables $u_1,\ldots,u_n$; clauses $c_1,\ldots,c_m$ of length three over the $u_i$ ...
  • 5,732
8 votes
Accepted

Random sampling data structure with removal

Copying my comment on that from here: There exist published algorithms that support sampling from discrete probability distributions in O(1) time, AND modifying the distribution in O(1) time per ...
  • 8,461
8 votes

List of quantum-inspired algorithms

There's also a recent work on low-rank semidefinite programming that, though not based directly on a quantum algorithm, still uses the same quantum-inspired techniques.
  • 81
8 votes
Accepted

Randomized algorithms not based on Schwartz-Zippel

Here is a natural problem known to be in $\mathsf{BPP}$ but not $\mathsf{RP} \cup \mathsf{coRP}$, Problem 2.6 of [1]: Given a prime $p$, integers $N$ and $d$, and a list $A$ of invertible $d \times d$ ...
7 votes

Generalizing the "median trick" to higher dimensions?

There is a notion of the median of a set of points in high-dimensions and general norms which is known under various names. It is just the point that minimizes the sum of distances to all the points ...
  • 881
7 votes

Can we fast generate perfectly uniformly mod 3 or solve NP problem?

If you could perfectly generate mod $3$ OR solve SAT (or any other NP-complete problem, for that matter) then $NP = coNP$. In particular, consider the perfect generator / solver when given a SAT ...
  • 3,236
7 votes

Randomized algorithms not based on Schwartz-Zippel

This is a search problem rather than a decision problem: factorization of polynomials over finite fields can be done in randomized polynomial time (TFZPP) using the Cantor–Zassenhaus algorithm, but no ...
6 votes
Accepted

The relationship between degree of vertex and size of dominating set

If all vertices have degree at least $d$ then there is always a dominating set of size $\frac{n \ln n}{d} + 1$. Pick a random set $S$ of size $\frac{n \ln n}{d}$. For a particular vertex $v$, the ...
  • 3,236
6 votes
Accepted

Can we fast generate perfectly uniformly mod 3 or solve NP problem?

As a followup to domotorp’s answer, I believe we can solve NP search problems satisfying one the following restrictions: the number of solutions is known, and not divisible by $3$; or, the number of ...
6 votes
Accepted

Uniform derandomisation of circuit complexity classes

The class uniform-RNC has been studied a lot. It is an open problem whether uniform-RNC = uniform-NC. Uniform-(R)NC correspond to (randomized) PRAMs with polynomially many processors and ...
6 votes
Accepted

List of quantum-inspired algorithms

As claimed by Leslie G. Valiant in a seminal paper 1 of his, Holographic algorithms are inspired by the quantum computational model. However, they are executable on classical computers and do not ...

Only top scored, non community-wiki answers of a minimum length are eligible