Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908673942487040 |
|---|---|
| author | Byramji, Farzan Impagliazzo, Russell |
| author_facet | Byramji, Farzan Impagliazzo, Russell |
| contents | We prove lower bounds for proofs of the bit pigeonhole principle (BPHP) and its generalizations in bounded-depth resolution over parities (Res$(\oplus)$). For weak BPHP$_n^m$ with $m = cn$ pigeons (for any constant $c>1$) and $n$ holes, for all $ε>0$, we prove that any depth $N^{1.5 - ε}$ proof in Res$(\oplus)$ must have exponential size, where $N = cn\log n$ is the number of variables.
Inspired by recent work in TFNP on multicollision-finding, we consider a generalization of the bit pigeonhole principle, denoted $t$-BPHP$_n^m$, asserting that there is a map from $[m]$ to $[n]$ ($m > (t-1)n$) such that each $i \in [n]$ has fewer than $t$ preimages. We prove that any depth $N^{2-1/t-ε}$ proof in Res$(\oplus)$ of $t$-BPHP$_n^{ctn}$ (for any constant $c \geq 1$) must have exponential size.
For the usual bit pigeonhole principle, we show that any depth $N^{2-ε}$ Res$(\oplus)$ proof of BPHP$_n^{n+1}$ must have exponential size. As a byproduct of our proof, we obtain that any randomized parity decision tree for the collision-finding problem with $n+1$ pigeons and $n$ holes must have depth $Ω(n)$, which matches the upper bound coming from a deterministic decision tree.
We also prove a lifting theorem for bounded-depth Res$(\oplus)$ with a constant size gadget which lifts from $(p, q)$-DT-hardness, recently defined by Bhattacharya and Chattopadhyay. By combining our lifting theorem with the $(Ω(n), Ω(n))$-DT-hardness of the $n$-variate Tseitin contradiction over a suitable expander, proved by Bhattacharya and Chattopadhyay, we obtain an $N$-variate constant-width unsatisfiable CNF formula with $O(N)$ clauses for which any depth $N^{2-ε}$ Res$(\oplus)$ proof requires size $\exp(Ω(N^ε))$. Previously no superpolynomial lower bounds were known for Res$(\oplus)$ proofs when the depth is superlinear in the size of the formula. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_20023 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities Byramji, Farzan Impagliazzo, Russell Computational Complexity We prove lower bounds for proofs of the bit pigeonhole principle (BPHP) and its generalizations in bounded-depth resolution over parities (Res$(\oplus)$). For weak BPHP$_n^m$ with $m = cn$ pigeons (for any constant $c>1$) and $n$ holes, for all $ε>0$, we prove that any depth $N^{1.5 - ε}$ proof in Res$(\oplus)$ must have exponential size, where $N = cn\log n$ is the number of variables. Inspired by recent work in TFNP on multicollision-finding, we consider a generalization of the bit pigeonhole principle, denoted $t$-BPHP$_n^m$, asserting that there is a map from $[m]$ to $[n]$ ($m > (t-1)n$) such that each $i \in [n]$ has fewer than $t$ preimages. We prove that any depth $N^{2-1/t-ε}$ proof in Res$(\oplus)$ of $t$-BPHP$_n^{ctn}$ (for any constant $c \geq 1$) must have exponential size. For the usual bit pigeonhole principle, we show that any depth $N^{2-ε}$ Res$(\oplus)$ proof of BPHP$_n^{n+1}$ must have exponential size. As a byproduct of our proof, we obtain that any randomized parity decision tree for the collision-finding problem with $n+1$ pigeons and $n$ holes must have depth $Ω(n)$, which matches the upper bound coming from a deterministic decision tree. We also prove a lifting theorem for bounded-depth Res$(\oplus)$ with a constant size gadget which lifts from $(p, q)$-DT-hardness, recently defined by Bhattacharya and Chattopadhyay. By combining our lifting theorem with the $(Ω(n), Ω(n))$-DT-hardness of the $n$-variate Tseitin contradiction over a suitable expander, proved by Bhattacharya and Chattopadhyay, we obtain an $N$-variate constant-width unsatisfiable CNF formula with $O(N)$ clauses for which any depth $N^{2-ε}$ Res$(\oplus)$ proof requires size $\exp(Ω(N^ε))$. Previously no superpolynomial lower bounds were known for Res$(\oplus)$ proofs when the depth is superlinear in the size of the formula. |
| title | Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2511.20023 |