Razborov and Rudich's natural proofs barrier roughly says that it is computationally hard to certify that a uniformly random truth table has high circuit complexity. In this work, we show that the natural proofs barrier (specifically, Rudich's conjecture that there are no NP-constructive natural properties against $P/poly$) implies the following ... more >>>