3 ms·
Many tight connections between the problem of (BPP vs superpolynomial-time complexity classes) and the existence of hard-on-average functions have been known fo
by CaptainNegative 5y ago
Many tight connections between the problem of (BPP vs superpolynomial-time complexity classes) and the existence of hard-on-average functions have been known for a long time -- at least since the Nisan-Wigderson construction was discovered in '94. What distinguishes this paper from the related results preceding it?