A function f: on strings is AC0 -pseudorandom if the pair (xf(x)) is AC0 -indistinguishable from a uniformly random pair (yz) when x is chosen uniformly at random. Here 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 AC0 -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