Limitations of the Impagliazzo-Nisan-Wigderson Pseudorandom Generator Against Permutation Branching Programs.

The classic Impagliazzo-Nisan-Wigderson (INW) pseudorandom generator (PRG) (STOC '94) for space-bounded computation uses a seed of length to fool ordered branching programs of length , width , and alphabet size to within error . A series of works have shown that the analysis of the INW generator can be improved for the class of branching programs or the more general branching programs, improving the dependence on the length to or . However, when also considering the dependence on the other parameters, these analyses still fall short of the optimal PRG seed length .

Universal Bell Correlations Do Not Exist.

We prove that there is no finite-alphabet nonlocal box that generates exactly those correlations that can be generated using a maximally entangled pair of qubits. More generally, we prove that if some finite-alphabet nonlocal box is strong enough to simulate arbitrary local projective measurements of a maximally entangled pair of qubits, then that nonlocal box cannot itself be simulated using any finite amount of entanglement. We also give a quantitative version of this theorem for approximate simulations, along with a corresponding positive result.