Linear Programming Relaxations for Goldreich's Generators over Non-Binary Alphabets

Ryuhei Mori, Takeshi Koshiba, Osamu Watanabe +1

Goldreich suggested candidates of one-way functions and pseudorandom generators included in ${\mathsf{NC}}^0$. It is known that randomly generated Goldreich's generator using $(r-1)$…