ON BOUNDED DEPTH PROOFS FOR TSEITIN FORMULAS ON THE GRID; REVISITED
We study Frege proofs using depth-d Boolean formulas for the Tseitin contradiction on n \times n grids. We prove that if each line in the proof is of size M, then the number of lines is exponential in n/(log M)O(d). This strengthens a recent result of Pitassi, Ramakrishman, and Tan [2022 IEEE 62nd Annual Symposium on Foundations of Computer Science, 2022, pp. 445-456]. The key technical step is a
