Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR13-088 | 16th June 2013 04:09

#### $AC^0$ Pseudorandomness of Natural Operations

TR13-088
Authors: Zachary Remscrim, Michael Sipser
Publication: 16th June 2013 04:41
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 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.