All reports by Author Michael Sipser:

__
TR13-088
| 16th June 2013
__

Zachary Remscrim, Michael Sipser#### $AC^0$ Pseudorandomness of Natural Operations

Zachary Remscrim, Michael Sipser

A function $f:\Sigma^{*} \rightarrow \Sigma^{*}$ on strings is $AC^0$-pseudorandom if the pair $(x,\hat f(x))$ is $AC^0$-indistinguishable from a uniformly random pair $(y,z)$ when $x$ is chosen uniformly at random. Here $\hat f(x)$ is the string that is obtained from $f(x)$ by discarding some selected bits from $f(x)$.

It is shown ... more >>>