We prove that for the bit pigeonhole principle with any number of pigeons and $n$ holes, any depth $D$ proof in resolution over parities must have size $\exp(\Omega(n^3/D^2))$. Our proof uses the random walk with restarts approach of Alekseev and Itsykson [STOC '25], along with ideas from recent simulation theorems ... more >>>

In this work we observe a tight connection between three topics: $NC^0$ cryptography, $NC^0$ range avoidance, and static data structure lower bounds. Using this connection, we leverage techniques from the cryptanalysis of $NC^0$ PRGs to prove state-of-the-art results in the latter two subjects. Our main result is a quadratic improvement ... more >>>

We prove a lifting theorem from randomized decision tree depth to randomized parity decision tree (PDT) size. We use the same property of the gadget, stifling, which was introduced by Chattopadhyay, Mande, Sanyal and Sherif [ITCS'23] to prove a lifting theorem for deterministic PDTs. Moreover, even the milder condition that ... more >>>