{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T09:09:43Z","timestamp":1764580183409,"version":"3.46.0"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2025,10,14]]},"abstract":"<jats:p>We study Frege proofs for the one-to-one graph Pigeon Hole Principle defined on the $n\\times n$ grid where $n$ is odd. We are interested in the case where each formula in the proof is a depth $d$ formula in the basis given by $\\land$, $\\lor$, and $\\neg$. We prove that in this situation the proof needs to be of size exponential in $n^{\u03a9(1\/d)}$. If we restrict the size of each line in the proof to be of size $M$ then the number of lines needed is exponential in $n\/(\\log M)^{O(d)}$. The main technical component of the proofs is to design a new family of random restrictions and to prove the appropriate switching lemmas.<\/jats:p>\n                  <jats:p>42 pages. This is the TheoretiCS journal version<\/jats:p>","DOI":"10.46298\/theoretics.25.27","type":"journal-article","created":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T09:05:12Z","timestamp":1764579912000},"source":"Crossref","is-referenced-by-count":0,"title":["On Small-depth Frege Proofs for PHP"],"prefix":"10.46298","volume":"Phase 2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5379-345X","authenticated-orcid":false,"given":"Johan","family":"H\u00e5stad","sequence":"first","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2025,12,1]]},"container-title":["TheoretiCS"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/arxiv.org\/pdf\/2401.15683v3","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/arxiv.org\/pdf\/2401.15683v3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T09:05:12Z","timestamp":1764579912000},"score":1,"resource":{"primary":{"URL":"https:\/\/theoretics.episciences.org\/12967"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,1]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/theoretics.25.27","relation":{"has-preprint":[{"id-type":"arxiv","id":"2401.15683v2","asserted-by":"subject"},{"id-type":"arxiv","id":"2401.15683v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2401.15683","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2401.15683","asserted-by":"subject"}]},"ISSN":["2751-4838"],"issn-type":[{"value":"2751-4838","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,1]]},"article-number":"12967"}}