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.DS2024
On the complexity and approximability of Bounded access Lempel Ziv coding
Ferdinando Cicalese, Francesca Ugazio
We study the complexity of constructing an optimal parsing of a string under the constraint that given a position in the original text, and the LZ…