# Tag Info

37

For one, proving $BPP \subseteq NP$ would easily imply that $NEXP \neq BPP$, which already means that your proof can't relativize. But let's look at something even weaker: $coRP \subseteq NTIME[2^{n^{o(1)}}]$. If that is true, then polynomial identity testing for arithmetic circuits is in nondeterministic subexponential time. By Impagliazzo-Kabanets'04, ...

36

Sorting nuts and bolts The following problem was suggested by Rawlins in 1992: Suppose you are given a collection of n nuts and n bolts. Each bolt fits exactly one nut, and otherwise, the nuts and bolts have distinct sizes. The sizes are too close to allow direct comparison between pairs of bolts or pairs of nuts. However, you can compare any nut to any ...

32

This is discussed a bit in my paper with H. C. Williams, "Factoring Integers before Computers" In a 1917 paper, H. C. Pocklington discussed an algorithm for finding sqrt(a), modulo p, which depended on choosing elements at random to get a nonresidue of a certain form. In it, he said, "We have to do this [find the nonresidue] by trial, using the Law of ...

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

27

Buffons needle algorithm for estimating $\pi$, basically a Monte Carlo method, dates to publication in 1777. note that Monte Carlo methods date to the 1940s with the US "Manhattan" atom bomb project & were coinvented by Ulam, Von Neumann, and Metropolis.

22

What you need is a "seeded extractor" with the following parameters: seed of length $O(\log n)$, crude randomness $n/2$, and output length $n^{\Omega(1)}$. These are known. While I'm not up to date with the most recent surveys, I believe that section 3 of Ronen's survey is enough. The only thing you will need to show is that your source has sufficient "min-...

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

Your solution does not work (or I don't understand it): the resulting permutation would not be uniformly random. To Sasho Nikolov, this is a research topic and is actually the topic (among others) of a paper I have recently submitted, where I provide an optimal algorithm. I can give you an idea of the lower bound. Indeed, you would have to distinguish ...

19

I think the difficulty is that this wording slightly misleading; as they state more clearly in the Introduction (1.2), "the expected values of the dual variables constitute a feasible dual solution." For every fixed setting of the dual variables $X$, we obtain some primal solution of value $f(X)$ and a dual solution of value $\frac{e}{e-1}f(X)$. (The dual ...

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

18

The Metropolis–Hastings algorithm was published in 1953 and dates back earlier to the Manhattan project, long before Rabin. Like many of the early randomized methods given in other answers, it is a Monte Carlo algorithm. Is it possible that the claim on the Wikipedia page is a garbled form of the claim that Rabin's was the first Las Vegas algorithm?

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

18

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

17

Once you are not just talking about poly-time but rather look at the many models of computation we study, there are examples everywhere: In Logspace: Un-directed ST connectivity (in RL since 1979, and in L only since 2005) In NC: Finding a perfect matching in a bipartite graph in parallel (in RNC and still not known to be in NC) In interactive proofs: ...

17

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{... 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 ... 13 Problem: An array$A[1..2n]$consists of$n$1s and$n$0s. Find an$i$such that$A[i]$is 1. You are allowed to query 'Which number is present in$A[i]$'? Each query takes constant time. Solution: Randomized Algorithm: Pick a random index$i$and check if$A[i]$is 1. Expected number of queries is 2, but any deterministic algorithm must make at least$...

13

The notion of "theoretically sound" pseudorandom generators is not really well defined. After all, no pseudorandom generator has a proof of security. I don't know that we can say that a pseudorandom generator based on the hardness of factoring large integers is "more secure" than, say, using AES as a pseudorandom generator. (In fact, there is a sense that it ...

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

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

Most streaming algorithms In the streaming model of computation (AMS, book), an algorithm processes an online sequence of updates and is restricted to keep only sublinear space. At any point in time, the algorithm should be able to answer a query. For many problems there exist sublinear space randomized streaming algorithms while provably no deterministic ...

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

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

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 The Gaussian normal curve/distribution of statistics can be "computed" by many very simple physical processes. One of the simplest is a board with a pin array in a triangular grid (also known as a "Galton box" dating to the 1800s) where pins are offset 1/2 square distance on alternating rows. Dropping balls repeatedly from the same position, the balls ... 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 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_\...

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