Tight Depth Lower Bounds for Stretch AmplificationResearch Paper
A pseudorandom generator (PRG) with stretch is an efficiently computable function , , whose random outputs no polynomial-time observer can tell from uniform -bit strings. A generator of very small stretch is often considerably easier to build from a hardness assumption, while key applications need a larger…