Lower bounds for the Bit Pigeonhole Principle in Bounded-Depth Resolution over Parities
Farzan Byramji (UCSD)
Monday, October 26th 2025, 2-3pm
Abstract:
The proof system resolution over parities extends the resolution proof system to allow linear algebra mod 2. While no strong lower bounds are known for this proof system, a recent line of work has shown exponential lower bounds for such proofs as long as the depth is restricted.
In this work, we prove such exponential lower bounds in bounded-depth resolution over parities for the bit pigeonhole principle and some of its variants. Along the way, we show that randomized parity decision trees are not much better than randomized ordinary decision trees for solving the collision-finding problem.
Joint work with Russell Impagliazzo