An exponential lower bound for the bit pigeonhole principle in resolution over parities
Claimed: for every , any dag-like refutation of the bit pigeonhole principle with pigeons and holes has more than nodes; exponential in the number of holes up to a factor, for a proof system with no regularity or depth restriction. The whitepaper's route is a transfer to degree- polynomial calculus. Can…