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

<p>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 <a href="http://www.google.com/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=2&amp;cad=rja&amp;uact=8&amp;ved=0CCcQFjAB&amp;url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.47.2997&amp;ei=bwCTVLH-MaLCsASQn4CQDA&amp;usg=AFQjCNGEQZA_6E950NTNBFyiqSwOEE9F-Q&amp;bvm=bv.82001339,d.cWc" rel="nofollow">RL $\subseteq$ SC</a>.  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$.</p>

CC BY-SA 3.0
2014-12-19T18:19:47.543Z
I think you mean RL$\subseteq$SC.
Holden Lee
CC BY-SA 3.0
2014-12-18T16:34:06.043Z
2014-12-19T19:11:24.783Z
2014-12-19T19:11:24.783Z
Manu
<p>something close to what you are requesting seems to be proven in Thm 2.10 p6 of these lecture notes by O'Donnell, <a href="http://www.cs.cmu.edu/~odonnell/complexity/docs/lecture16.pdf" rel="nofollow">Lecture 16: Nisan’s PRG for small space</a> 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. <em>(volunteers?)</em> in the theorem $M^n$ is a transition matrix defining a FSM. there are other related theorems in the notes. </p>

<p>this apparently same proof is also cited by RJlipton on his blog <a href="http://rjlipton.wordpress.com/2010/10/31/the-warranty-on-nisans-generator/" rel="nofollow">"the warranty on Nisans generator"</a>. the proof apparently originates from the paper <a href="http://www.cs.toronto.edu/~papakons/pdfs/nisan_RNC.pdf" rel="nofollow">How strong is Nisan’s pseudo-random generator?</a> David, Papakonstantinou, Sidiropoulos (2010). also note a near deeper question &amp; better bounds are tied with a major complexity class separation:</p>

<blockquote>
  <p>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}$. </p>
</blockquote>

CC BY-SA 3.0
2014-12-16T22:16:17.843Z
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).
vzn
CC BY-SA 3.0
2014-12-16T22:45:51.010Z
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
Sasho Nikolov
CC BY-SA 3.0
2014-12-16T23:19:25.033Z
note some statements of the thm are in terms of logspace TMs. see also [Fooling space-bounded models and low degree polynomials
a survey](http://iiis.tsinghua.edu.cn/~RC3/liyuanzhi/lowdegree.pdf), Li, Yang, sec 1.3 p6 Fooling read-once log-space Turing Machine
vzn
CC BY-SA 3.0
2014-12-17T04:36:52.453Z
Both this question and the original paper give a statement in terms of FSMs. So your comment is hardly relevant.
Sasho Nikolov
CC BY-SA 3.0
2014-12-17T04:39:02.170Z
huh? logspace TMs are shown to be equivalent to FSMs for purposes of the similar thm in the Li/Yang ref.
vzn
CC BY-SA 3.0
2014-12-17T04:49:21.250Z
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?
Sasho Nikolov
CC BY-SA 3.0
2014-12-17T04:58:40.157Z
am not interpreting the question as _narrowly_ as you seem to be. the later research of this over 2 decade old result has gone in new directions building on it. the original poster is clearly asking also more _broadly_ about what _range_ of results are known on the problem. plz feel free to edit the answer to state the original thm if you like. would have linked to an electronic version of the Nisan paper if one seemed to be available. yes, admittedly it is not a trivial exercise to reformulate the result _exactly_ in the form requested but as the answer starts, "something _close_..."
vzn
CC BY-SA 3.0
2014-12-16T21:50:44.743Z
2014-12-16T21:50:44.743Z
vzn
<p>Let $d$ be a constant. How can we provably construct a pseudorandom generator that fools $d$-state finite automata? </p>

<p>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$, </p>

<p>$$|\mathbb P_{x\sim U_{k}}(A(f(x))=1)-\mathbb P_{x\sim U_n}(A(x)=1)|&lt; \epsilon.$$ </p>

<p>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$?). </p>

<p><strong>Some background</strong></p>

<p>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 (<a href="http://homes.cs.washington.edu/~anuprao/pubs/spaceFeb27.pdf">http://homes.cs.washington.edu/~anuprao/pubs/spaceFeb27.pdf</a>) gives a bound of approximately $\log n\log d$ for <em>regular</em> 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.)</p>

CC BY-SA 3.0
2014-12-15T23:56:30.800Z
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](http://en.wikipedia.org/wiki/Probably_approximately_correct_learning) etc?
vzn
CC BY-SA 3.0
2014-12-16T04:47:52.043Z
I added a little background.
Holden Lee
CC BY-SA 3.0
2014-12-16T21:20:37.457Z
maybe the idea of [FSM fooling sets](https://courses.engr.illinois.edu/cs498374/notes/03-automata.pdf) (p12) would work well here? ("If L has an infinite fooling set, then L is not accepted by any DFA.")
vzn
<automata-theory><pseudorandomness><pseudorandom-generators>
Pseudorandom generator for finite automata
Holden Lee
# Pseudorandom generator for finite automata

(Asked by: username_0 on 2014-12-15)

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

**Tags:** automata-theory, pseudorandomness, pseudorandom-generators
> **Comments:**
> **username_1**: 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](http://en.wikipedia.org/wiki/Probably_approximately_correct_learning) etc?  
> **username_0**: I added a little background.  
> **username_1**: maybe the idea of [FSM fooling sets](https://courses.engr.illinois.edu/cs498374/notes/03-automata.pdf) (p12) would work well here? ("If L has an infinite fooling set, then L is not accepted by any DFA.")  

---

## 2 answers

### Answer by username_2 on 2014-12-18. Score: 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 Nisan's result [RL $\subseteq$ SC](http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact=8&ved=0CCcQFjAB&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.47.2997&ei=bwCTVLH-MaLCsASQn4CQDA&usg=AFQjCNGEQZA_6E950NTNBFyiqSwOEE9F-Q&bvm=bv.82001339,d.cWc). 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$.

> **Comments:**
> **username_0**: I think you mean RL$\subseteq$SC.  

---

### Answer by username_1 on 2014-12-16. Score: 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](http://www.cs.cmu.edu/~odonnell/complexity/docs/lecture16.pdf) 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"](http://rjlipton.wordpress.com/2010/10/31/the-warranty-on-nisans-generator/). the proof apparently originates from the paper [How strong is Nisan’s pseudo-random generator?](http://www.cs.toronto.edu/~papakons/pdfs/nisan_RNC.pdf) 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}$.

> **Comments:**
> **username_1**: 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).  
> **username_3**: 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  
> **username_1**: note some statements of the thm are in terms of logspace TMs. see also [Fooling space-bounded models and low degree polynomials a survey](http://iiis.tsinghua.edu.cn/~RC3/liyuanzhi/lowdegree.pdf), Li, Yang, sec 1.3 p6 Fooling read-once log-space Turing Machine  
> **username_3**: Both this question and the original paper give a statement in terms of FSMs. So your comment is hardly relevant.  
> **username_1**: huh? logspace TMs are shown to be equivalent to FSMs for purposes of the similar thm in the Li/Yang ref.  
> **username_3**: 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?  
> **username_1**: am not interpreting the question as _narrowly_ as you seem to be. the later research of this over 2 decade old result has gone in new directions building on it. the original poster is clearly asking also more _broadly_ about what _range_ of results are known on the problem. plz feel free to edit the answer to state the original thm if you like. would have linked to an electronic version of the Nisan paper if one seemed to be available. yes, admittedly it is not a trivial exercise to reformulate the result _exactly_ in the form requested but as the answer starts, "something _close_..."  

---

