Subset sum at constant density below one ⇒ PRG

Standard model · IN96

Statement

Let with for a constant . If subset sum is hard at constant density below one for this , then , mapping seed bits to output bits, is a PRG — IN96. One evaluation stretches the seed by bits using only additions, and the construction can be implemented in NC with an optimal number of processors — IN96.

Notes