28 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 ...
user avatar
22 votes
Accepted

The randomized query complexity of the conjoined trees problem

I think I have a deterministic algorithm that finds the exit in $O(n2^{n/2})$ oracle calls. First, find the labels for all the vertices of distance $n/2$ from the entrance. This takes $O(2^{n/2})$ ...
user avatar
  • 236
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")...
user avatar
  • 6,997
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 ...
user avatar
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, ...
user avatar
17 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" ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 2,743
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 ...
user avatar
  • 2,743
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 ...
user avatar
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 ...
user avatar
12 votes
Accepted

A converse to Fano's inequality ?

Consider the following reconstruction procedure $P(y)$: given $y$, output $x$ such that $\Pr[X = x \mid Y = y]$ is maximized. The probability that this procedure succeeds is $\max_x \Pr[x \mid Y = y]$....
user avatar
  • 3,698
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$, ...
user avatar
  • 14.1k
11 votes
Accepted

A flowchart for concentration bounds

Fan Chung and Linyuan Lu. Concentration inequalities and martingale inequalities: a survey available at http://projecteuclid.org/euclid.im/1175266369 or at Fan Chung Graham's web page.
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 3,458
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 ...
user avatar
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 ...
user avatar
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$ ...
user avatar
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. ...
user avatar
  • 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 ...
user avatar
  • 16.2k
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 ...
user avatar
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$ ...
user avatar
  • 5,712
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 ...
user avatar
  • 8,133
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.
user avatar
  • 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$ ...
user avatar
7 votes

Proving properties of Random Graphs

It doesn't sound hopeful in general. For example, let $P$ be the statement "all vertices have degree 0 or 1". Let $p=1/n$ and $n$ even. Then conditioned on the event of being regular, with high ...
user avatar
7 votes
Accepted

Where does randomness help when deciding algebraic geometry over $\mathbb{C}$?

For the question of when does $p=0 \Rightarrow q=0$, randomness can indeed help, as follows. First, factor $p$ (uses randomness when $p$ is given as a straight-line program; doesn't need randomness if ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 3,161

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