ECCC-Report TR13-088https://eccc.weizmann.ac.il/report/2013/088Comments and Revisions published for TR13-088en-usSun, 16 Jun 2013 04:41:33 +0300
Paper TR13-088
| $AC^0$ Pseudorandomness of Natural Operations |
Zachary Remscrim,
Michael Sipser
https://eccc.weizmann.ac.il/report/2013/088A 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 that several naturally occurring functions are $AC^0$-pseudorandom, including convolution, nearly all homomorphisms, Boolean matrix multiplication, integer multiplication, finite field multiplication and division, several problems involving computing rank and determinant, and a variant of the algebraic integer problem.Sun, 16 Jun 2013 04:41:33 +0300https://eccc.weizmann.ac.il/report/2013/088