Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR13-088 | 16th June 2013 04:09

$AC^0$ Pseudorandomness of Natural Operations

RSS-Feed




TR13-088
Authors: Zachary Remscrim, Michael Sipser
Publication: 16th June 2013 04:41
Downloads: 2924
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint