Subset sum at constant density below one ⇒ PRG
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
- Pseudorandomness of is hardness of decision subset sum at the same parameters (Subset sum at constant density below one ⇒ Decision subset sum) — standard.