The Switching Lemma shows what the Switching Lemma cannot prove: an unconditional natural-proofs barrier

Bruno Loff, Suhail Sherif, Navid Talebanfard +1

Razborov and Rudich (JCSS'97) observed that all known lower-bound proofs follow a certain pattern: when showing that a function $F$ is hard, along the way the proof provides us wit…