# Tag Info

## Hot answers tagged randomized-algorithms

28

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 known deterministic algorithms are $\tilde O(n^4)$ assuming GRH (deterministic Miller–Rabin) or $\tilde O(n^6)$ unconditionally (variants of AKS).

22

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})$ queries. Then, start from the entrance and walk $n+1$ steps to get to a node $X$ of distance $n+1$ from the entrance. We will try to reach the exit from this node....

19

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 no deterministic algorithm can come even close unconditionally. The first example of such a randomized strategy was by Dyer, Frieze and Kannan, and the ...

19

$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") that $SL = L$, where $S$ stands for "symmetric" and $SL$ is an intermediate class between $RL$ and $L$. The idea is that you can think of a randomized ...

18

Perhaps most people think that $\mathsf{RNC}\subseteq \mathsf{DSPACE(polylog)}$ (or even that $\mathsf{RNC}=\mathsf{NC}$), but I'm skeptical about this (see the second part of my answer, below). If $\mathsf{RNC}$ is indeed contained in $\mathsf{DSPACE(polylog)}$, then it is also contained in $\mathsf{NTIME(2^{polylog})}$ (more specifically, it is in $\mathsf{... 18 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, this can be improved to a correctness probability of$1-2^{-k}$, using$O(r+k)$random bits. (Note: while the authors use the specific constant 2/3 in the ... 17 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" but the rest of them are arbitrarily far away, then your output will also be close to the ground truth. The "breakdown point" of such a method is the fraction ... 16 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 Kabanets show that PIT in P would imply some circuit lower bounds. So circuit lower bounds are the only reason (but a pretty good one) that we believe P = BPP. 14 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 probability a large fraction of$x_i$s fall into some good set$G$. You don't know what$G$is, just that it is convex. The good news is that there is a way to ... 14 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 \in \{1,\cdots,n\}$and all$(x_1,\cdots,x_{i-1})$in the support of$(X_1, \cdots, X_{i-1})$, we have$\mathbb{E}[X_i | X_1=x_1, \cdots, X_{i-1}=x_{i-1}] \...

13

First, observe that if $\mathsf{BPP} \subseteq \mathsf{ZPTIME}[2^{n^{c}}]$ for some constant $c$, then $\mathsf{BPP} \neq \mathsf{NEXP}$. (Proof by nondeterministic time hierarchy.) So proving such an inclusion would be significant, not just because it's an improved simulation but also would yield the first progress on randomized time lower bounds in decades....

13

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 a graph. There is a randomized poly-time algorithm to approximate these numbers within a (1+eps) factor, whereas the best deterministic algorithms achieve only ...

13

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 Kolmogorov random string?" This is at least the question I will attempt to answer! (The short answer is "Yes, but only if you amplify the error probability first") ...

12

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]$. This is also $2^{-H_\infty(X | Y = y)}$, where $H_\infty(X \mid Y = y)$ is the min-entropy of the random variable $X$ conditioned on $Y = y$. We know that $H_\... 12 There isn't really a single formalization of the kind of thing you are asking. There are many, many aspects to truth, trust, lies, and fallible reasoning, and this leads to an enormous variety of logical formalisms, each handling different aspects of this problem. If you want to account for uncertainty about your hypotheses, the traditional route is via ... 12 Probably the simplest approach is to perturb the edge weights symbolically rather than numerically. Intuitively, you'd like to reassign the weight of each edge as $$\tilde{w}(e) = w(e) + \varepsilon \cdot w'(e)$$ where$w(e)$is the original edge weight,$w'(e)$is a secondary edge weight, and$\varepsilon$is a global scaling factor. This perturbation ... 12 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$, and suppose that it preserves distances up to a factor of$C$. In particular, the$n$points$\varphi(e_1),\ldots,\varphi(e_n)$are within distance$C$of$\...

11

On a side note, it's not clear that EBPP is a robust class. For example, if instead of allowing the algorithm to flip an unbiased coin, if it were given an unbiased 3-sided coin, or a 6-sided die, it's not clear that you get the same class. BPP remains the same if you change these details. Anyway, your primary question is whether EBPP is equal to BPP or ...

11

I guess that the number of random variables $t$ and the threshold $t$ are different parameters, as otherwise $\Pr[|Y| \geq t] = 0$. Let $a_1, \dots, a_k, b_1, \dots, b_k\in_U \{\pm 1\}$ be iid random variables sampled uniformly at random from $\{\pm 1\}$ and $n=2^k$. Consider random variables $W_1,\dots, W_n$ of the form $c_1 \cdot c_2\cdot \dots \cdot c_k$ ...

11

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.

11

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 Lunch (NFL) theorem. There is a paper "Perhaps not a free lunch but at least a free appetizer" where it is shown that employing randomisation, (...

11

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 circuit, which takes a somewhat larger advice string, as follows. There are $2^n$ possible inputs. By hypothesis about the circuit, each random string is good ...

10

I will answer this from the perspective of distributed graph algorithms (distributed algorithms that solve a graph problem related to the structure of the communication network). Here are some non-obvious reasons for designing deterministic distributed algorithms in this setting: Subroutines in randomised algorithms. On p. 12–13 of these slides, Elkin ...

10

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 probability of error can be reduced below $2^{-n}$ by running $O(n)$ instances of the circuit with independent random bits in parallel, and taking a majority ...

10

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 problems) (This generalizes the example with one-way permutations. It includes as a special case decision problems from $\mathrm{UP\cap coUP}$.) The setup is ...

9

Use $k=\lceil\log n\rceil$ random bits to get a random number $r$ between $0$ and $2^k$. With probability at least $\tfrac{1}{2}$, $0\leq r < n$ so use that as your answer; otherwise, try again. If you've not succeeded after $t$ attempts, reject your input. The probability of this happening is at most $2^{-t}$, which can be made as small ...

9

The Kushilevitz-Mansour algorithm in learning theory establishes, that whenever $\hat{f}(x)$ is approximately sparse, i.e. there are only $O(poly(n))$-many large Fourier coefficients of absolute value $\Omega(1/poly(n))$, then we can find their locations and approximate their complex values in $\sf{BPP}$. Of course you can also efficiently sample from that ...

9

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$ both large) to $$\exp (z_{\mathrm{sq}}mn)$$ where $$z_{\mathrm{sq}}=\frac{4}{\pi}\sum_{i=0}^\infty\frac{(-1)^i}{(2i+1)^2}\approx 1.16624$$ but I'm not sure ...

9

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. 1989. The basic idea: Instead of checking $n = ab$ modulo $p$ for some random prime number $p$, check it modulo $2^i-1$ for some integer $i$. The reduction ...

8

It depends on what assumptions you are willing to make. Under certain hardness assumptions, namely $E \not\subseteq SIZE(2^{\varepsilon n})$, you get that $P = BPP$. This in particular implies that $BPP = ZPP$, and therefore that every language $L \in BPP$ is accepted by a Las Vegas machine (see "P=BPP unless E has Subexponential Circuits: Derandomizing the ...

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