2 papers
cs.CC2026
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 is hard, along the way the proof provides us wit…
cs.CC2024
A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity
Pavel DvoÅák, Bruno Loff, Suhail Sherif
We study semidefinite relaxations of combinatorial statements. By relaxing the pigeonhole principle, we obtain a new "quantum" pigeonhole principle which is a stronger state…