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.CC2025
Communication Complexity is NP-hard
Shuichi Hirahara, Rahul Ilango, Bruno Loff
In the paper where he first defined Communication Complexity, Yao asks: \emph{Is computing (the 2-way communication complexity of a given function ) NP-complete?} The pr…