# Tag Info

20

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

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.

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

10

If $d$ is of the order of $n$ then you can write a constant-width branching program as a finite-state automaton, and logarithmic seed length is not known. But if $d$ is very small, say a constant, then you can do better and achieve logarithmic seed length -- I think, this is something I thought about years ago but never wrote down. The trick is to use ...

7

Yes, this notion has been studied. One interesting aspect is that the two notions of pseudorandomness known to be equivalent under the usual adversaries, "next bit predictability" and "indistinguishability", do not seem to be equivalent for deterministic adversaries. (If they were, we would have complexity class separations.) Here are three references; I'm ...

6

The meaning is a bit string $x$ which is distributed uniformly on $\{0,1\}^{|x|}$.

4

You can determine the period reasonably easily if you know the factorization of $M$ as $pq$, the factorization of $(p-1)\cdot (q-1)$ and the factorization of $\ell-1$ for any prime $\ell$ that divides $(p-1)\cdot (q-1)$. This requires two steps, first find the order of $x_0$ modulo $M$. Since this divides $(p-1)\cdot (q-1)$ whose factorization is known, ...

4

Not very practical, but you can sample from a the polytope of feasible flows using the well-known random walk techniques, see for example this classical paper by Kannan, Lovasz and Simonovits. These algorithms allow you to sample in polynomial time (in the dimension) from a distribution which is arbitrarily close to uniform in $L_1$ distance.

2

I think I can show the optimality of a scheme that I skteched in the question, the one that does rejection sampling but reuses the remaining entropy. Description of the scheme. Thinking as an algorithm, the scheme is the following. It has two parameters, an integer $n$, and a bound $m$, $0 \leq n < m$, with the invariant that $n$ was drawn uniformly at ...

1

The Perfect Matching problem was "almost" derandomized in 2016 [1]: there is a deterministic algorithm requiring "only" quaispolynomial resources, namely $n^{\mathcal O(\log n)}$ for the bipartite case and $n^{\mathcal O(\log^2n)}$ for the general case (in 2017 [2]). Although Edmonds gave a polynomial-time algorithm for perfect matching, ...

1

something close to what you are requesting seems to be proven in Thm 2.10 p6 of these lecture notes by O'Donnell, Lecture 16: Nisan’s PRG for small space but it does not cite the original ref for the proof. a simple statement of the theorem in terms of FSMs is not given in this ref but is translatable. (volunteers?) in the theorem $M^n$ is a transition ...

1

Regarding question A, it is possible to adapt the PRNG to yield uniformly distributed numbers using this. However, the range of this new uniform generator has size smaller than $K$, unless the PRNG is itself uniform. The number of possible outcomes of this new generator will depend on the min-entropy of the original generator. To get some intuition on why ...

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