We study the complexity of black-box constructions of
pseudorandom functions (PRF) from one-way functions (OWF)
that are secure against non-uniform adversaries. We show
that if OWF do not exist, then given as an oracle any
(inefficient) hard-to-invert function, one can compute a
PRF in polynomial time with only $k(n)$ oracle queries,
for any $k(n) = \omega(1)$ (e.g.\ $k(n) = \log^* n$).
This result shows a limitation of a certain class of
techniques for proving efficiency lower bounds on the
construction of PRF from OWF. Our result builds on the
work of Reingold, Trevisan, and Vadhan (TCC '04), who
show that when OWF do not exist there is a pseudorandom
{\em generator} (PRG) construction that makes only one
oracle query to the hard-to-invert function. Our proof
combines theirs with the Nisan-Wigderson generator (JCSS '94),
and with a recent technique by Berman and Haitner (TCC '12).

Working in the same context (i.e.\ when OWF do not
exist), we also construct a poly-time PRG with arbitrary
polynomial stretch that makes non-adaptive queries to an
(inefficient) one-bit-stretch oracle PRG. This contrasts
with the well-known adaptive stretch-increasing
construction due to Goldreich and Micali.

Both above constructions simply apply an affine function
(parity or its complement) to the query answers. We
complement this by showing that if the post-processing is
restricted to only taking projections then non-adaptive
constructions of PRF, or even linear-stretch PRG, can be
ruled out.

We also use a result by Applebaum, Ishai, and Kushilevitz (J.\ Comput.\ '06) to rule out simple ``hash-query-extract'' PRF
constructions, assuming the existence of OWF computable
in logarithmic space.