12
$\begingroup$

Let $d$ be a constant. How can we provably construct a pseudorandom generator that fools $d$-state finite automata?

Here, a $d$-state finite automata has $d$ nodes, a start node, a set of nodes representing accept states, and two directed edges labeled 0, 1 coming out of each node. It changes state in the natural way as it reads input. Given an $\epsilon$, find $f:\{0,1\}^{k}\to \{0,1\}^n$ such that for every $d$-state finite automaton computing some function $A$,

$$|\mathbb P_{x\sim U_{k}}(A(f(x))=1)-\mathbb P_{x\sim U_n}(A(x)=1)|< \epsilon.$$

Here $U_k$ denotes the uniform distribution on $k$ variables, and we want $k$ to be as small as possible (e.g. $\log n$). I'm thinking of $d$ being on the order of $n$, though we can also ask the question more generally (ex. would the number of bits required grow with $n$?).

Some background

Construction of pseudorandom generators is important in derandomization, but the general problem (PRG's for polynomial-time algorithms) has so far proved too difficult. There has however been progress on PRG's for bounded-space computation. For example this recent paper (http://homes.cs.washington.edu/~anuprao/pubs/spaceFeb27.pdf) gives a bound of approximately $\log n\log d$ for regular read-once branching programs. The question with general read-once branching programs is still open (with $k=\log n$), so I'm wondering if the answer for this simplification is known. (A finite automaton is like a read-once branching program where every layer is the same.)

$\endgroup$
  • $\begingroup$ it might help to detail/ describe some why this is a natural formulation of the problem ie the origins/ bkg/ details/ reasoning of the probability expression. are there other known solutions of the question for other models? is it tied with the PAC framework etc? $\endgroup$ – vzn Dec 15 '14 at 23:56
  • $\begingroup$ I added a little background. $\endgroup$ – Holden Lee Dec 16 '14 at 4:47
  • $\begingroup$ maybe the idea of FSM fooling sets (p12) would work well here? ("If L has an infinite fooling set, then L is not accepted by any DFA.") $\endgroup$ – vzn Dec 16 '14 at 21:20
10
$\begingroup$

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 Nisan's result RL $\subseteq$ SC. Basically, he shows that if you are given a branching program then you can find a logarithmic-seed distribution that fools it. His result extends to a small number of branching programs. So if $d$ is a constant then you can enumerate over all possible finite-state automata, and find a distribution that fools all of them. This should still work as long as the number of programs is polynomial in $n$.

$\endgroup$
  • $\begingroup$ I think you mean RL$\subseteq$SC. $\endgroup$ – Holden Lee Dec 19 '14 at 18:19
1
$\begingroup$

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 matrix defining a FSM. there are other related theorems in the notes.

this apparently same proof is also cited by RJlipton on his blog "the warranty on Nisans generator". the proof apparently originates from the paper How strong is Nisan’s pseudo-random generator? David, Papakonstantinou, Sidiropoulos (2010). also note a near deeper question & better bounds are tied with a major complexity class separation:

They point out, without any proof, that if there was a PRG that does polynomially many passes and fools logspace machines then $\mathsf{L} \neq \mathsf{NP}$.

$\endgroup$
  • $\begingroup$ note, further look, the DPS paper is an extension of Nisans paper [NIS92] in their refs to space bounded machines with multiple passes. that ref is N. Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449–461, 1992. (also STOC’90). $\endgroup$ – vzn Dec 16 '14 at 22:16
  • 1
    $\begingroup$ Maybe if you read Nisan's paper you would notice that he states his theorem in terms of FSMs. Also it would be nice if you give some quantitative bounds $\endgroup$ – Sasho Nikolov Dec 16 '14 at 22:45
  • $\begingroup$ note some statements of the thm are in terms of logspace TMs. see also Fooling space-bounded models and low degree polynomials a survey, Li, Yang, sec 1.3 p6 Fooling read-once log-space Turing Machine $\endgroup$ – vzn Dec 16 '14 at 23:19
  • $\begingroup$ Both this question and the original paper give a statement in terms of FSMs. So your comment is hardly relevant. $\endgroup$ – Sasho Nikolov Dec 17 '14 at 4:36
  • 2
    $\begingroup$ Can you just state the relevant theorem, in the FSM formulation from Nisan's paper, in your answer? Not notes that state it in a different way, not a survey paper that states it a different way: first state the actual answer to the actual question? Is there anything difficult to understand about why that is a good thing to do? $\endgroup$ – Sasho Nikolov Dec 17 '14 at 4:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.