# Tag Info

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

28

First, let me comment on the specific case of the Valiant-Vazirani reduction; this will, I hope, help clarify the general situation. The Valiant-Vazirani reduction can be viewed/defined in several ways. This reduction is "trying" to map a satisfiable Boolean formula $F$ to a uniquely-satisfiable $F'$, and an unsatisfiable $F$ to an unsatisfiable $F'$. All ...

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

Just for reference, I stumbled across this really interesting paper today, which gives evidence that a deterministic reduction is unlikely: Dell, H., Kabanets, V., Watanabe, O., & van Melkebeek, D. (2012). Is the Valiant-Vazirani Isolation Lemma Improvable? ECCC TR11-151 They argue that this is not possible unless NP is contained in P/poly.

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

Not sure how much of an answer this is, I'm just indulging in some rumination. Question 1 could be equally asked about P $\neq$ NP and with a similar answer -- the techniques/ideas used to prove the result would be the big breakthrough more so than the conclusion itself. For Question 2 I want to share some background and a thought. Pretty much all the ...

16

Check Chapter 7 of Salil Vadhan's monograph. Corollary 7.64 is Impagliazzo and Wigderson's result.

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.

15

1) What is meant by necessary is that one way to generate a $k$-wise independent distribution is to break the input in blocks of $k+1$ bits, and let the $(k+1)$th bit of each block be the parity of the other $k$ bits in the block. Obviously this distribution can be broken just by computing parity on $k$ bits. The result you claim follows from the fact that ...

14

I'd say we have no good reason to think BQP is in P/poly. We do have reasons to think that BQP is not in P/poly, but they're more-or-less identical to our reasons to think that BQP≠BPP. E.g., if BQP⊂P/poly then Factoring is in P/poly, which is enough to break lots of cryptography according to standard security definitions. Also, as you correctly ...

14

The number field sieve has never been analyzed rigorously. The complexity that you quote is merely heuristic. The only subexponential algorithm which has been analyzed rigorously is Dixon's factorization algorithm, which is very similar to the quadratic sieve. According to Wikipedia, Dixon's algorithm runs in time $e^{O(2\sqrt{2}\sqrt{\log n\log\log n})}$. ...

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 In the oracle world, it is easy to give examples where randomness gives us much more power. Consider, for example, the problem of finding a zero of a balanced Boolean function. A randomized algorithm accomplishes that using$O(1)$queries with constant success probability, while any deterministic algorithm requires at least$n/2$queries. Here is another ... 13 If you're asking for independent problems, how about: Find a prime in the interval$[N, 5N/4]$, Find two primes whose product is in the interval$[N, 9N/8]$, Find three primes whose product is in the interval$[N, 17N/16]$, Find four primes whose product is in the interval$[N, 33N/32]$, Find five primes whose product is in the interval$[N, 65N/...

12

One reason why it might seem strange to you, that we seem to think there is more apparent (or conjectured) power in the randomized reductions from $\mathsf{NP}$ to $\mathsf{UP}$ than the comparable one from $\mathsf{BPP}$ to $\mathsf P$, is because you may be tempted to think of randomness as something which is either powerful (or not powerful) independently ...

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

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

11

Nondeterministic computations can also be viewed as verification of claims using short proofs. That is, the class NTIME(t) can also be viewed as the class of languages $L$ such that a claim of the form $x \in L$ can be verified in time $t(|x|)$ by reading a short proofs. In this model, "quantifying the braching" is analogous to studying how short the proofs ...

11

It follows from this PRG of Nisan and Zuckerman. This paper shows that if you have an algorithm that uses space $S$ and only $\mathrm{poly}(S)$ random bits, then the number of random bits can be decreased to $O(S)$. In particular, in the setting you describe, we have $S = O(\log n)$, so the number of random bits can be reduced to $O(\log n)$. Then, we can ...

11

This is not known, but as domotorp stated, it is believed not to be the case. First, note that $\mathsf{P} = \mathsf{BPP}$ doesn't say that randomness isn't useful in any context, just in the context of poly-time decision problems. For example, just assuming $\mathsf{P} = \mathsf{BPP}$ is already not known to imply that $\mathsf{AM} = \mathsf{NP}$ (and the ...

10

There is a particular use of randomness that is fairly common in parameterized complexity, which involves either the isolation lemma, or the Schwartz-Zippel lemma. Roughly, it involves defining a large enumeration of potential solutions, and arguing that all non-solutions "pair up" (e.g., are counted twice) while the desired solution(s) are counted only once....

10

Another example is estimating the volume of a polyhedron in high dimensions. There's an unconditional lower bound on deterministic strategies to approximate the volume to even an exponential factor, but there's an FPRAS for the problem. Update: the relevant paper is (link to PDF): I. Barany and Z. Furedi. Computing the volume is difficult, Discrete and ...

10

[tl;dr] A lot is known, and it is a very active area! [/tl;dr] It is important to specify the representation of the input polynomials, since it they are given as lists of coefficients or nonzero monomials, the problem is trivial. Thus one usually assumes the polynomials to be given as arithmetic circuits (a.k.a. straight-line programs). And the general case ...

10

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

The paper you linked in the comments - and references therein - already seems to answer your first question. For your second question: I have little reason to think that there is a theorem of the form "If GI is in P, then [something about derandomizing PIT]." For example, it is possible that GI is in P, but Polynomial Equivalence is not. (Note that PolyEq ...

9

By the work of Klivans and van Melkebeek (which relativizes), if E = DTIME($2^{O(n)}$) does not have circuits with PP gates of size $2^{o(n)}$ then PH is in PP. The contrapositive says that if PH is not in PP then E has subexponential-size circuits with PP gates. That is consistent with the fact that an oracle proof of PH not in PP gives a relativized lower ...

9

There is a difficulty with the premise of your question — "when does randomization stops helping within $\mathrm{PSPACE}$ — because it suggests that the computational classes $\mathrm{X}$ such that $\mathrm{P \subseteq X \subseteq PSPACE}$ form some sort of linear hierarchy when this is not evident. We can illustrate this by comparisons between ...

8

Polylog independence may not be the only way to fool $AC^{0}$ circuits. To illustrate this example, consider the class of linear polynomials. Any zero set of a linear polynomial is $(n-1)$-wise independent but of course this doesn't fool linear polynomials. Hence, $(n-1)$-wise independent distributions do not fool this class. This of course doesn't mean that ...

8

I'm not an expert, but perhaps some (not-so-natural?) examples can be directly derived using the technique of deterministically reducing BPP search problems to BPP decision problems, presented in: Oded Goldreich, In a World of P=BPP. Studies in Complexity and Cryptography 2011: 191-232 In particular see Theorem 3.5: (reducing search to decision): For every ...

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