Black-Box PPP is Not Turing-Closed
Noah Fleming

Stefan Grosser

Toniann Pitassi

Robert Robere

Memorial University

McGillColumbia University

McGillJune 28, 2024
Abstract
The complexity class PPP contains all total search problems many-one reducible to the
P IGEON problem, where we are given a succinct encoding of a function mapping n+1 pigeons
to n holes, and must output two pigeons that collide in a hole. PPP is one of the “original
five” syntactically-defined subclasses of TFNP, and has been extensively studied due to thestrong connections between its defining problem — the pigeonhole principle — and problems in cryptography, extremal combinatorics, proof complexity, and other fields. However,despite its importance, PPP appears to be less robust than the other important TFNP subclasses. In particular, unlike all other major TFNP subclasses, it was conjectured by Buss
and Johnson that PPP is not closed under Turing reductions, and they called for a black-box
separation in order to provide evidence for this conjecture. The question of whether PPP
contains its Turing closure was further highlighted by Daskalakis in his recent IMU Abacus
Medal Lecture.
In this work we prove that PPP is indeed not Turing-closed in the black-box setting,affirmatively resolving the above conjecture and providing strong evidence that PPP is not
Turing-closed. In fact, we are able to separate PPP from its non-adaptive Turing closure, inwhich all calls to the P IGEON oracle must be made in parallel. This differentiates PPP fromall other important TFNP subclasses, and especially from its closely-related subclass PWPP
— defined by reducibility to the weak pigeonhole principle — which is known to be nonadaptively Turing-closed. Our proof requires developing new tools for PPP lower bounds,
and creates new connections between PPP and the theory of pseudoexpectation operators
used for Sherali-Adams and Sum-of-Squares lower bounds. In particular, we introduce a new
type of pseudoexpectation operator that is precisely tailored for lower bounds against blackbox PPP, which may be of independent interest.

Contents
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 Preliminaries on Black-Box TFNP . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 Collision-Free Pseudoexpectations . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 Lower Bounds for Black-Box PPP . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 Lower Bounds for P IGEON⊗2 Generalizations . . . . . . . . . . . . . . . . . . . . . .
6 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A SOS Bounds for Nonadaptive Pigeon . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
7
9
12
28
32
32
35

1

Introduction

The class TFNP consists of all total NP search problems: that is, search problems where potential solutions
can be efficiently verified, and also where solutions are guaranteed to exist. TFNP contains many importantsearch problems that we would like to efficiently solve in practice, but which seem to not admit polynomialtime algorithms. Two standard examples are the NASH problem (given a bimatrix game, output a Nashequilibrium of that game) and the FACTORING problem (given a number n, output a prime factor of n).
Note that TFNP itself is a semantic class, and therefore believed not to admit complete problems [Pud15].
Therefore, in order to study problems inside of TFNP, researchers have defined syntactic subclasses byusing many-one reductions to certain complete problems of interest. For instance, the NASH problem iscomplete for the class PPAD [DGP09, CDT09], which is typically defined using the complete problem
E ND -O F -L INE [Pap94].
In this work we study the TFNP subclass PPP, whose defining complete problem is P IGEON.
Definition 1.1. The P IGEON problem is defined as follows. The input is a polynomial-size boolean circuit
C encoding a boolean function from {0, 1}n → {0, 1}n . The output is either any x ∈ {0, 1}n such that
C(x) = 0n , or any two strings x ̸= y ∈ {0, 1}n such that C(x) = C(y). The class PPP contains all total
search problems that are polynomial-time many-one reducible to P IGEON.
PPP is one of the “original five” TFNP subclasses introduced in the 1990s to capture the complexity ofinteresting total search problems [MP91, JPY88, Pap94, BIK+ 94] — the other four being PLS, PPA, PPAD,
and PPADS. PPP is also one of the most important of the TFNP subclasses. The pigeonhole principle
captures strong induction, which is the basic axiom underlying most formal systems for mathematical reasoning. Additionally, PPP has strong connections to other areas such as the theory of lattices and cryptography [Jer16, BJP+ 19, SZZ18, HV21], extremal combinatorics [BFH+ 23, PPY23], and propositional proof
complexity [BCE+ 98, BM04, BJ12].
Despite the prominent role of PPP, it seems to lack certain robustness properties that all other natural
TFNP classes enjoy. A prominent example of such a property is closure under Turing reductions. (A TFNP
class C is closed under Turing reductions if any problem polynomial-time reducible to C via multiple calls
to a problem in C is also polynomial-time reducible to a single call to C.) The classical TFNP classes
are typically defined using closure under many-one reductions, although, the original family of black-box
separations between these classes, proved by [BCE+ 98], already hold for the Turing closed variants. The
later work of Buss and Johnson [BJ12] asked whether these classical TFNP classes are closed under Turing
reductions.They proved that four of the five original TFNP classes PPA, PPAD, PPADS, and PLS are closed
under Turing reductions, and they constructed an artificial TFNP subclass that was not Turing closed in theblack-box setting. Subsequently, with the exception of PPP, all other natural TFNP classes (e.g., CLS) havebeen shown to be Turing closed. Thus PPP stands as the only natural TFNP class not known to be Turingclosed.
The Turing closure of PPP is not only interesting from a structural point of view, but is also connected
to other questions. First, our understanding of the relative complexity of other important TFNP problems
connected to PPP has been murky, largely due to the absence of a technique for showing that PPP is closed
under multiple calls. For example, in a recent work, Sotiraki, Zampetakis, and Zirdelis [SZZ18] showedthat several problems on lattices are Turing reducible to P IGEON (but, notably, not many-one reducible),
including the fundamental n-SVP problem underlying lattice-based cryptography. Another well-studiedclass of problems related to PPP comes from extremal combinatorics. Problems such as Ramsey’s theorem
and the Sunflower Theorem are also proven via iterated applications of the pigeonhole principle; but again
it is unknown if these problems are reducible to a single instance of PPP. (See Section 1.2 for references
and more on these connections.)1

Secondly, the distinction between many-one and Turing reductions is sometimes important, as it relates
to the circuit depth of the reduction. For example, an important result in cryptography shows the existenceof PRGs in NC0 (assuming there are one-way functions in NC1 ) [AIK04]. However the stretch of their
PRGs is sublinear, and known methods to increase the stretch require iterated applications of a version of
the pigeonhole principle. It is an important open question whether or not PRGs with polynomial stretch
exist in NC0 ; for example [JLS21] show that such constructions imply indistinguishability obsfucation.
Thirdly, the Turing closure of PPP has important implications in proof complexity. A body of recent
work in the intersection of complexity theory and proof complexity has linked natural TFNP classes to natural propositional proof systems (e.g., [BIK+ 94, GHJ+ 22, DR23, BFI23].) This in turn has vastly increased
our toolkit for proving black-box separations for TFNP classes, and also raised many new questions. Onceagain the glaring outlier is PPP, which is the only natural TFNP class that lacks an equivalant characterization by a natural proof system. Indeed, we suspect that this again can be attributed to the lack of robustnessof the TFNP class PPP, and thus understanding the Turing closure question for PPP (equivalently, whether
or not PPP equals FPPPP ) is a step towards understanding this phenomena.
Recently, the question of the Turing-closure of PPP was highlighted in Daskalakis’ IMU Abacus Medal
Lecture [Das19, Open Question 7], with a tighter characterization of the complexity of n-SVP singled out
as one notable application. Buss and Johnson [BJ12] openly conjectured that PPP ̸= FPPPP , and they ask
whether it is possible to provide evidence for this conjecture via a black-box separation.
Open Problem 1. [BJ12, Das19] Can we provide black-box separations between PPP and FPPPP ?

1.1

Main Results and Technical Highlights

The main contribution of this work is to provide the first complexity-theoretic evidence for the separations
between PPP and FPPPP . We work in the black-box setting, where the input to P IGEON is presented as a
black-box oracle which we can query, instead of as a boolean circuit (see Section 2 for formal definitions).
Our main result is a black-box separation between PPP and FPPPP , resolving the open problem above.
Theorem 1.2. PPP is not Turing-closed in the black-box setting.
We note that in the land of TFNP, all currently known inclusion results hold in the black-box setting.
This means that black-box separations are significant since they rule out all existing techniques for proving
inclusions.
We prove Theorem 1.2 by giving a black-box separation between the P IGEON problem, and following
P IGEON ⊗ P IGEON problem:
Definition 1.3. The P IGEON ⊗ P IGEON problem, also denoted P IGEON⊗2 , is defined as follows. The input
is two boolean circuits C1 , C2 , both encoding functions from {0, 1}n → {0, 1}n . The output is a solutionof P IGEON on both C1 and on C2 .
Theorem 1.4. P IGEON⊗2 is not black-box reducible to P IGEON.
In other words we show that one cannot efficiently reduce, in a black-box way, solving two independent
instances of P IGEON to one instance of P IGEON. Since P IGEON⊗2 is easily observed to be contained in
FPPPP — just call the P IGEON oracle twice — Theorem 1.2 follows.
We first remark that our result shows something stronger. Namely, it shows that PPP is not even nonadaptively Turing closed in the black-box setting, where the non-adaptive Turing closure is where one isallowed to ask multiple queries to the P IGEON oracle in parallel, as opposed to sequentially. Recall that in
the closely related W EAK -P IGEON problem — the defining problem for the class PWPP — we seek to find acollision in a map from 2n+1 pigeons to 2n holes, rather than 2n pigeons to 2n −1 holes. Contra to our above2

result, Jeřábek showed that PWPP is non-adaptively Turing closed and so, in particular, W EAK -P IGEON⊗2
many-one reduces to W EAK -P IGEON [Jer16]. Thus our result further distinguishes P IGEON and PPP fromW EAK -P IGEON and PWPP.
Our techniques can be used to prove more than just the above separation. Let P IGEONM
N for M > N
denote the problem of finding a collision in a map from M pigeons to N holes. For example, if N = 2n , then2N
we can write P IGEON = P IGEONN
N −1 and W EAK -P IGEON = P IGEON N in this notation. As an immediate
corollary, we can prove the following strengthening of the above result:+N
Theorem 1.5. Let 0 < ε < 1 be a universal constant. Then P IGEONN
N
N
black-box reducible to P IGEONN −1 .

1−ε

N +N
⊗ P IGEONN

1−ε

is not1−ε+1+NProof. We prove that P IGEONN
is black-box reducible1 to P IGEONN. This immediately implies
N
N
1−ε
N +1
N +1
N +N
N +N 1−εthat P IGEONN ⊗ P IGEONN reduces to P IGEONN⊗ P IGEONN, and so if the latter problem+1
reduces to P IGEONN
thenwecontradict
ourmaintheorem.
N+1
Our reduction is straightforward. Given an instance f of P IGEONN, create c = N 1/ε−1 = N (1/ε)(1−ε)
N
(1)
(2)
(c)
parallel copies of the instance f , f , · · · , f that share the hole 0 but otherwise are independent. Reparametrize by setting M = N 1/ε , and the result of this reduction is an instance ofc(N +1)

P IGEONcN

1/ε

+N
cN +c
= P IGEONN= P IGEONcN
N 1/ε(1/ε)(1−ε)+M= P IGEONM
M

1−ε

,

+1
instance.
and any solution of this new instance can be used to recover a solution to the original P IGEONN
N
Finally, since ε < 1 is a universal constant, we note that M = N 1/ε incurs just a polynomial-size blowup in
the instance.

Since W EAK -P IGEON⊗2 ∈ PPP, this result implies that when we slowly increase the ratio of pigeons
to holes, a “phase-transition” happens once we reach mapping Θ(N ) pigeons to N holes, where suddenly
the non-adaptive problem switches from being “hard” for PPP to being contained in PWPP. (We notethat this aligns with the bounded-depth proof complexity of the pigeonhole principle, where a similar phasetransition occurs.)
We can also use our lower bound for P IGEON⊗2 to prove a hierarchy result, showing that having k nonadaptive queries to P IGEON is more powerful than k − 1 non-adaptive queries. Formally, let P IGEON⊗kdenote the natural generalization of P IGEON⊗2 to k copies of P IGEON, where the goal is to output k solutions. Clearly P IGEON⊗k−1 reduces to P IGEON⊗k , since we can just embed a fixed solution on the extra
copy of P IGEON⊗k . Complementing this, we have the following:
Theorem 1.6. For all constant k, P IGEON⊗k is not black-box reducible to P IGEON⊗k−1 .
The above hierarchy theorem follows from using our main technical theorem (Theorem 4.15) as a basecase in an inductive argument. It is not clear how to deduce the previous hierarchy theorem immediatelyfrom Theorem 1.4 via an inductive argument — it appears that our stronger lower-bound technique is neededin order to make the induction work.
Technical Overview. The tools we use to prove the above separations are developed from lower-boundtools in propositional proof complexity. Propositional proof complexity has a very close relationship to
TFNP, as each of the defining problems for TFNP subclasses correspond to existence theorems: that is,
tautologies of the form ∀x∃yϕ(x, y), where ϕ is a polynomial-time computable predicate. Indeed, the complexity and relative relationships between TFNP subclasses are intimately related to the relative provabilityof the existence principles defining the classes [BIK+ 94, Mor01, BM04, BJ12].
1

Our original proof of this theorem used the techniques from Section 4 in a direct argument. We thank Jiawei Li for pointing
out this simplified proof.

3

A recent line of work has tightened these connections further, by showing actual equivalences between black-box TFNP subclasses and propositional proof systems [BJ12,GKRS18,GHJ+ 22,DR23,BFI23].
Roughly speaking, these results show that for many natural TFNP classes C, there is an associated natural
proof system, PC such that the following statement holds:
A total search problem R is contained in the (black-box) TFNP subclass C
if and only if
A propositional encoding of the totality of R can be efficiently proved in PC .
This generic connection often allows us to reduce the problem of proving black-box separations to thealready-tackled problem of proving a separation between the corresponding proof systems2 . Indeed, thisstrategy has been used effectively to provide oracle separations between nearly all of the classical TFNP
classes [BIK+ 94, GHJ+ 22].
Unfortunately, we cannot appeal directly to a proof complexity separation to black-box separate P IGEON
and P IGEON⊗2 , since as mentioned in the Introduction, there is no natural proof system corresponding to
PPP. Nonetheless, we are able to bypass this issue, and our main technical contribution is the development of new tools to prove lower bounds against black-box PPP directly, without needing to appeal to thecorresponding proof system.
Our new tools are still directly inspired from proof complexity methods, and so we believe that they
may be of independent interest. The starting place for our lower bound is the observation that the proof
theoretic strength of the pigeonhole principle sits between the well-studied semi-algebraic proof systems
Sherali-Adams (SA) and Sums-of-Squares (SOS). The theory of lower bounds in SA and SOS are welldeveloped: SA proof complexity is characterized by the so-called family of pseudo-expectation operators
and SOS complexity (which is strictly stronger than SA) is characterized by the stronger family of positive semi-definite pseudo-expectations [FKP19]. It is well-known that the pigeonhole principle (underlying
P IGEON) requires large SA proofs, and [GM08] give a lower bound by explicitly constructing a pseudoexpectation operator for P IGEON. On the other hand, SOS has short proofs of both (the totality of) P IGEON
and P IGEON⊗2 (cf. Appendix A). Therefore, both PPP and PPP ⊗ PPP are bracketed above and below by
two proof systems that are characterized by pseudo-expecatation operators: SA is “too weak” since it cannot
efficiently certify either PPP or PPP ⊗ PPP, and SOS is “too strong” since it can efficiently certify both
PPP and PPP ⊗ PPP.
This suggests the following question:
Is there a variant of pseudoexpectation operators, intermediate in strength between standard
pseudoexpectations and PSD pseudoexpectations, which imply lower bounds for black-box PPP?
We show that the answer to this question is “Yes”!
In Section 3, we introduce and develop a new variant of pseudoexpectation operators that are tailored toproving lower bounds against black-box PPP — we call these collision-free pseudoexpectation operators.
Importantly, such operators are not automatically PSD pseudoexpectations, and thus do not imply lower
bounds for SOS proofs. We then prove Theorem 1.4 by constructing a collision-free pseudoexpectation
operator for the P IGEON⊗2 problem (cf. Section 4). While the particular pseudoexpectation operator that
we choose for P IGEON⊗2 is natural — it is an obvious generalization of the pseudoexpectation for P IGEON— proving that it is collision-free requires a delicate and technical proof, combining methods developedin the theory of pseudoexpectations and also in the theory of lower bounds for bounded-depth Frege (particularly, the use of matching decision trees). Indeed, this makes some sense as the particular black-box
2

A recent paper of Buss, Fleming and Impagliazzo [BFI23] shows that this equivalence is general: for any syntactic TFNP class,there is always a corresponding proof system satisfying the above property. However, the proof system may in general not be onethat is natural or that has already been defined.

4

separation we are trying to prove is very thin, being between two problems that are very close in complexity.
To see this, observe that the P IGEON problem by itself cannot admit a collision-free pseudoexpectation (ofcourse). However, neither can the problem W EAK -P IGEON ⊗ W EAK -P IGEON, due to the result of Jeřábek
showing W EAK -P IGEON ⊗ W EAK -P IGEON ∈ PWPP ⊆ PPP [Jer16]. In our view, this makes the separation P IGEON⊗2 ̸∈ PPP, and its generalization to N + N 1−ε pigeons (Theorem 1.5), quite interesting andsurprising.
We believe that these new notions of pseudoexpectations may help us develop an enriched set of tools
for constructing dual certificates that generalize the standard pseudoexpectations needed for refutational
SA (SOS) lower bounds. For example, a key tool for proving lower bounds on the extension complexityof approximation algorithms is via lifting lower bounds for a implicational versions of SA and SOS (e.g.,[CLRS13, LRS15, KMR17]). Lower bounds for implicational SA are harder than proving lower bounds
for SA refutations, and thus the pseudoexpectation properties required here are more demanding. Anotherexample are black-box lower bounds for pseudodeterministic algorithms for NP search problems. These canbe proven from degree lower bounds for a certain generalization of SA proofs, whose dual certificate again
requires a strengthening of the definition of SA pseudoexpectations [GIPS21].
We refer to Section 3 for a formal discussion of the new type of pseudoexpectation operator, and to
Section 4 for a technical overview of our lower bound for P IGEON⊗2 .

1.2

Related Work

Cryptography and PPP. In the original paper that introduced the class PPP, Papadimitriou already observed that an efficient algorithm for P IGEON would allow the inversion of any one-way permutation [Pap94,
Proposition 3]. This original observation predicted an entire host of results connecting the complexity of
PPP to the hardness of various cryptographic primitives in cryptography. A later result by Jeřábek [Jer16]
showed that FACTORING is reducible in randomized polynomial-time to P IGEON, and even to its weakervariant W EAK -P IGEON (defined above).
Later works have connected the complexity of PPP to other fundamental cryptographic primitives. Workby Hubáček and Václavek [HV21] showed that various versions of the fundamental discrete logarithm problem were PWPP- and PPP-complete. Another central recent work by Sotiraki, Zampetakis, and Zirdelis[SZZ18] showed fundamental connections between PPP and PWPP, collision-resistant hash functions, andthe hardness of various problems on lattices. (Indeed, the connection to collision-resistant hash functions
is embodied by the very definition of the W EAK -P IGEON problem: we are given a contracting map fromn + 1 bits to n bits computed by a polynomial-size circuit, and the goal is to find two input strings mappingto the same output string.) The hardness of various lattice problems have been foundational to many cryptographic constructions since the seminal work of Ajtai [Ajt96]. Sotiraki, Zampetakis, and Zirdelis showthat B LICHFELDT, a computational problem on lattices closely related to Blichfeldt’s theorem on lattices[Bli14], is PPP-Complete. Using this problem, they were able to show that several notable problems on
lattices are Turing reducible to P IGEON (but, notably, not many-one reducible). This includes the problem
n-SVP of approximating the shortest vector within a lattice to a factor of n, the hardness of which is foundational to lattice-based cryptography [Reg05]. Indeed, locating the n-SVP question into a natural complexity
class is an important open question, and the Turing closure FPPPP is the best current upper bound on its
complexity.
Extremal Combinatorics and PPP. In the class FPPPP , we get to use a P IGEON oracle to solve ourproblems of interest, and of course later queries to the P IGEON oracle can depend on the responses to earlier
queries. There are, however, other ways to employ the pigeonhole principle iteratively, and many such
examples come from extremal combinatorics. The prototypical example is in the standard proof of Ramsey’s
Theorem, which states that any graph on 22n vertices either has a clique of size n or an independent set of5

size n. This proof involves an iterated application of the pigeonhole principle in the following sense: wefirst pick an arbitrary node u, and then choose the next node from whichever set is larger: either the nodes
adjacent to u, or the nodes not adjacent to u. Repeating this process for 2n steps yields a sequence of 2nnodes, and now we can see that among these 2n nodes there is either a clique of size n or an independent setof size n. Indeed, one can easily turn Ramsey’s Theorem into a computational problem, denoted R AMSEY,
where we are given an encoding of a graph on 22n nodes by a polynomial-size circuit C and must output an
independent set or clique on the graph. We note that it is currently an open question whether or not R AMSEY
reduces to P IGEON, although, it is known that W EAK -P IGEON reduces to R AMSEY, both under randomized
reductions [KNY19], and also deterministically to a multicoloured version [KNY19, PPY23]. However, forthe converse direction, it is not at all clear how to simulate the above proof of Ramsey’s theorem inside PPP— in fact, it is not even clear whether or not R AMSEY ∈ FPPPP !
To address this problem, Pasarkar, Papadimitriou, and Yannakakis [PPY23] introduced a new TFNP
subclass that they called PLC (other work relating PPP to extremal combinatorics appeared concurrently by
Bourneuf et al [BFH+ 23]). The defining problem of PLC is L ONG -C HOICE, which embodies the kind of
iterated application of the pigeonhole principle seen in the proof of Ramsey’s Theorem. They proved that
PLC ⊇ PPP, and also that it contains other interesting search problems related to extremal combinatorics
not known to lie in PPP. Two such examples of problems that lie in PLC include R AMSEY, which we havealready discussed, and S UNFLOWER, which is a computational analogue of the famous Sunflower Lemma[ER60]. One of the main open problems suggested by Pasarkar, Papadimitriou, and Yannakakis is to giveany complexity theoretic evidence — such as a black-box separation — showing that PLC and PPP are
distinct classes [PPY23], and thus that “sequential” applications of the pigeonhole principle, in this othersense, are stronger than a “single” application of the pigeonhole principle. In a concurrent work (discussed
more below), Jain, Li, Robere, and Xun used similar techniques as in the present paper to separate R AMSEY
and L ONG -C HOICE from PPP [JLRX23].
Propositional proof complexity, bounded arithmetic, and PPP. The theory of propositional proof complexity also has many close ties with TFNP, and particularly with the P IGEON problem. As we have alreadymentioned above, each of the defining search problems for the TFNP subclasses naturally correspond toexistence theorems: theorems that can be written in the form ∀x∃yϕ(x, y). Of course, the existence theorem corresponding to the P IGEON problem is — what else — the pigeonhole principle. The pigeonhole
principle is perhaps the most well-studied tautology in all of propositional proof complexity, as it provides adifficult example for many propositional proof systems under common study [Hak85,Ajt88,BIK+ 92,Raz98,
Raz01]. The pigeonhole principle lower bounds are also closely related to independence results in theories
of bounded arithmetic [Ajt88].
There have been several works which formalize the three-way connections between proof complexity,
TFNP, and first-order logic, some of which are important to mention. Buss and Krajı́ček showed that the
total functions computable in the TFNP class PLS are exactly the witnessing functions for the boundedarithmetic theory T21 [BK94]. Buresh-Oppenheim and Morioka gave a framework for defining syntactic
TFNP subclasses using existentially quantified first-order formulas [BM04]. For an example, consider thefollowing existential first-order formula:∃x, y : f (x) = 0 ∨ (x ̸= y ∧ f (x) = f (y)).
This formula states that either f (x) = 0, or there is a y ̸= x such that f (x) = f (y) — that is, it encodes thepigeonhole principle. Buresh-Oppenheim and Morioka showed how to turn any such existential sentence
ϕ into a defining problem Qϕ for a corresponding syntactic TFNP subclass. Moreover, they showed thatgiven two such formulas ϕ, ψ, if the corresponding problems Qϕ many-one reduces to Qψ , then certain
propositional encodings of the totality of ϕ can be deduced from the totality of ψ. Their results were6

improved by the work of Buss and Johnson [BJ12], who strengthened this correspondence in two ways: first,
they improved many-one reducibility to Turing reducibility, and second, they strengthened the implication
to an equivalence. In other words, Buss and Johnson showed that Qϕ is Turing reducible to Qψ if andonly if the propositional encoding of ϕ is provable from ψ in a certain proof system. By the results ofBuss and Johnson, one can therefore use our work to show that it is impossible to prove the totality of
P IGEON ⊗ P IGEON from the totality of P IGEON in a particular proof system. We refer an interested reader
to [BJ12] for the details.
Comparison with the work of Jain, Li, Robere, and Xun [JLRX23]. A concurrently appearing workof Jain, Li, Robere, and Xun generalizes the collision-free pseudoexpectation operators that are introduced
here. They use this generalization to obtain lower bounds for a hierarchy of classes above PPP called
the “Pecking Order”. The emblematic class for level t of the Pecking Order is t-P IGEON, where we are
given a mapping from (t − 1)n + 1 pigeons to n holes, and the goal is to find a hole containing t pigeons(note P IGEON = 2-P IGEON in this notation). The lower bounds shown by Jain, Li, Robere, and Xun are
orthogonal to the lower bounds in the present paper. For instance, they use their generalized collisionfree pseudoexpectation operators to show that, in the black-box setting, R AMSEY ̸∈ PPP, and also that
UPLC ̸⊆ PPP, where UPLC ⊆ PLC is the “unary” variant of the PLC class introduced above [PPY23]. We
note that our lower bound for P IGEON⊗2 in Theorem 1.4 gives an alternate proof of black-box separation
PLC ̸⊆ PPP, since P IGEON⊗2 is easily verified to be in PLC.

1.3

Paper Organization

The rest of the paper is organized as follows. In Section 2, we introduce some necessary technical preliminaries for black-box TFNP, as well as show that P IGEON⊗2 is contained in both PLC and FPPPP . In
Section 3, we develop our new lower bound tool of collision-free pseudoexpectations in a general setting.
Then, in Section 4, we prove Theorem 1.2 and Theorem 1.5. Finally, in Section 5 we prove generalizationsof our main theorem (Theorems 1.5 and 1.6).

2

Preliminaries on Black-Box TFNP

A relation R ⊆ {0, 1}∗ × {0, 1}∗ is total if for all x ∈ {0, 1}∗ there is a y ∈ {0, 1}∗ such that R(x, y)holds. Each total relation corresponds to a total search problem in the natural way: given x as input,
output any y such that R(x, y) holds. In the classical theory of TFNP, we are interested in the total search
problems defined from polynomial-time computable, polynomially-bounded total relations R. The total
search problems of particular interest in this paper are related to the pigeonhole principle, whose definition
we again recall.
Definition 2.1. The P IGEON problem is defined as follows. The input is a boolean circuit C encoding afunction from {0, 1}n → {0, 1}n . The output is either any x ∈ {0, 1}n such that C(x) = 0n , or, any two
strings x ̸= y ∈ {0, 1}n such that C(x) = C(y).
The class of search problems polynomial-time mapping reducible to P IGEON is called PPP, and is oneof the central classes of study in the theory of TFNP. In this paper, we will be interested in the following
generalization of the P IGEON problem.
Definition 2.2. The P IGEON ⊗ P IGEON problem, also denoted P IGEON⊗2 , is defined as follows. The input
is two boolean circuits C1 , C2 , both encoding functions from {0, 1}n → {0, 1}n . The output is a solutionof P IGEON on both C1 and on C2 .

7

Figure 1: An instance of P IGEON⊗2 . A solution (1, 3, 4) is indicated by the red edges; in the left P IGEONinstance, pigeons 1 and 3 collide in the same hole, while in the right P IGEON-instance, pigeon 4 maps to theforbidden 0-hole.

It is clear that P IGEON⊗2 lies in the class FPPPP . This is because, given an instance (C1 , C2 ) of
P IGEON⊗2 , we can use the PPP oracle to solve each instance separately, and then output both solutions. The
main goal of this paper is to give evidence that P IGEON⊗2 does not lie in PPP. We do this by proving lower
bounds for P IGEON⊗2 in the black-box model. For this, we must introduce some preliminaries regarding theblack-box model of TFNP.
As defined above, the input to the P IGEON problem is a function f : {0, 1}n → {0, 1}n encoded by apolynomial-size circuit. In the black-box setting, we instead presume that the input function f is given by
an oracle, which we are allowed to query, but cannot investigate the actual computation of the function f .
Definition 2.3. A total (query) search problem is a sequence of relations R := {Rn ⊆ {0, 1}n × On }n ,where On are finite sets, such that ∀x ∈ {0, 1}n ∃o ∈ On : Rn (x, o). A total search problem R is in
TFNPdt if for each o ∈ On there is a poly(log(n))-depth decision tree To such that for all x ∈ {0, 1}n ,To (x) = 1 iff (x, o) ∈ Rn .
It will be convenient to think of the input as being encoded over a broader domain, such as [n]. For
example, when considering the P IGEON problem, it is natural to think of the input as being encoded by afunction f : [n + 1] → [n + 1]. We can do this by encoding each of the inputs in binary in the naturalway, and this changes the complexity of the reductions in this paper by no more than a O(log n) factor.
Furthermore, it will also often be convenient to refer to a single relation Rn in the sequence R. In an abuseof notation, we refer to Rn as a “total search problem”. We will also allow the inputs to Rn to have nO(1)input bits for notational convenience.
With these remarks in mind, we denote by P IGEONdt and (P IGEON⊗2 )dt the query variants of the
P IGEON and P IGEON⊗2 problems, respectively. The input to P IGEONdt
n is a function f : [n + 1] → [n + 1],
and the goal is to output either (1) any input i such that f (i) = 1, or any i ̸= j such that f (i) = f (j)(the input to (P IGEON⊗2 )dt is defined similarly). Formally speaking, the input to P IGEONdt
n is encoded by aboolean string of length O(n log n), which encodes n + 1 “pointers” of pigeons to holes, each of O(log n)bits each. We will elide this formal low-level encoding, and presume that the query algorithms will always
query entire pointers f (i).
We now introduce the definition of a (many-one) reduction in the black-box model.
Definition 2.4. Let R ⊆ {0, 1}n × OR and S ⊆ {0, 1}m × OS be total search problems. An S-formulationof R is a decision-tree reduction (fi , go )i∈[m],o∈OS from R to S. Formally, for each i ∈ [m] and o ∈ OS
there are functions fi : {0, 1}n → {0, 1} and go : {0, 1}n → OR such that(x, go (x)) ∈ R ⇐= (f (x), o) ∈ S
8where f (x) ∈ {0, 1}m is the string whose ith bit is fi (x). The depth of the reduction is
d := max {D(fi ) : i ∈ [m]} ∪ {D(go ) : o ∈ OS } ,where D(h) denotes the decision-tree depth of h. The size of the reduction is m, the number of input bits to
S. The complexity of the reduction is log m + d. We write S dt (R) to denote the minimum complexity of an
S-formulation of R.
We extend these notations to sequences in the natural way. If R is a single search problem and S = (Sm )dt (R) over all m. If R = (R )is a sequence of search problems, then we denote by Sdt (R) the minimum of Smndtdt
is also a sequence, then we denote by S (R) the function n 7→ S (Rn ).
We denote by PPPdt the class of all total search problems which admit poly(log(n))-complexity P IGEONdt formulations. In general, we will prove that problems do not black-box reduce to P IGEON by proving that
low-complexity P IGEON-formulations do not exist. This connection was first noted (using the language of“Type-2 Complexity”) by [BCE+ 98].

3

Collision-Free Pseudoexpectations

In this section we introduce our new lower-bound technique for PPPdt using pseudoexpectation operators.
We develop our technique in a general setting, as we believe it may be of independent interest.
We must introduce some notation and also recall some of the theory of multilinear polynomials. All
polynomials in this paper will have real coefficients. A polynomial p ∈ R[x1 , . . . , xn ] is multilinear if theindividual degree of any variable in p is at most 1. The algebra of multilinear polynomials is that of thequotient ring R[x1 , . . . , xn ]/⟨x2i − xi ⟩ni=1 . More concretely, we can define the multiplication of two multilinear polynomials as follows: the multilinear polynomial pq is obtained from the multilinear polynomials p
and q by multiplying p and q using standard polynomial multiplication, and then lowering the degree of all
variables appearing in pq to 1. For instance, (xy + z) · (xz) = xyz + xz, as multilinear polynomials. We
will always be operating with multilinear polynomials, and presume that all operations are done over thisquotient ring.
Let Rn ⊆ {0, 1}n × O be a query total search problem in TFNPdt , and let x1 , x2 , . . . , xn denote the ninput bits to Rn . A conjunction C is a conjunction of boolean literals over x1 , . . . , xn . It will be particularly
convenient to think of a conjunction C as a multilinear polynomial over these variables. For instance, we
can encode the conjunction x ∧ y ∧ z as the polynomial x(1 − y)z, which takes the same values as the
conjunction over {0, 1}. The degree of a conjunction C, denoted deg(C), is the number of literals occurringin it. Two conjunctions C1 , C2 are consistent if C1 C2 ̸= 0, and an input x ∈ {0, 1}n is consistent with
C if C(x) = 1. A conjunction C witnesses the solution o ∈ O to Rn if for all x ∈ Rn consistent withC, (x, o) ∈ Rn . We write Rn ↾ C ⊆ {0, 1}n−deg(C) × O to denote the new search problem obtained by
restricting the appropriate input bits to R according to the literals in C.
Definition 3.1. Let Pn,d denote the collection of all degree-d real-coefficient multilinear polynomials overthe variables x1 , x2 , . . . , xn . A degree-d pseudoexpectation operator is a function Ẽ : Pn,d → R satisfying
the following properties:− Linearity. Ẽ[αp + βq] = αẼ[p] + β Ẽ[q] for all α, β ∈ R and all p, q ∈ Pn,d .
− Normalized. Ẽ[1] = 1.
− Nonnegativity. For every degree ≤ d conjunction C, Ẽ[C] ≥ 0.
Let R ⊆ {0, 1}n × O be any total query search problem. We say that Ẽ is a pseudoexpectation for R if, inaddition to the above three properties, it satisfies the following additional property:9

− R-Nonwitnessing. Ẽ[C] = 0, for any degree ≤ d conjunction C witnessing a solution to R.
Pseudoexpectation operators were originally introduced to prove lower bounds on Sherali-Adams degree, and a stronger pseudoexpectation operator was introduced to prove lower bounds for Sums-of-Squares
degree. The standard method to construct pseudoexpectation operators is through the use of pseudodistributions, the definition of which we recall next.
Definition 3.2. Let x1 , . . . , xn be a set of boolean variables, and let d be a positive integer. A degree-d
pseudodistribution over these variables is a family of probability distributions
D = {DS : S ⊆ [n], |S| ≤ d} ,such that the following properties hold:− For each set S ⊆ [n], |S| ≤ d, DS is supported on {0, 1}S , interpreted as boolean assignments tovariables in {xi : i ∈ S}.
B for B ⊆ A is the− For each S, T ⊆ [n], |S|, |T | ≤ d, we have DSS∩T = DTS∩T = DS∩T , where DA
marginal distribution of A to variables indexed by B.
Let R ⊆ {0, 1}n × O be any query total search problem. Then D is a pseudodistribution for R if for every
degree ≤ d conjunction C witnessing a solution to R, no distribution DS in D is supported on a consistentassignment for C.
In other words, a pseudodistribution is an object that “looks like” a probability distribution to an external
adversary that can only investigate marginals of up to d bits, but, the distribution is not supported on any
assignment that witnesses a solution to R. The following lemma is standard.
Lemma 3.3 ([FKP19]). Suppose D is a degree-d pseudodistribution over x1 , . . . , xn for R ⊆ {0, 1}n × O.
The operator Ẽ : Pn,d → R defined by"#YẼxi = Pr [∀i ∈ S : xi = yi ]
i∈S

y∼DS

and extended to all of Pn,d by linearity is a degree-d pseudoexpectation for R ⊆ {0, 1}n × O.
In fact, the two objects are equivalent, but we will only need the above direction of this equivalence inthe current work.
We now introduce our new variant of pseudoexpectation operators that are tuned to proving lower bounds
for PPPdt -formulations. This definition must be stronger than the definition of a standard pseudoexpectation, since standard pseudoexpectations prove lower bounds for the Sherali-Adams hierarchy, and it is
known that P IGEONdt is hard for Sherali-Adams. However, this definition must be weaker than the positive
semidefinite pseudoexpectations that imply lower bounds for the SOS hierarchy, since one can show thatboth P IGEONdt and (P IGEON⊗2 )dt are easy for the SOS hierarchy (see Appendix A). We need one more
auxiliary definition before we can define our new variant of a pseudoexpectation operator.
Definition 3.4. Let R ⊆ {0, 1}n × O be a query total search problem, and let F be a family of conjunctions
over x1 , . . . , xn . The family F is d-pairwise witnessing for R if no conjunction in F witnesses a solution
for R, but, for any pair of conjunctions C1 ̸= C2 ∈ F, either C1 C2 ≡ 0 or R ↾ C1 C2 has decision treecomplexity at most d.
In other words, for any pair of consistent conjunctions C1 , C2 in a 2-witnessing family, restricting R by
C1 C2 makes the search problem efficiently solvable.
10Definition 3.5. Let R ⊆ {0, 1}n × O be a total query search problem, and let d be a positive integer. Let Ẽ
be a degree D ≥ d pseudoexpectation for R. The operator Ẽ is d-collision-free if it satisfies the following
property:X− Collision Freedom.
Ẽ[C] ≤ 1 for every d-pairwise witnessing F of degree ≤ d conjunctions.
C∈F

As we show next, this notion of “collision-freedom” is strong enough to prove lower bounds against
P IGEONdt -formulations, and therefore against PPPdt .
Theorem 3.6. Let R ⊆ {0, 1}n × O be a total query search problem, and let d be a positive integer. If Ẽ
is a degree D ≥ 2d, d-collision-free pseudoexpectation for R, then there is no P IGEONdt -formulation of R
with complexity ≤ d.
Proof. Suppose there is a P IGEONdt
N -formulation of R with complexity at most d. For each pigeon i =1, 2, . . . , N , we have a decision tree Ti which queries at most d input bits of R and outputs some holeTi (x) ∈ [N ] for the pigeon i. For any depth ≤ d decision tree T querying bits of R, let L(T ) denote theleaves of T , and for any leaf ℓ ∈ L(T ) let Cℓ denote the conjunction of literals on the path to ℓ.
We begin by doing some pre-processing on the P IGEONdt
N formulation in order to put 0-weight on paths
which map a pigeon to the forbidden hole 1. Suppose that ℓ ∈ L(Ti ) is any leaf of the pigeon tree Ti labelledwith 1. Let gi,1 : {0, 1}n → O be the decision tree defined by the formulation that maps the solution i 7→ 1
of P IGEONdt to a solution of R. For each i and for each such leaf ℓ ∈ Ti , replace the leaf ℓ with a copyof gi,1 (removing redundant queries when necessary in the subtree), and label each leaf of the new subtreewith 1. It is clear that this new formulation has depth at most 2d instead of d. Furthermore, for any leaf ℓlabelled with 1 in this new formulation, the correctness of the original formulation implies that Cℓ witnesses
a solution to R, and therefore Ẽ[Cℓ ] = 0.
We first claim thatX
Cℓ = 1,ℓ∈L(T )

where the equation is between polynomials, for any decision tree T . This can be seen by an easy induction
on the depth of T . If the depth of T is 0, then the conjunction Cℓ is empty, and thus Cℓ = 1. Inductively,
consider the root node u of T . Suppose that u queries the variable xi , and when xi is 0 it proceeds tothe subtree T0 , and when xi is 1 it proceeds to the subtree T1 . The claim follows by a straightforward
calculation:
X
X
X
Cℓ =
(1 − xi )Cℓ +x i Cℓℓ∈L(T )ℓ∈L(T0 )= (1 − xi )ℓ∈L(T1 )Xℓ∈L(T0 )Cℓ + x i

X

Cℓℓ∈L(T1 )= (1 − xi ) + xi
= 1,
where the third equality is by the inductive hypothesis. The claim immediately impliesby the linearity and normalization of Ẽ.
Now, for each j = 1, 2, 3, . . . , N , define the set of conjunctions
Hj :=

N
[

{C : C = Cℓ for some j-labelled leaf ℓ ∈ L(Ti )} .

i=1

11

P

ℓ∈L(T ) Ẽ[Cℓ ] = 1

First, observe thatN
X
X

Ẽ[Cℓ ] =i=1 ℓ∈L(Ti )N X
XẼ[C],

j=1 C∈Hj

since each conjunction on a root-to-leaf path in Ti is mapped to exactly one set Hj . Second, by the preprocessing step above, we know that for every conjunction C ∈ H1 , we have Ẽ[C] = 0, since each such C
must be witnessing for R. Finally, we claim that for j = 2, 3, . . . , N , the family Hj is d-pairwise witnessing.
To see this, consider any two conjunctions C1 ̸= C2 ∈ Hj that are consistent. These two conjunctions musthave come from different decision trees Ti , Tj , since all conjunctions coming from the same decision tree areinconsistent. But then, by the correctness of the P IGEONdt -formulation, it follows that pigeons i and j aremapped to the same hole under any input x consistent with
PC1 C2 , and therefore we can recover a solution
to R using at most d more queries. Therefore Ẽ[Hj ] := C∈Hj Ẽ[C] ≤ 1, since Ẽ is collision-free. By
Pcombining these three facts together, along with the fact that ℓ∈L(T ) Ẽ[Cℓ ] = 1, we have
N=

N
X
X

Ẽ[Cℓ ] =i=1 ℓ∈L(Ti )N X
XẼ[C] =

j=1 C∈Hj

N X
X

Ẽ[C] ≤ N − 1,

j=2 C∈Hj

which is a contradiction.
Therefore, if we can construct a degree ω(poly(log(n))) collision-free pseudoexpectation for (P IGEON⊗2 )dt ,we will prove our main theorem. The construction of this pseudoexpectation is done in the next section.

4

Lower Bounds for Black-Box PPP

The goal of this section is to prove the following theorem.
Theorem 4.1. (P IGEON⊗2 )dt ̸∈ PPPdt .
We prove the above theorem by constructing a collision-free pseudoexpectation for the P IGEON⊗2 problem. For the remainder of the paper we will now drop the “dt” superscript for notational convenience.

4.1

Constructing a Collision-Free Pseudoexpectation for P IGEON⊗2

In this section, we construct a collision-free pseudoexpectation for P IGEON⊗2 . To do this, we must first set
down some notational preliminaries.
Preliminaries. Throughout this section we will be considering P IGEON⊗2
n , the input of which is twofunctions f, g : [n + 1] → [n + 1] As we discussed above, we will consider these inputs as encoded overthe domain [n + 1] instead of a binary domain for notational convenience. Formally, the input to P IGEON⊗2nwill be two tuples (x, y) ∈ [n + 1]n+1 × [n + 1]n+1 , encoding the two functions f, g, respectively. (We canalways convert to the underlying binary encoding by replacing each xi ∈ [n+1] with O(log n) bits encoding
the value pointed to by xi .) Decision trees querying the input will have their internal nodes querying input
indices (e.g. “xi ”) and outputting values in [n + 1]. Formally speaking, a decision tree querying variables
taking values over [n + 1] is equivalent to a standard binary decision tree that has the guarantee that it always
queries the entirety of a single pointer xi .
In this multivalued framework, a “conjunction” is now a conjunction of atoms of the form Jxi 7→ jK forsome i, j ∈ [n + 1], indicating that pigeon i maps to the hole j. We can convert to the standard polynomial
conjunctions discussed in the above section by employing the binary encoding. Each such conjunction over12the variables of P IGEON⊗2n therefore corresponds to an assignment of some of the pigeons to holes in the
two P IGEON instances comprising the P IGEON⊗2 instance.
Definition 4.2. A matching term M is any conjunction of variables in P IGEON⊗2n that encodes a matchingacross the two underlying P IGEON instances, such that no pigeon is mapped to the hole 1 in either of theinstances. Two matching terms M1 , M2 are consistent if M1 M2 ̸≡ 0 — in other words, if there is no pigeon
that is mapped to two different holes by M1 M2 . Two matching terms M1 , M2 are coherent if M1 M2 is itself
a matching term (i.e. the union of matchings encoded by M1 and M2 form a matching).
In other words, a matching term M encodes an instance that does not witness a collision in either of
the two P IGEON instances. Further note that coherency is a strictly stronger condition than consistency: if
M1 M2 witnesses a collision between two pigeons, then M1 and M2 are consistent as conjunctions, but notcoherent.
We use matchings to define our pseudoexpectation, as follows:
Definition 4.3. The degree-d matching pseudodistribution is defined as follows. Given two sets of pigeons
P1 , P2 from the two instances of P IGEONn comprising P IGEON⊗2n such that |P1 ∪ P2 | ≤ d, the distribution
DP1 ,P2 samples a uniformly random matching from the P1 pigeons to |P1 | holes and the P2 pigeons to |P2 |holes, avoiding the hole 1. Formally, given two matching terms M1 of the P1 pigeons to holes, and M2 ofthe P2 pigeons to holes, the corresponding pseudoexpectation is defined to be|P1 |−1Ẽ[M1 M2 ] :=Y
i=0|P2 |−1
Y
1
1
,
n−i
n−j
j=0

and extended by linearity.
We first prove that this is indeed a pseudodistribution — and thus, by Lemma 3.3, Ẽ is a pseudoexpectation — for P IGEON⊗2n .
Lemma 4.4. For any d ≤ n − 1, the degree-d matching pseudodistribution is a pseudodistribution for
P IGEON⊗2n .
Proof. We first observe that no assignment in the support of the pseudodistribution witnesses a solution
to P IGEON⊗2n , since they are matchings that avoid the hole 1 in both instances of P IGEON . So, we verify
the shared marginals property. Let S = P1 ∪ P2 be any subset
 2of 2pigeons2 with |S| ≤ d − 1 and let
11
1|P1 | = d1 , |P2 | = d2 . Write P1 = p1 , p2 , . . . , pd1 and P2 = p1 , p2 , . . . , pd2 , and let p be any pigeon
not appearing in P1 ∪ P2 . Suppose without loss of generality that p is in the first sub-instance of P IGEON.
Let h11 , . . . , h1d1 , h1 be any set of d1 + 1 distinct holes in [n + 1] \ {1}, and let h21 , . . . , h2d2 be any set of d2
distinct holes in [n + 1] \ {1}. ThenPr

x,y∼DS∪p[(x, y) = (x, y)] = Pr[∀i, j : p1i 7→ h1i ∧ p2j 7→ h2j ∧ p 7→ h1 ] =

d1
Y
i=0

d −1

2
1 Y
1
.
n−i
n−j

j=0

Marginalizing out the pigeon p over each of the possible n − d1 choices for the hole h1 we have
n−d
d1
X1 Y
h1 =1 i=0

d −1

d −1

j=0

i=0

d −1

2
1
2
Y
1 Y
1
1 Y
1
=
n−i
n−j
n−i
n−j

i=0
1
= Pr[∀i, j : pi 7→ h1i ∧ p2j 7→ h2j ]=Pr(x,y)∼DS

and thus the shared marginals property is verified.
13[(x, y) = (x, y)],Throughout the rest of the section, when we use the symbol Ẽ we will always be referring to the matching
pseudodistribution. The rest of the section is devoted to the proof of Theorem 4.1.
Proof of Theorem 4.1.
Proof Outline. We begin by describing the overall strategy of our proof. As we have shown above, thepseudoexpectation Ẽ is indeed a pseudoexpectation for P IGEON⊗2 , and we must show that it is d-collision
free for some suitable choice of d. Formally, the goal is to prove, for any pairwise-witnessing family F, thatX
Ẽ[F] :=
Ẽ[M ] ≤ 1.
M ∈F

To do this, we must analyze pairwise-witnessing families for P IGEON⊗2 . First, we observe that since Ẽplaces 0 weight on any conjunction that witnesses a collision across either sub-instance of P IGEON⊗2 , itfollows that we only need to consider pairwise-witnessing families consisting entirely of matchings. Let
us define a strong pairwise witnessing family to be a pairwise witnessing family satisfying the following stronger conclusion: if M1 ̸= M2 ∈ F are consistent, then M1 M2 must itself witness a solution to
P IGEON⊗2 . The first step of the argument is to reduce to the case where the family is strongly pairwise
witnessing (cf. Lemma 4.5). This reduction is crucial for the next step.
Next, let us fix a strong pairwise witnessing family F, and we seek to show that Ẽ[F] ≤ 1. To prove
this inequality, we will first endow F with “more structure”, as follows: we will find a shallow matchingdecision tree TF that “covers” the weight of the family F, in the sense that Ẽ[F] ≤ Ẽ[TF ] (cf. Lemma 4.12).
A matching decision tree is like a standard decision tree, except, it only describes matchings. The internal
nodes of a matching decision tree are either pigeon queries, where we learn a hole that the pigeon is mapped
to, or hole queries, where we learn which of the remaining pigeons maps to this hole. Each leaf of a matchingdecision tree is labelled with 0 or 1. Letting L1 (TF ) denote the family of matchings corresponding to the
1-leaves of TF , we define Ẽ[TF ] = Ẽ[L1 (TF )]. While we cannot find a matching decision tree TF suchthat L1 (TF ) = F (indeed, such a strong statement is clearly false), we can settle for the weaker goal offinding a shallow matching decision tree that simply covers all of the weight of F. Said another way, thisstep of the proof can be viewed as a second reduction, where now we only need to bound the weight ofstrong pairwise-witnessing families arising from shallow matching decision trees.
The rest of the proof is an analysis of the pseudoexpectation weight of matching decision trees that
describe pairwise-witnessing families. To get an idea of how one can analyze this, it is helpful to think
about how the weight of a matching decision tree evolves “marginally” as it queries pigeons and holes.
Suppose that we have made some queries in our matching decision tree T , and have arrived at a node u witha partial matching M from t pigeons to t holes learned at this point. For the sake of argument, supposethat M only queries pigeons in one of the sub-instances of P IGEON⊗2
n . By definition of the matching−1
pseudoexpectation, in this case Ẽ[M ] = (n(n − 1) · · · (n − t + 1)) . If the node u queries a pigeon pithat can map to n − t remaining holes, then the matching M is extended to n − t matchings, each of weight(n(n − 1) · · · (n − t))−1 . We can see that marginally we have not increased the weight of the pairwise
witnessing family, since the (n − t) new matchings are balanced out by the additional decrease in weightof (n − t)−1 . Thus pigeon queries can safely be “ignored”, at least at this heuristic level, since they “don’t
marginally contribute” to the weight of the family.
Everything changes when we make hole queries, leading us to the crux of the argument. If the node uqueries a hole instead, there are now n − t + 1 possible pigeons that can map to this hole. It follows that thepartial matching M is now replaced with n−t+1 different matchings, each of weight (n(n−1) · · · (n−t))−1 .
We have therefore increased the total weight of the family by a (n − t + 1)/(n − t) = 1 + 1/(n − t)multiplicative factor. Considered by itself, this appears hopeless at first, since we have increased the weight14

of the family beyond 1. It is here that we must use the fact that F is strongly pairwise witnessing. Roughly
speaking, we can show that since F is strongly pairwise witnessing, whenever we make a hole query, mostof the leaves below the hole query must be labelled with 0, compensating for the apparent multiplicative“gain” in the total weight from the hole query (cf. Theorem 4.15). It is natural to try to prove this directly
by somehow arguing about the structure of TF . However, this direct approach seems technically difficult
to implement successfully. Instead, we can avoid this argument by doing a general trick that exploits theshallowness of the matching decision trees. We remark that exploiting the bounded depth via this trick is
the only step of our argument which fails for the weak pigeonhole principle (i.e. where we map 2n pigeons
to n holes), which must happen somewhere since the weak pigeonhole principle is “non-adaptively Turingclosed” [Jer16], as we discussed in the introduction.
Reduction to Strong Pairwise Witnessing Families. We now begin the proof in earnest. First we exhibit
the reduction to strong pairwise witnessing families.
Lemma 4.5. Let n, d be positive integers with d < n/2. Suppose F is d-pairwise witnessing family ofmatching terms, each of degree ≤ d, for P IGEON⊗2
n . Then for any matching terms M1 , M2 such thatM1 M2 ̸≡ 0, M1 M2 witnesses a solution to P IGEON⊗2
n . Equivalently, the decision tree complexity of
P IGEON⊗2
↾
M
M
is
0.
1 2
n
Proof. Let M1 , M2 ∈ F be matchings across the two P IGEONn instances such that M1 M2 ̸≡ 0. Since
F is d-pairwise witnessing, it follows that we can recover a solution to P IGEON⊗2n — that is, collisions
in both of the sub-instances — using at most d extra queries. Suppose additionally by contradiction thatM1 M2 does not witness a solution. Let H1 ⊆ M1 , H2 ⊆ M2 be the submatchings on the first P IGEONn
sub-instance, and suppose without loss of generality that H1 H2 does not witness a collision, and is therefore
a matching. Let p ≤ d be the number of pigeons queried by H1 H2 . It follows that P IGEONn ↾ H1 H2 canrecover a collision with at most d extra queries, and thus it has decision-tree complexity at most d. But
P IGEONn ↾ H1 H2 ≡ P IGEONn−p , since we are just matching p pigeons to holes, and the decision treecomplexity of P IGEONn−p is ≥ n − p by an easy adversary argument. Therefore d ≥ n − p ≥ n − d, andthus d ≥ n/2, which is a contradiction.
Reduction to Matching Decision Trees. We now move on to constructing a matching decision tree thatcovers the weight of a strong pairwise-witnessing family. In this part of the proof, it will be convenient tothink of families as DNF formulas, as follows:
Definition 4.6. A matching DNF is a DNF F where every term M in the DNF is a matching term over thevariables of P IGEON⊗2
n . The width of F is theW degree of the widest term in F . Given a family of matchings
F, the matching DNF corresponding to F is M ∈F M . We say a matching DNF is good if its corresponding
family of matchings is strongly d-pairwise witnessing.
P Given a matching DNF F we can evaluate the matching pseudoexpectation on F by defining Ẽ[F ] :=M ∈F Ẽ[M ] to be the sum of the pseudoexpectation values in F . The definition of coherency leads us to
the following simple observation:
Observation 4.7. If a matching DNF F is good then every pair of matchings M1 ̸= M2 in F are incoherent.
Proof. If F is good, then every pair of matchings M1 ̸= M2 are either inconsistent or witness a solution to
P IGEON⊗2n , i.e. M1 M2 are incoherent.

15

If M1 and M2 are two matching terms, then define the matching term
if M1 and M2 are incoherent,0
M1 ↾ M2 := 1
if M1 ⊆ M2 ,

M1 \ M2 otherwise.
We extend the restriction operator to matching DNFs F by defining
if N ↾ M = 0 for all N ∈ F
0F ↾ M := 1
if there is an N ∈ F such that N ↾ M = 1Wotherwise
N ∈F N ↾ M
Implicitly, in the third case above, we remove any term N ↾ M of the DNF if N ↾ M = 0.
It is crucial to note here that the restriction operator outputs different “truth values” than it would undernormal boolean assignments, due to the substitution of “coherency” for “consistency”. However, these“nonstandard” truth values are consistent with the values of the pseudoexpectation operator Ẽ, which is why
they are useful for us. Indeed, this switch to non-standard logic and “coherency” is one of the key steps thatmake the proof possible.
We can now introduce the central notion of a matching decision tree.
Definition 4.8. Consider a P IGEON⊗2n instance. A matching decision tree T is a rooted tree defined asfollows. Each internal node of the tree is labelled by either a pigeon p or a hole h occurring in the P IGEON⊗2ninstance, and each leaf of the tree is labelled with 0 or 1. If a node is labelled with a pigeon p, then theoutgoing edges are labelled with pairs of the form p 7→ h, where h is an available hole that the pigeon p can
map to. Similarly, if a node is labelled with a hole h, then the outgoing edges are labelled with pairs of theform p 7→ h, where p is an unmapped pigeon that can map to h. Furthermore, no node or edge label can be
repeated on any path of T , and if u is a node of T then the edge labels on the path from the root to u should
determine a matching, denoted π(u), from pigeons p to holes h. The matching tree is full if every internal
node has the maximum number of children.
Given a matching decision tree T and a bit b ∈ {0, 1}, let
Lb (T ) := {π(ℓ) : ℓ is a leaf of T labelled with b}
and M (T ) = L0 (T ) ∪ L1 (T ). We can evaluate the matching pseudoexpectation on a matching decision tree
by defining
X
Ẽ[T ] :=Ẽ[M ]
M ∈L1 (T )to be the sum over the matchings at the 1-leaves of T .
Next, we discuss how to relate matching decision trees and matching DNFs. If T is a matching decision
tree and F is a matching DNF, then T represents F if for every b-labelled leaf ℓ of T , F ↾ π(ℓ) = b.
Furthermore, we say that T strongly represents F if T represents F and, furthermore, for every 1-leaf ℓ of
T there is a unique matching σ ∈ F that is coherent with π(ℓ). An obvious decision tree that represents any
matching DNF is the so-called canonical decision tree associated with F , which we define now (and will befamiliar to any reader acquainted with the switching lemma). First we need the definition of a full matchingtree for a set of nodes U .
Definition 4.9. Let U be a subset of nodes (either pigeons or holes) in P IGEON⊗2
n . The full matchingdecision tree TU covering U is defined recursively as follows. We begin with an unlabelled root node.
16

p11

h11

h12

p13

1

p23

h12

h11
p12

h21

h12

p12

p22

h22

h21

h21

1

p22

h22

h21

1

p21

p23

p21

p23

0

0

0

0

Figure 2: A canonical matching decision tree for [[p11 7→ h12 ]] ∨ ([[p11 7→ h11 ]] ∧ [[p22 7→ h21 ]]) of P IGEON⊗2
2 . The1
1
nodes in green correspond to the full matching tree for [[p1 7→ h2 ]], while the nodes in yellow come from thefull matching tree for ([[p11 7→ h11 ]] ∧ [[p22 7→ h21 ]]) ↾ π(ℓ).
While there is an unlabelled node x ∈ TU , choose the first uncovered pigeon or hole u ∈ U and label x withu. The children of x have edges connected to x labelled with all edges e containing u such that π(u) ∪ {e}is a matching.
Definition 4.10. Let F = M1 ∨ M2 ∨ · · · ∨ Mm be a matching disjunction over P IGEON⊗2
n . The canonicalmatching decision tree of F , denoted Can(F ), is the matching decision tree defined as follows.
− If F ≡ b for b ∈ {0, 1}, then Can(F ) is a single leaf node labelled with b.
− If F is not constant, then consider the first i such that Mi ̸≡ 0. The tree Can(F ) is constructed asfollows:− Construct the full matching decision tree TU covering the set of nodes U appearing in Mi .
− Recursively replace each leaf ℓ of TU with the canonical tree Can(F ↾ π(ℓ)).
It is obvious from the definition that Can(F ) represents any matching disjunction F . However, it is
not true that Can(F ) will always strongly represent F . To see this, consider the matching disjunction
F = Jp1 7→ h1 K ∨ Jp2 7→ h2 K. The tree Can(F ) will start by querying the pigeon p1 , and when it learns
that p1 7→ h1 it will stop and output 1. However, the matching Jp1 7→ h1 K is coherent with the matching
Jp2 7→ h2 K, and so Can(F ) will not strongly represent F . Thus Can(F ) does not strongly represent F
whenever F contains two coherent matchings. In fact, we can show that this is the only time this happens:
Lemma 4.11. If F is any matching disjunction then Can(F ) represents F . Furthermore, if for all matchingterms M1 ̸= M2 in F , M1 and M2 are incoherent, then Can(F ) strongly represents F .
Proof. The fact that Can(F ) represents F is clear from the definition of Can(F ). So, we focus on showing
the claim about strong representation. Write F = M1 ∨ M2 ∨ · · · ∨ Mm , and consider any 1-leaf ℓ ofCan(F ). By construction, Can(F ) represents F , and so F ↾ π(ℓ) ≡ 1 and thus there is a matching Mi suchthat Mi ⊆ π(ℓ). Suppose by way of contradiction that there is a j ̸= i such that Mj is also coherent with
π(ℓ). Then Mi and Mj are also coherent, contradicting the assumption.
The importance of strong representation owes to the fact that it conserves pseudoexpectation weight.
We prove this next:
17

T

σ

π(ℓ) = HℓℓFigure 3: The base case of Lemma 4.12. The black path is π(ℓ) and the red segments are the edges in σ.
Lemma 4.12. Consider P IGEON⊗2n , let d ≤ n − 1, and let F be any width-d matching DNF. If T is a fullmatching decision tree that strongly represents F , then Ẽ[F ] ≤ Ẽ[T ].
Proof. Letting H denote the family of matchings associated with F , we show that Ẽ[T ] = Ẽ[L1 (T )] ≥Ẽ[H] = Ẽ[F ]. Let u be any node in the tree T and let Tu be the subtree of T rooted at u. Define the sets ofmatching terms
Hu = {M π(u) : M ∈ H and M π(u) is coherent}
Mu = {N π(u) : N ∈ L1 (Tu )} .
We argue by induction over T that Ẽ[Mu ] ≥ Ẽ[Hu ]. When u = r is the root node, we have that Hr = H
and Mr = L1 (T ), which completes the proof.
For the base case, consider any leaf node ℓ of the tree T . Clearly Mℓ ⊆ {π(ℓ)} and, since T strongly
represents F , π(ℓ) is coherent with at most one element of H which it must extend. If ℓ is labelled with 0,then by the definition of strong representation π(ℓ) ∪ σ is incoherent for all σ ∈ H. This means that Hℓ = ∅and the induction hypothesis is satisfied. Otherwise, let σ be the unique element of H such that π(ℓ) ⊇ σ,then we have Hℓ = Mℓ , as Hℓ consists of exactly the extension of σ by the path π(ℓ), and the claim is true.
(We remark that it is the fact that σ is unique is precisely where we need strong representation in order toprove the lemma.)
Now, consider any internal node u of the tree T and let v1 , . . . , vc denote the child
Sc nodes of u in T . Let
ρ1 , ρ2 , . . . , ρc be the edge labels
on
the
edges
connecting
u
to
v
in
T
.
By
definitionii=1 Mvi is a partitionPof Mu , andPthus Ẽ[Mu ] = i Ẽ[Mvi ]. By induction, Ẽ[Hvi ] ≤ Ẽ[Mvi ] for each i, and thus we show thatẼ[Hu ] ≤ i Ẽ[Hvi ]. Since T is full, if M ∈ H is coherent with π(u), then M will also be coherent withat least one child of π(u), and thus all N ∈ Hu will be coherent with at least one child of u. For each i, we
can write
Hvi = {N ρi : N ∈ Hu }where ρi is the edge label on the edge connecting u to vi in T .
PConsider any N ∈ Hu , and recall that our goal is to prove that Ẽ[Hu ] ≤ ci=1 Ẽ[Hvi ]. There are exactly
two possibilities:
1. There is a unique vi such that N ∈ Hvi , or
2. N does not occur in any Hvi .
The first case occurs if the pigeon or hole queried by u occurs in N , and otherwise the second case occurs.
We will prove that the weight of N is covered in either case. In the first case, the weight Ẽ[N ] in Hu
18

is covered exactly by the weight Ẽ[N ] in Hvi , since there is a unique outgoing edge for N to follow inthe decision tree. In the second case, let t ≤ c be the number of edges of N occurring in the P IGEON
instance containing the query labelled on the node u. There are exactly c − t edges among the labels
ρ1 , ρ2 , . . . , ρc that are coherent with N , so suppose without loss of generality that the first c − t labels are
the coherent ones. Then the set Hvi for 1 ≤ i ≤ c − t contains a copy of the matching N ρi , which has
weight Ẽ[N ] · (c − t − 1)−1 ≥ Ẽ[N ] · (c − t)−1 if u was a hole query, and weight Ẽ[N ] · (c − t)−1 if u wasa pigeon query. Since there are (c − t) of these matchings, in either case we have that
c−t
X
i=1


Ẽ[N ρi ] ≥

c−t
c−t


Ẽ[N ] = Ẽ[N ].

Thus in the second case the weight of Ẽ[N ] is covered as well. This means that Ẽ[Hu ] ≤completing the induction step and the proof.

Pc

i=1 Ẽ[Hvi ],Corollary 4.13. For any good matching disjunction F , Ẽ[F ] ≤ Ẽ[Can(F )].
Bounding the Weight of Matching Decision Trees. We are now on the final steps of the proof. First, we
will repeatedly use the following useful lemma that bounds the depth of canonical decision trees.
Lemma 4.14. Let F be any width-d matching DNF such that for all M1 ̸= M2 ∈ F , M1 ∪M2 is incoherent.
Then the depth of Can(F ) is O(d2 ).
Proof. The canonical decision tree Can(F ) is constructed in rounds, where in each round we choose thenext matching term Mi that is not set to a constant and construct the full matching decision tree over that
term. We prove the following claim by induction:
Claim. Let ℓi be any leaf in the tree produced after i rounds of construction of Can(F ), let Mi be any
matching term in F such that Mi ↾ π(ℓ) is not a constant. Then |Mi \ π(ℓi )| ≤ |Mi | − i.
Proof of Claim. When i = 0 the claim is vacuously true. So, by way of induction, suppose we have justcompleted the ith round of the construction of Can(F ). Let ℓi−1 be the leaf of the tree chosen at the
beginning of the ith round, and let Mi−1 be the matching from F chosen to be queried during the ith round.
By induction, we know that |Mi \ π(ℓi−1 )| ≤ |Mi | − (i − 1). So, we need to argue that during the ith round
we queried at least one more edge in Mi .
To see this, we observe that in the ith round we construct the full matching decision tree over Mi−1 ↾π(ℓi−1 ), and thus query every node appearing in Mi−1 ↾ π(ℓi−1 ) in this sub-tree. Since Mi and Mi−1 areincoherent matching terms, there is a node u appearing in Mi such that u participates in a different edgein both Mi and Mi−1 . Since the leaf ℓi is coherent with Mi , it cannot be coherent with Mi−1 , and thus
this node must have been queried along the path from ℓi−1 to ℓi and the query must be coherent with Mi .
Therefore, we have made one more query to Mi , and so the proof of the claim is complete.
Due to the claim, in each round of construction the width of all coherent matching terms that remains
decreases by 1. Since all terms begin with width ≤ d, this means that the construction of Can(F ) cancontinue for at most d rounds, and in each round we query at most 2d edges. Thus the depth of any path inCan(F ) is at most O(d2 ).
We are now ready to combine these ingredients together and prove our final weight bound. The next theorem, when combined with Theorem 3.6, immediately implies the main result (Theorem 4.1) as a corollary.
Theorem 4.15. If d = o(n1/8 ) and F is a good matching DNF of width at most d, then Ẽ[F ] ≤ 1. In
particular, letting D = n/2, the degree-D matching pseudoexpectation for P IGEON⊗2
n is d-collision free.
19

Proof. We begin by showing that the “in particular” statement holds, assuming the first part of the theorem.
Let Ẽ be the degree-D matching pseudoexpectation, and let F be a d-pairwise-witnessing family of matching terms for P IGEON⊗2
n . By Lemma 4.5, we may assume that F is a strong pairwise-witnessing family. Let
F be the good matching DNF corresponding to F. We note that since F is strongly pairwise-witnessing,it follows that F is good, and in particular that every pair of matchings M1 ̸= M2 in F are incoherent byObservation 4.7. Hence, Ẽ[F] = Ẽ[F ] ≤ 1 by assumption.
We now prove the first part of the theorem. Let F be a width ≤ d good matching DNF chosen such that
Ẽ[F ] is maximized, and let H be the set of matchings associated with F . We will show that Ẽ[F ] ≤ 1. In
the proof of this theorem, a weighted matching decision tree T is a matching decision tree
Pwhere each leaf ℓis labelled with a real weight w(ℓ) ≥ 0. Given such a decision tree, we define w(T ) := ℓ∈L(T ) w(ℓ). Our
overall goal is to construct a weighted matching decision tree T such that
1. T is composed only of pigeon queries.
2. For each leaf ℓ of T , w(ℓ) ≤ Ẽ[π(ℓ)].
3. Ẽ[F ] ≤ w(T ).
The proof is complete once we have such a tree, since properties (1) and (2) imply that w(T ) ≤ 1 by aneasy induction over the depth of the tree, and combining this with property (3) yields the theorem.
We first describe the construction of the tree. At a high level, we follow the construction of Can(F ),except we “skip” the hole queries and “freeze” the matchings that would have participated in them instead,removing them from consideration in future queries of the algorithm. Formally, the construction of the tree
T proceeds by the following query algorithm. Throughout the construction of T , we maintain the followingdata.
− A node u that is currently visited.
− A set L ⊆ H of live matchings.
− A set R ⊆ H of frozen matchings.
For any node u in the decision tree, let π(u) denote the matching obtained by following the path in the tree
from the root to u. Just as in the proof of Lemma 4.12, for any set of matchings S and any node u in thedecision tree, define
Su := {M π(u) : M ∈ S and M, π(u) are coherent}.
Initially, L = H is the set of matchings associated with F , R = ∅, and u = r is the root node of the decision
tree. Throughout, we maintain the important invariant that L ∩ R are disjoint, and that all matchings in
L ∪ R are coherent with the matching π(u) throughout the construction. This invariant is clearly satisfied
at the beginning of the construction.
The construction proceeds in stages. At the beginning of a stage, we have arrived at node u with setsof matchings L, R. If L = ∅ or if L = {M } such that M ⊆ π(u), then we halt and label the leaf with theweight Ẽ[Lu ]+ Ẽ[Ru ]. Otherwise, we pick any matching M ∈ L, and write M = {p1 7→ h1 , . . . , pt 7→ ht },noting that t ≤ d. Let I ⊆ [t] be the set of indices of pigeons in M that have not yet been queried. Next, werepeat the following for each index i ∈ I. We query pi , receiving some hole h in response, and remove allmatchings from L ∪ R that are incoherent with this query. Afterwards, if h ̸= hi , then we take all matchings
N ∈ L that contain the hole hi and freeze them, deleting them from L and placing them in R. We call thesematchings newly frozen at this query. Once all indices have been queried in this way, we finish this stage,
and continue the construction recursively. This completes the description of the weighted tree T .
By definition, the tree T is composed only of pigeon queries. Therefore it suffices to prove the following
claims.
Claim 1. w(T ) ≥ Ẽ[F ].
20

Claim 2. For each leaf ℓ of T , w(ℓ) ≤ Ẽ[π(ℓ)] ≤ 1.
Assuming these claims, we complete the proof of Theorem 4.15. By induction on the size of the subtree
Tu , we argue that w(Tu ) ≤ 1 for all nodes u ∈ T . This will imply that w(T ) ≤ 1, and hence Claim 1
completes the proof of the theorem.
For the base case, if ℓ is a leaf of T , then w(Tℓ ) = w(ℓ) ≤ 1 by Claim 2. Suppose that u is non-leaf
node of T , and let p be the pigeon queried at u. Let c be the number of holes mentioned on the root-to-upath π(u) which come from the same P IGEON instance as p, and let v1 , . . . , vn−c be the children of u. By
induction, w(Tvi ) ≤ 1 for all i ∈ [n − c]. Hence
Ẽ[Tu ] =

n−c
X

n−c

Ẽ[(p 7→ hi ) ◦ Tvi ] =

i=1

1 X
n−c
Ẽ[Tvi ] ≤
= 1,
n−c
n−c
i=1

which completes the induction.
We prove these two claims by induction, but an interesting feature of the proof is that the first fact will
be proven by induction from the bottom-up, while the second fact will be proven by induction from the topdown. Before launching into proving these facts, we make two simple observations. First, we observe thatan easy induction over the construction of the tree proves that Lu ∪ Ru = Hu for each node u. Second, we
observe that the depth of T is at most the depth of Can(F ), since we are simulating the execution of Can(F )except that we skip the hole queries and remove any matchings participating in those hole queries fromfurther consideration, which only decreases the depth of T relative to Can(F ). Therefore, by Lemma 4.14,
the depth of T is at most O(d2 ).
Now, we begin by proving the first, and easier, claim. The proof of this claim is very similar to the proof
of Lemma 4.12, and so we will only sketch some of the details for the sake of brevity.
Proof of Claim 1. For any node u in the tree, we prove by induction that Ẽ[Hu ] ≤ w(Tu ), where Tu is thesubtree of T rooted at u. This implies the claim, since Hr = H and w(Tr ) = w(T ), where r is the rootnode.
As a base case, consider any leaf node ℓ of the tree. By the construction of T , the weight of w(Tℓ ) isdefined to be Ẽ[Lℓ ] + Ẽ[Rℓ ], where L and R are the sets of matchings when the leaf ℓ is visited. However,Lℓ ∪ Rℓ = Hℓ , and the proof of the inductive claim is complete.
Now, by induction, consider any internal node u of the tree. Suppose that p was the pigeon queriedat this node, and let v1 , v2 , . . . , vc be the child nodes of u with the edges labelled by h1 , h2 , . . . , hc . The
inductive hypothesis implies that w(Tvi ) ≥ Ẽ[Lvi ] + Ẽ[Rvi ] P= Ẽ[Hvi ]. By a paddingargument identical toPccthe argument at the end of Lemma 4.12, we have Ẽ[Hu ] ≤ i=1 Ẽ[Hvi ] ≤ i=1 w(Tvi ) = w(Tu ). This
completes the proof of the claim.
Now we proceed to the proof of the second, and more difficult, claim.
Proof of Claim 2. As we have observed above, at each node u we have Hu = Lu ∪ Ru . In particular, since
H is a good family, Hu is also a good family, and so Lu ∪ Ru is a good family. Now, consider the leaf nodeℓ. By the construction of T , since ℓ is a leaf we have that either Lℓ = ∅ or Lℓ = {π(ℓ)}. If Lℓ = {π(ℓ)},
then Rℓ = ∅, since Hℓ is a good family and every matching in Rℓ must extend π(ℓ) by definition. Thus, inthis case,w(ℓ) = Ẽ[Lℓ ] + Ẽ[Rℓ ] = Ẽ[π(ℓ)] + 0 = Ẽ[π(ℓ)],
completing the proof.

21

Moving forward, we therefore assume that Lℓ = ∅ and Rℓ ̸= ∅. This means that w(ℓ) = Ẽ[Rℓ ], andthus we must show that Ẽ[Rℓ ] ≤ Ẽ[π(ℓ)]. To show this, we prove by induction that for each node u theinequality
 2dẼ[Ru ] ≤ O
depth(u) · Ẽ[π(u)](1)
nholds. Let us briefly assume that the inequality holds. Then, since we have observed above that for any leafℓ, depth(ℓ) = O(d2 ), and we have assumed that d2 = o(n1/4 ), this inequality implies that Ẽ[Rℓ ] < Ẽ[π(ℓ)],
which completes the proof of Claim 2 and the theorem.
As a base case, when u = r we have Rr = ∅, and thus Ẽ[Rr ] = 0. Since depth(r) = 0 the inequality
trivially holds. Now, by induction, consider an internal node u and suppose that Equation (1) holds for
Ru . Let p be the pigeon queried at the node u, and suppose that u has c children denoted v1 , . . . , vc ,corresponding to the holes h1 , h2 , . . . , hc . Let vi be any child of u, and consider the set Rvi . We prove that 2Ẽ[Ru ]d+OẼ[π(vi )],Ẽ[Rvi ] ≤cnand Equation (1) follows for vi by some simple algebra.
First, we assume without loss of generality that every matching M ∈ Ru contains the pigeon p. If not,letting k denote the number of edges in M in the instance of P IGEONn containing p, we can replace M withn − k new matchings M1 , . . . , Mn−k , which are identical to M except we add an edge in Mi from p to the
ith available hole. After replacement, the new family still has weight Ru and is good, and moreover thefamilies Rvi remain unchanged.
With this simplification in mind, observe that every matching M ∈ Rvi either already lies in Ru , or, it
is a newly frozen matching. Let R′vi = Ru ∩ Rvi denote the set of matchings that were inherited from Ru ,and let Nvi denote the set of newly frozen matchings. Using this notation, we can write Rvi = R′vi ∪ Nvi ,and henceẼ[Rvi ] = Ẽ[R′vi ] + Ẽ[Nvi ].
We prove that Ẽ[R′vi ] ≤ Ẽ[Rvi ]/c and Ẽ[Nvi ] ≤ O(d2 /n)Ẽ[π(vi )], which completes the proof of Equation (1).
Let us first prove that Ẽ[R′vi ] ≤ Ẽ[Ru ]/c. Since every matching M ∈ Ru contains the pigeon p, it
follows that R′v1 , R′v2 , . . . , R′vc is a partition of Ru . We claim that for each a ̸= b, Ẽ[R′a ] = Ẽ[R′b ]. If thisis true, then we are done, since then all c sets R′vi comprising the partition of Ẽ[Ru ] have equal weight, andso by averaging they must have weight Ẽ[Ru ]/c. So, to see the claim, suppose by contradiction that there isa pair a ̸= b such that Ẽ[R′a ] > Ẽ[R′b ]. In this case, we will show how to modify Ru (and thus H) to obtain
another good family with even larger weight, contradicting the assumption that F is a good DNF with the
maximum possible weight.
Given a matching π containing the edge p 7→ hi and another hole hj ̸= hi , define the new matchingswap(π, p, hi , hj ) by taking π and either removing the edge p 7→ hi and adding p 7→ hj , if hj has no pigeon
mapping to it in π, or by swapping the pigeons mapping to holes hi and hj if hj does have a pigeon mapping
to it. With this, define the family
R′′b = swap(π, p, ha , hb ) | π ∈ R′a
to be all swaps of matchings in R′a . Since every matching in R′a contains the edge p 7→ ha , it follows that
all matchings in R′′b are well defined, they all contain p 7→ hb , and also Ẽ[R′′b ] = Ẽ[R′a ] > Ẽ[R′b ]. With
this in mind, consider the set R′u = (Ru \ R′b ) ∪ R′′b . We immediately have that Ẽ[R′u ] > Ẽ[Ru ], and thus
the weight has increased. Thus, if we prove that R′u is also a good family, we will have contradicted the
maximality of Ẽ[F ], since it implies the maximality of Ẽ[Ru ].
22

Figure 4: The swap operation applied to (π, p11 , h12 , h13 ). The original matching π is given in red, while the
new matching swap(π, p11 , h12 , h13 ) is given in black.

Consider any two distinct matchings π, σ ∈ R′u , and we prove that π and σ are either inconsistentor witnessing. We only need to consider the case where π, σ ∈ R′′b , since if one of π or σ is not in R′′bthen either they are inconsistent on the pigeon p, or, they are both contained in a set of the form R′i forsome i ̸= b, which we already know to be a good family. So, suppose that π = swap(π ′ , p, ha , hb ) andσ = swap(σ ′ , p, ha , hb ) for some π ′ , σ ′ ∈ R′a . Since π ̸= σ we immediately have that π ′ ̸= σ ′ , and thus
they must either be inconsistent or witness. Since π and σ are obtained by swapping p 7→ ha with p 7→ hb ,it follows by a case analysis that π and σ must be inconsistent or witness as well. This completes the proof
that R′u is a good family, and we obtain our final contradiction. Therefore, Ẽ[R′vi ] ≤ Ẽ[Ru ]/c.
Finally, we prove that Ẽ[Nvi ] ≤ O(d2 /n)Ẽ[π(vi )]. This is implied immediately by the next lemma,
setting M = Nvi , π = π(vi ), and h is the hole used that witnesses the newly-frozen matchings.
Lemma 4.16. Let n be any sufficiently large integer, and let k ≤ d = o(n1/8 ). Let π be a matching of size
k on P IGEON⊗2
n , and let h be a hole not appearing in π. Let M be any good family of size ≤ d matchings
such that each matching in M contains both π and h. Then!
d2 · Ẽ[π]Ẽ[M] = O.
nAs discussed above, this lemma implies Ẽ[Nvi ] ≤ O(d2 /n)Ẽ[π(vi )], which completes the proof of
Equation (1) and hence Claim 2.
Proof of Lemma 4.16. Let T = Can(M), although, with the added assumption that the tree begins by firstquerying all of π, and then immediately afterwards it queries the hole h. Since every matching M ∈ M
contains π, any leaf of T not consistent with π is set to 0. Let D be the depth of T , and note that D = O(d2 ).
Let u be the first node in T consistent with π, and we note that the hole h is queried at u. Let v1 , v2 , . . . , vc be
the children of u, corresponding to the pigeons p1 , p2 , . . . , pc , and note that n + 1 − k ≤ c ≤ n + 1. Observethat M = Mu , and since every matching in M contains the hole h, it follows that Mv1 , Mv2 , . . . , Mvc
is a partition of M. For each i = 1, . . . , c, define M′i = {π(ℓ) : ℓ ∈ L1 (Tvi )}S to be the set of matchings
obtained by taking root-to-leaf paths in the subtree rooted at vi , and let M′ = ci=1 M′i .
Before we bound the weight of M, we make a key observation about the family M′ .
Key Observation. If τ ∈ M′i is any matching, then there is a set of t > c−D +1 indices Iτ ⊆ {1, 2, . . . , c}such that for each j ∈ Iτ and each τ ′ ∈ M′j , the matchings τ and τ ′ are incoherent.
To prove this key observation, consider any σ ∈ Mvi and any σ ′ ∈ Mvj . Since M is good, σ andσ ′ must be either inconsistent or witnessing. Write σ = π(pi 7→ h)τ and σ ′ = π(pj 7→ h)τ ′ (noting that23π

T = Can(M)hp1p2 p3 . . .

pc

M′ =
Tv1

Tv2

Tv3

Tvc

S

i∈[c] L1 (Tvi )Figure 5: The family M′ formed by taking the 1-paths of the sub-trees trees Tv1 , . . . , Tvc rooted at thechildren of a leaf of a path π in Can(M′ ).
τ ∈ M′i and τ ′ ∈ M′j ), and suppose that τ and τ ′ are coherent matchings. Then the only possibility is thateither pi occurs in τ ′ or pj occurs in τ , since otherwise σ and σ ′ would not be inconsistent or witness. Since
τ has at most D − 1 edges in it, this can only occur for at most c − D + 1 of the subtrees of u, proving theobservation.
We now continue with the proof. Consider the following useful notation. If π and σ are coherent
matchings, then we writeẼ[πσ]
Ẽ[π|σ] :=,Ẽ[σ]and refer to Ẽ[π|σ] as the conditional pseudoexpectation of π given σ. We extend the conditional
notationP
to sets in the natural way: if U is a set of matchings coherent with π, then Ẽ[U|π] := σ∈U Ẽ[σ|π]. With
this notation in hand, we can writeẼ[M] = Ẽ[Mu ]cX= Ẽ[π]Ẽ[pi 7→ h|π]Ẽ[M′i |π ◦ (pi 7→ h)]
=

Ẽ[π]
c

i=1
c
X

Ẽ[M′i |π ◦ (pi 7→ h)].

i=1

We now prove the boundc
XẼ[M′i |π ◦ (pi 7→ h)] ≤ D = O(d2 ).

(2)

i=1

Once we have this bound, the proof is complete, since c ≥ n − k ≥ n − d ≥ 0.99n for sufficiently large n,assuming d = o(n1/8 ). Plugging both of these bounds in yields!
Ẽ[π]d2
Ẽ[M] ≤ On24

as desired.
To establish(2) we build another weighted matching decision tree, T ′ , which will bound thePc Equation′
weight of i=1 Ẽ[Mi |π ◦ (pi 7→ h)]. In particular, we will construct T ′ so that the following holds:
D ≥ w(T ′ ) ≥cXẼ M′i |π ◦ (pi 7→ h) .
i=1

We build T ′ by constructing the canonical matching decision tree for M′ (with somePcslight modifications′
described below). This will cover the weight of M . To instead cover the weight of i=1 Ẽ[M′i |π ◦ (pi 7→h)], we re-weight the leaves. There
here: we would like to assign sufficiently large weight to the
Pc is tension′
leaves so that we upper-bound i=1 Ẽ[Mi |π ◦ (pi 7→ h)], however we cannot exceed a total weight of D.
By the Key Observation, we will show that at most (D − 1)-many matchings can be coherent with any leaf
ℓ of T ′ , and so we should weight ℓ by (D − 1) times the weight of the matching π(ℓ). However, this is ahuge overkill, as we haven’t accounted for the conditional expectation — the expectation of each matchingin M′i is conditioned on the fact that we have queried the (k + 1)-many holes and pigeons π ◦ (pi 7→ h).
Therefore, we should actually weight ℓ by (D − 1) times the weight of π(ℓ) conditioned on π ◦ (pi 7→ h).
However, the at most (D − 1)-many matchings that are coherent with π(ℓ) may come from different M′iand hence may be conditioned on different pi . The key is that we only care about covering the weight ofthis family, and hence it only matters that we condition on a matching of size k + 1. Hence, it suffices toweight each leaf by (D − 1) · Ẽ[π(ℓ)|π ◦ (p∗ 7→ h∗ )] for some arbitrary p∗ , h∗ not queried in π(ℓ). We now
formally describe T ′ .
Let P IGEON⊗2 ↾ π be obtained by fixing the variables of P IGEON⊗2 according to π. This decision tree
will query pigeons and holes from P IGEON⊗2 ↾ π; that is, we will build T ′ assuming that π has already been
queried. Note that the matchings in M′ do not mention any pigeons or holes mentioned by π. Let FM′
be the matching DNF corresponding to M′ . We construct the weighted matching decision tree T ′ coveringFM′ by the following modification of the construction of the canonical decision tree:
1. At each recursive round, in which we extend a leaf ℓ constructed in the tree so far by choosing a termin FM′ ↾ π(ℓ) and query every pigeon and hole mentioned within it, the term of FM′ ↾ π(ℓ) which isthe chosen is the one with the largest width.
2. If we reach a leaf ℓ where FM′ ↾ π(ℓ) = b ∈ {0, 1}, then if b = 1 we label the weight of this leaf ℓwith w(ℓ) := (D − 1) · Ẽ[π(ℓ)|π ◦ (p∗ 7→ h∗ )], where p∗ and h∗ are a pigeon and a hole which havenot been queried by π(ℓ); this is to ensure that T ′ correctly covers the weight and so the particularnames of p∗ and h∗ are immaterial. Otherwise, if b = 0 then we label it by w(ℓ) := 0.
We stress that only pigeons and holes from P IGEON⊗2 ↾ π are queried during this process.
The (D − 1) factor in the weight comes from the fact that Key Observation only guarantees that τ ∈ M′i
is incoherent with matchings from at least c − (D − 1)-many M′j . This differs from previous cases where
we constructed canonical trees from good families (in which every pair of matchings is incoherent). Evenso, the Key Observation still suffices to bound the depth.
Lemma 4.17. T ′ satisfies the following:(i) T ′ has depth at most D3(ii) For each leaf node ℓ of T ′ , there are at most (D − 1)-many indices i such that M′i,ℓ is non-empty, andfor each such i, |M′i,ℓ | = 1.
Proof. The proof of (i) is similar to the proof of Lemma 4.14, however in that proof we relied on every
pair of matchings in M′ being incoherent. Now, M′ only satisfies the following two weaker properties: (1)The Key Observation holds for every τ ∈ M′ , and (2) for every i ∈ [c], every pair of matchings in M′i
25

is incoherent. (2) holds because every pair of paths in a matching decision tree are incoherent, and eachM′i := {π(ℓ) : ℓ ∈ L1 (Tvi )}. As we will see, the same general idea can still be carried out, however at thecost of an additional multiplicative factor of D.
Say that a matching τ ∈ M′ is constant under a matching γ if its corresponding matching term becomes
constant after restricting by γ. That is, if γ and τ are incoherent or τ ⊆ γ. The key to the proof (i) is thefollowing technical claim.
Claim. Let ℓi be any leaf in the tree produced after i recursive rounds in the construction of T ′ , let τ be
the matching that is queried at the (i + 1)-st recursive round, where τ ∈ M′t for some t ∈ [c], and let ℓi+1
be any leaf that is reached after querying τ . Then, for any j ∈ Iτ ∪ {t} and τ ′ ∈ M′j such that τ ↾ π(ℓ) is
not a constant, |τ ′ \ π(ℓi+1 )| ≤ |τ ′ \ π(ℓi )| − 1.
Proof of Claim. In the (i + 1)-st recursive round we construct the full matching decision tree over the nodesin τ \ π(ℓi ). Let Iτ ⊆ [c] be the set of indices guaranteed for τ by the Key Observation, and pick somej ∈ Iτ ∪ {t} and any τ ′ ∈ M′j such that τ ′ ↾ π(ℓ) is not constant. We argue that after querying τ , the widthof τ ↾ π(ℓ) drops by at least 1. To do so, it suffices to show that in the (i + 1)-st round we query at least oneedge of τ \ ρ(ℓi ).
Since j ∈ Iτ ∪ {t}, τ and τ ′ are incoherent, and since |τ ′ ↾ π(ℓ)| ≠ 0, τ ′ and π(ℓ) are coherent. Hence,τ ↾ π(ℓ) and τ ′ ↾ π(ℓ) are incoherent, and so they have at least one pigeon or hole in common. Therefore,
after querying the nodes of τ ↾ π(ℓ) in the (i + 1)-st round, |τ ′ \ π(ℓi+1 )| ≤ |τ ′ \ π(ℓi )| − 1.
Using this claim, we prove (i) by induction: for i = 1, . . . , D, we argue that if we have reached a nodeℓ after iD-many recursive rounds in the construction of T ′ , the width of every matching in M′ has dropped
by at least i. That is, for every τ ′ ∈ M′ , either τ ′ ↾ π(ℓ) is constant or |τ \ π(ℓ)| ≤ D − i. This suffices toprove (i) as each matching has size at most D. For y ∈ [D2 ] we will denote by ℓy any leaf node which wehave arrived at after y recursive rounds in the construction of T ′ .
Supposing that the inductive hypothesis holds at the end of the the D(i − 1)-st recursive round, we provethat it holds at the end of the Dith recursive round. Let τ ∈ M′t be the matching whose nodes were queriedin the (D(i − 1) + 1)-st recursive round. By the Claim, for every j ∈ Iτ ∪ {t} and every τ ′ ∈ M′j such thatτ ′ ↾ π(ℓ(D(i−1)+1 ) is not constant, we have that |τ ′ \ π(ℓ(D−i)+1 )| ≤ D − i. That is, the width of all of thematchings in the families indexed by Iτ ∪ {t} has dropped by at least 1.
It remains to argue that the width of all matchings in M′k for k ∈ [c] \ (Iτ ∪ {t}) drops by at least 1 afterD − 1 additional rounds. To see that this happens, note that construction of T ′ always chooses the matchingin M′ with the largest width (under the current restriction) to query. Therefore, if there are any matchingsof width D − i + 1, they will be queried next. The Claim ensures that we only need to query at most D − 1matchings before they all have width at most D −i. Indeed, By the claim, whenever we query some τ ∈ M′z
for some z ∈ [c] \ (τ ∪ {t}), the width of all non-constant matchings in M′z drops by at least 1. Hence, thewidth of all non-constant matchings in M′ drops to ≤ D − i after |[c] \ Iτ | = c − (c − (D + 1)) = D − 1
additional rounds, completing the induction and the proof of (i).
To prove (ii), let ℓ be a leaf of T ′ and recall that
M′i,ℓ := {τ π(ℓ) : τ ∈ M′i and τ, π(ℓ) are coherent}.
By the construction of T ′ , every τ ∈ M must either be contained in, or incoherent with π(ℓ), as otherwise
we would have queried τ , contradicting that ℓ is a leaf. Let I := {i ∈ [s] : M′i,ℓ ̸= ∅} and consider any τ insome M′i such that τ ⊆ π(ℓ). By the Key Observation, there is a set Iτ ⊆ [c] with |Iτ | ≥ c − D + 1 suchthat τ is incoherent with every τ ′ ∈ M′j for every j ∈ Iτ . Hence, as τ ⊆ π(ℓ) we have Iτ ∩ I = ∅, and so|I| = c − |Iτ | ≤ D + 1.
26

Finally, suppose that there is some i ∈ I such that |M′i,ℓ | > 1. Then there are τ, τ ′ ∈ M′ such thatτ, τ ′ ⊆ π(ℓ). This contradicts that every pair of matchings in M′i are incoherent.
In the remainder we will argue thatD ≥ w(T ′ ) ≥cXẼ M′i |π ◦ (pi 7→ h) ,i=1

which completes the proof of Equation(2), and hence Claim 2.
P
First, we show that w(T ′ ) ≥ ci=1 Ẽ[M′i |π ◦(pi 7→ h)]. This follows from an almost identical induction
to what we have done before (e.g. in Lemma 4.12), albeit with a slight twist in the base case. Let v be any
node in the tree T ′ , and we prove by induction thatw(Tv′ ) ≥cXẼ M′i,v |π ◦ (pi 7→ h) .
i=1

For the base case, let v = ℓ be any leaf node of the tree T ′ and let w(ℓ) = (D − 1) · Ẽ[π(ℓ)|π ◦ (p∗ 7→ h∗ )]be its weight, for some p∗ , h∗ not queried in π(ℓ) or π. By Lemma 4.17, there are at most D − 1 indicesi such that M′i,ℓ is non-empty. For each of these indices, there will be a unique matching M ∈ M′i,ℓ , andM ⊆ π(ℓ). Let M1 , . . . , Mz be these matchings, for z ≤ D − 1, then
z
c
X


 X

Ẽ Mi |π ◦ (pi 7→ h)Ẽ M′i,ℓ |π ◦ (pi 7→ h) =
i=1

i=1
z
X


=
Ẽ Mi |π ◦ (p∗ 7→ h∗ )(As Mi ⊆ π(ℓ) and p∗ , h∗ ̸∈ π(ℓ))

i=1



≤ (D − 1)Ẽ π(ℓ)|π ◦ (p∗ 7→ h∗ )= w(ℓ) = w(Tℓ ).
The inductive case follows identically
P to the inductive case in the proof of Claim 1 above and in the proof
of Lemma 4.12. Hence, w(T ′ ) ≥ ci=1 Ẽ[M′i |π ◦ (pi 7→ h)].
Next, we argue that D ≥ w(T ′ ). We will assume that T ′ satisfies the following properties:
1. It is composed entirely of hole queries,
2. All of the hole queries in T ′ and π come from the same P IGEON instance,
3. Every leaf of T has depth exactly D3 .
We claim that this assumption is without loss of generality, as it can only increase the weight of T ′ . As wehave made use of similar properties throughout the paper, we only sketch the proof. Consider a leaf ℓ in
the construction of T ∗ , and let k be the number of queries made to, say, the first P IGEON instance. To seethat (1) holds, observe that hole queries are the only queries which increase the weight of the tree. Indeed,
if we extend π(ℓ) byPa pigeon query to the first P IGEON instance then the total weight of the children of ℓ1
becomes w(π(ℓ)) · n−t= w(π(ℓ)), whereas if we extended it by a hole query the weight becomes
Pn−t+1 1 i=1 n−t
1
1w(π(ℓ)) · i=1 n−t = w(π(ℓ)) · (1 + n−t). To see (2), observe that the weight-gain 1 + n−t
of a hole
query increases with t, the number of queries made to the same P IGEON-instance. Finally, (3) holds as any
leaf of depth < D3 can be extended by additional hole queries to increase the weight of T ∗ .
Hence we assume (1) – (3). We have already occupied k pigeon to holes due to π and every path inQ 3 −1′T has depth exactly D3 . This means that there are at most D
i=0 ((n + 1) − (k + i)) root-to-leaf paths27

in T ′ . Since each path has depth exactly D3 , it follows that the weight of each leaf is bounded above by
Q 3 −1−1
leaf must matchthe same number of pigeons to holes,(D − 1) D
i=0 (n − (k + 1 + i)) , since eachand each leaf is labelled with with (D − 1)Ẽ π(ℓ)|π ◦ (p∗ 7→ h∗ ) . Note that this “+1” comes from theadditional condition that (p∗ 7→ h∗ ). Therefore, the total weight of this tree is

′

3 −1
DY

n + 1 − (k + i)n − (k + 1 + i)
i=0



n−k
n+1−k
= (D − 1)n − (k + D3 − 1)n − (k + D3 )



3
D
D3
= (D − 1) 1 +1+
n + 1 − k − D3
n − k − D3
2
D3
≤ (D − 1) 1 +n − k − D3

W (T ) ≤ (D − 1)

As k ≤ d, D = O(d2 ), and d = o(n1/8 ), D3 /(n − k − D3 ) ≤ 2/n, for sufficiently large n. Hence,

2


D3
2 2
′
w(T ) ≤ (D − 1) 1 +≤ (D − 1) 1 +≤ (D − 1) + 1 = D.
n − k − D3nThis completes the proof of Lemma 4.16.
We note that Lemma 4.16 is where our technique would break down if one tried to use it to “prove”
2n2n
P IGEON2nn ⊗ P IGEON n does not reduce to P IGEON n . (In particular, the upper bound in Equation (2) fails,
as in the case of hole queries the number of leaves will grow very quickly relative to the weight of theconditional pseudoexpectation.)

5

Lower Bounds for P IGEON⊗2 Generalizations

In this section we extend the argument from the previous section in order to prove Theorem 1.6.
Theorem 1.6. For all constant k, P IGEON⊗k is not black-box reducible to P IGEON⊗k−1 .
To prove this, one might hope to directly generalize the proof of Theorem 4.1. However, it is not clear
how to construct a low-depth matching decision tree which represents the natural extension of d-pairwise
witnessing families to the setting where we have k instances of P IGEON. Instead, we will give an inductive
argument. We would like to argue that if we have a reduction from P IGEON⊗k+1 to P IGEON⊗k , then this
implies that P IGEON⊗k reduces to P IGEON⊗k−1 , and hence we would contradict our main theorem thatP IGEON⊗2 does not reduce to P IGEON. A natural approach is to find a restriction which we could apply
to the P IGEON⊗k -formulation of P IGEON⊗k+1 that would leave us with a P IGEON⊗k−1 -formulation of
P IGEON⊗k . To do so, it suffices to pick one of the k instances of P IGEON from P IGEON⊗k -formulation andtry to find a pair of pigeons i, j and paths π1 , π2 in their decision trees such that under π1 π2 , the pigeons
i and j fly to the same hole (thus fixing one of the collisions of P IGEON⊗k , reducing it to P IGEON⊗k−1 )and such that π1 π2 witnesses at most one collision in P IGEON⊗k+1 . It turns out that we can guarantee theexistence of such a pair π1 π2 by proving a slightly strengthened version of our P IGEON⊗2 lower-bound. We
now introduce this strengthened version.
Definition 5.1. The P IGEON(⊗k,2) problem is defined as follows. The input is k functions f1 , . . . , fk :[n + 1] → [n + 1]. The output is a solution to P IGEON on any two of the k sub-instances of P IGEON.
28

Figure 6: An instance of P IGEON(⊗3,2) . A solution (1(2, 4), 3(2, 4)) is indicated by the red edges.

Note that P IGEON⊗2 = P IGEON(⊗2,2) , in the above notation. Next we define our matching pseudoexpectation for k copies of P IGEON, generalizing our earlier definition of pseudoexpectation for just two
copies of P IGEON. Recall that a matching term is just a conjunction of the variables such that no collision
between pigeons is witnessed and no pigeon is mapped to hole 1 in any of the instances.
Definition 5.2. The degree-d, k-matching pseudodistribution is defined as follows.
Given k sets of pigeonsSk⊗k
P1 , P2 , . . . , Pk from the k subinstances comprising P IGEONn such that | i=1 Pi | ≤ d, the distribution
DP1 ,...,Pk samples a uniformly random matching from Pi pigeons to |Pi | holes in [n + 1] \ {1} for eachi ∈ [k]. Formally, given k matching terms Mi of the Pi pigeons to holes, i ∈ [k], the corresponding
pseudoexpectation is defined to be|P1 |−1|P2 |−1|Pk |−1
Y
Y
Y
Y
1
1
1


Ẽ
Mi :=
···
,
n − i1n − i2n − ik
i∈[k]

i1 =0

i2 =0

ik =0

and extended to all matching terms by linearity.
By an analogous argument to the proof of Lemma 4.4, this is a pseudo-expectation for P IGEON⊗k and
P IGEON(⊗k,2) . By following the proof of Theorem 4.15, we can show the following generalization (we defer
the argument to the end of the section).
Theorem 5.3. Let k be any constant, let D = n/2 and d = o(n1/4 ). The degree-D, k-matching pseudoex(⊗k,2)
pectation Ẽ is d-collision free for P IGEONn.
Using this theorem we now prove Theorem 1.6.
Proof of Theorem 1.6. We will proceed by induction on k, using our separation of P IGEON⊗2 from P IGEON(Theorem 4.1) as the base case. Throughout this proof, we will write A ≤ B to denote when there is apoly(log(n))-complexity B-formulation of problem A. Our inductive hypothesis is the following:⊗k−1
Inductive Hypothesis. For any m and any M = mpoly(log(m)) , P IGEON⊗k.
m ̸≤ P IGEON M

Assume the inductive hypothesis for k, and suppose by way of contradiction that there is a P IGEON⊗k
N ⊗k+1poly(log(n))
formulation of P IGEONnfor some N = n
and decision trees of depth d = poly(log(n)). We
write this assumption as
P IGEON⊗k+1≤ P IGEON⊗k
(3)
n
N .
1
Let T11 , . . . , TN1 +1 be the decision trees defining the first P IGEONN -instance in P IGEON⊗k
N , where Ti specifies to which of the holes the ith pigeon flies.

29

For any decision tree T , let L(T ) denote the leaves of T , and for any ℓ ∈ L(T ), let Cℓ denote theconjunction of literals on the path to ℓ. For any hole h ∈ [N + 1], define the family
Hh :=

N[
+1

{C : C = Cℓ for some h-leaf ℓ ∈ L(Ti1 )}.

i=1

As in the proof of Theorem 3.6, we have
N +1=

N
+1
X

X

Ẽ[Cℓ ] =i=1 ℓ∈L(Ti1 )

N
+1
X

X

Ẽ[C],

h=1 C∈Hhsince we are summing over all of theP paths in each decision tree. Thus, by averaging, there must be somehole h ∈ [N + 1] with Ẽ[Hh ] := C∈Hh Ẽ[C] ≥ 1 + 1/N . We now break into cases, depending on thehole h and the structure of Hh , extracting a P IGEON⊗k−1 -formulation of P IGEON⊗k in each of them. We
will refer to the P IGEON instances comprising P IGEON⊗k as sub-instances.
Case 1. Ẽ[Hh ] ≥ 1 + 1/N for h = 1. Since h = 1, restricting along any matching term M ∈ H1 forces
some pigeon i in the first sub-instance of P IGEON⊗k
N to fly to hole 1. This means that
⊗k−1,
P IGEON⊗k
N ↾ M ≤ P IGEON N

since we can just map pigeon i to hole 1 in the first instance, and ignore the other pigeons in P IGEON⊗k
N thatwere mapped under the restriction M . On the other hand, as M is a matching of at most d = poly(log(n)) pigeons of P IGEON⊗k+1
to holes, restricting by M leaves us with an instance of P IGEON⊗k+1
that is no easier
n
n
⊗k
⊗k+1
⊗k+1
⊗k+1
↾ M ≥ P IGEON0.99n . Since P IGEON0.99n ≤ P IGEON⊗k+1
than P IGEON0.99n , and therefore P IGEONn
0.99n
trivially, we therefore have
⊗k+1
⊗k+1
P IGEON⊗k↾ M.
0.99n ≤ P IGEON 0.99n ≤ P IGEON n

Composing these reductions together with Equation (3), we have
⊗k−1,
P IGEON⊗k
0.99n ≤ P IGEON N

contradicting the inductive hypothesis.
Case 2. Ẽ[Hh ] ≥ 1 + 1/N for some h ̸= 1. We first assume that there are matching terms M1 , M2 ∈ Hhsuch that M1 M2 ̸= 0, and they witness a collision in at most one of the k + 1 sub-instances comprising
P IGEON⊗k+1. As M1 M2 ̸= 0, M1 and M2 must have come from different trees Ti1 and Tj1 for i ̸= j, andntherefore restricting by M1 M2 maps the ith and j th pigeon of the first sub-instance of P IGEON⊗k
N to hole h.
⊗k
Again, this means that the resulting instance P IGEONN ↾ M1 M2 reduces efficiently to P IGEON⊗k−1, andN
we therefore have
⊗k−1
P IGEON⊗k.
N ↾ M1 M2 ≤ P IGEON N
Our goal now is to prove that
⊗k+1
P IGEON⊗k↾ M 1 M2 .
0.99n ≤ P IGEON n

(4)

⊗k−1
Combining the above two reductions with Equation (3) yields P IGEON⊗k, a contradiction
0.99n ≤ P IGEON N
to the inductive hypothesis.

30Suppose first that M1 and M2 are coherent, meaning that M1 M2 is a matching. In this case, if we restrict
P IGEON⊗k+1
by M1 M2 , we do not witness any collision, but, we have mapped 2d = O(poly(log(n)))
n⊗kpigeons to holes. The resulting instance is therefore no easier than P IGEON⊗k+1
0.99n , and P IGEON 0.99n trivially⊗k+1
reduces to P IGEON0.99n . This means that we have again constructed a reduction from P IGEON⊗k
0.99n to⊗k−1
P IGEONN , proving Equation (4) and contradicting the induction hypothesis.
Next, suppose that M1 and M2 witness exactly one collision in P IGEON⊗k+1. Now, if we restrictn⊗k+1
P IGEONnby M1 M2 we have a collision in one sub-instance, along with mapping d = poly(log(n))
other pigeons to holes. The resulting instance is therefore no easier than P IGEON⊗k
0.99n . Therefore, we have
⊗k+1
shown P IGEON⊗k
≤
P
IGEON
↾
M
M
,
again
proving
Equation(4)
andfinishing
the proof of this
1 2
n
0.99n
case.
Finally, let us suppose that we are not in either of the above two subcases. This means that for all pairs
M1 , M2 ∈ Hh , either M1 M2 is inconsistent (meaning M1 M2 ≡ 0), or, M1 M2 witnesses at least two collisions among the k + 1 sub-instances of P IGEON⊗k+1. In other words, Hh is a d-pairwise-witnessing familynfor P IGEON(⊗k+1,2) with Ẽ[Hh ] ≥ 1 + 1/N . But Theorem 5.3 states that the k-matching pseudoexpectationẼ is d-collision-free (and collision-freeness by definition implies that the pseudoexpectation is at most 1),
which is a contradiction. This completes the proof.
It remains to prove Theorem 5.3; we only sketch the proof as it is an immediate generalization of theproof of Theorem 4.15.
(⊗k,2)

Proof Sketch of Theorem 5.3. We will argue that Ẽ is d-collision free for P IGEONn. The proof is identical to that of Theorem 3.6 and in what remains, we verify that the intermediate lemmas do indeed withstandthe generalization to P IGEON⊗k . Intuitively this should hold as the only thing which has changed is that weare working with k instances of P IGEONn , rather than two, however we are still only searching for a solution
to two instances.
The definition of a matching term is identical to before, but now the conjunctions read variables from anyof the k P IGEON sub-instances instead of just two. As before, a family F of matching terms is d-pairwise
witnessing if for any M1 , M2 ∈ F, M1 M2 = 0 or M1 M2 witnesses a solution in at least two of the ksub-instances of P IGEON(⊗k,2) . It suffices to show that for any pairwise-witnessing family F that Ẽ[F] ≤ 1.
Lemma 4.5 shows that d-pairwise witnessing families are in fact strong pairwise witnessing. In our
setting, what changes is that instead of knowing that for two matchings M1 , M2 ∈ F, that they pairwise
witness two (out of two) P IGEON sub-instances after d additional queries, now M1 , M2 will pairwise witness
some pair of P IGEON sub-instances (out of the k sub-instances). If we restrict to that pair of sub-instances,the proof proceeds identically.
Next, we reduce any strong pairwise witnessing family F, represented by a matching DNF F , to amatching decision tree which strongly represents F . The definition of matching decision trees, and theconstruction of the canonical matching decision tree for F readily generalizes to our setting. Indeed, eachpigeon still has only [n] holes to which it can fly and each hole has [n + 1] potential pigeons, the only
difference is that there are k instances of P IGEON, rather than two. For Lemma 4.12, the induction argument
depends only on the width of the matching DNF F instead of the number of P IGEON instances, and nochange to the argument is necessary. Similarly, Lemma 4.14 works for any incoherent matching DNF.
Finally, Theorem 4.15, Lemma 4.16 and Lemma 4.17, and their subclaims also do not require any modification, as their proofs rely on properties that do not change in the P IGEON(⊗k, 2) setting: the definitionsof conjunction width and incoherency, each pigeon can fly to at most n holes, and each hole can receive at
most n + 1 pigeons.

31

6

Acknowledgements

Noah Fleming, Stefan Grosser, and Robert Robere were supported by NSERC. Toni Pitassi was supported
by NSF AF:Medium 2212136. Part of this work was completed while the authors were attending the Simons
Institute for the Theory of Computing in the Winter 2023 programs on “Meta-Complexity” and “Extended
Reunion: Satisfiability”. The authors thank Mika Göös and Susanna de Rezende for some helpful discussions.

References[AIK04]

Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography in NC0 . In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy,
Proceedings, pages 166–175. IEEE Computer Society, 2004.

[Ajt88]

Miklos Ajtai. The complexity of the pigeonhole principle. In [Proceedings 1988] 29th Annual
Symposium on Foundations of Computer Science, pages 346–355, 1988.

[Ajt96]

Miklós Ajtai. Generating hard instances of lattice problems (extended abstract). In Gary L.
Miller, editor, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory ofComputing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 99–108. ACM, 1996.

[BCE+ 98] Paul Beame, Stephen Cook, Jeff Edmonds, Russell Impagliazzo, and Toniann Pitassi. The
relative complexity of NP search problems. Journal of Computer and System Sciences, 57(1):3–
19, 1998.
[BFH+ 23] Romain Bourneuf, Lukáš Folwarczný, Pavel Hubácek, Alon Rosen, and Nikolaj I.
Schwartzbach. Ppp-completeness and extremal combinatorics. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13,
2023, MIT, Cambridge, Massachusetts, USA, volume 251 of LIPIcs, pages 22:1–22:20. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
[BFI23]

Sam Buss, Noah Fleming, and Russell Impagliazzo. TFNP characterizations of proof systems
and monotone circuits. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer
Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA,volume 251 of LIPIcs, pages 30:1–30:40. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023.

[BIK+ 92] Paul Beame, Russell Impagliazzo, Jan Krajı́cek, Toniann Pitassi, Pavel Pudlák, and Alan R.
Woods. Exponential lower bounds for the pigeonhole principle. In S. Rao Kosaraju, Mike
Fellows, Avi Wigderson, and John A. Ellis, editors, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, pages
200–220. ACM, 1992.
[BIK+ 94] Paul Beame, Russell Impagliazzo, Jan Krajı́ček, Toniann Pitassi, and Pavel Pudlák. Lowerbounds on Hilbert’s Nullstellensatz and propositional proofs. In Proceedings of the 35th Symposium on Foundations of Computer Science (FOCS), pages 794–806, 1994.
[BJ12]

Samuel R. Buss and Alan S. Johnson. Propositional proofs and reductions between NP search
problems. Annals of Pure and Applied Logic, 163(9):1163–1182, 2012.

32

[BJP+ 19] Frank Ban, Kamal Jain, Christos H. Papadimitriou, Christos-Alexandros Psomas, and Aviad
Rubinstein. Reductions in PPP. Inf. Process. Lett., 145:48–52, 2019.
[BK94]Sam Buss and Jan Krajı́ček. An application of boolean complexity to separation problems inbounded arithmetic. In Proceedings of the London Mathematical Society, volume 69, pages
1–21, 1994.

[Bli14]

H. F. Blichfeldt. A new principle in the geometry of numbers, with some applications. Transactions of the American Mathematical Society, 15(3):227–235, 1914.

[BM04]

Joshua Buresh-Oppenheim and Tsuyoshi Morioka. Relativized NP search problems and propositional proof systems. In Proceedings of the 19th IEEE Conference on Computational Complexity (CCC), pages 54–67, 2004.

[CDT09]Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player
Nash equilibria. Journal of the ACM, 56(3):14:1–14:57, 2009.

[CLRS13] Siu On Chan, James R. Lee, Prasad Raghavendra, and David Steurer. Approximate constraint
satisfaction requires large LP relaxations. In 54th Annual IEEE Symposium on Foundations ofComputer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 350–359. IEEE
Computer Society, 2013.
[Das19]Constantinos Daskalakis. Equilibria, fixed points, and computational complexity. In Proceedings of the International Congress of Mathematicians (ICM). World Scientific, 2019.

[DGP09]Constantinos Daskalakis, Paul Goldberg, and Christos Papadimitriou. The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 39(1):195–259, 2009.

[DR23]Ben Davis and Robert Robere. Colourful TFNP and propositional proofs. In Amnon Ta-Shma,
editor, 38th Computational Complexity Conference, CCC 2023, July 17-20, 2023, Warwick, UK,
volume 264 of LIPIcs, pages 36:1–36:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023.

[ER60]Paul Erdös and Richard Rado. Intersection theorems for systems of sets. Journal of the London
Mathematical Society, Second Series, 35:85–90, 1960.

[FKP19]Noah Fleming, Pravesh Kothari, and Toniann Pitassi. Semialgebraic proofs and efficient algorithm design. Foundations and Trends in Theoretical Computer Science, 14(1-2):1–221, 2019.

[GHJ+ 22] Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert
Robere, and Ran Tao. Separations in proof complexity and TFNP. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 November 3, 2022, pages 1150–1161. IEEE, 2022.
[GIPS21] Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, and Rahul Santhanam. On the pseudodeterministic query complexity of NP search problems. In Valentine Kabanets, editor, 36th
Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada(Virtual Conference), volume 200 of LIPIcs, pages 36:1–36:22. Schloss Dagstuhl - LeibnizZentrum für Informatik, 2021.
[GKRS18] Mika Göös, Pritish Kamath, Robert Robere, and Dmitry Sokolov. Adventures in monotone
complexity and TFNP. In Proceedings of the 10th Innovations in Theoretical Computer Science
Conference (ITCS), volume 124, pages 38:1–38:19, 2018.
33

[GM08]

Konstantinos Georgiou and Avner Magen. Expansion fools the Sherali-Adams system: Compromising local and global arguments. Technical report, University of Toronto, 2008.

[Hak85]

Armin Haken. The intractability of resolution. Theor. Comput. Sci., 39:297–308, 1985.

[HV21]

Pavel Hubácek and Jan Václavek. On search complexity of discrete logarithm. In Filippo Bonchi
and Simon J. Puglisi, editors, 46th International Symposium on Mathematical Foundations ofComputer Science, MFCS 2021, August 23-27, 2021, Tallinn, Estonia, volume 202 of LIPIcs,
pages 60:1–60:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.

[Jer16]

Emil Jerábek. Integer factoring and modular square roots. J. Comput. Syst. Sci., 82(2):380–394,
2016.

[JLRX23] Siddhartha Jain, Jiawei Li, Robert Robere, and Zhiyang Xun. Pigeonhole principle and Ramsey
in TFNP. Manuscript in preparation., 2023.
[JLS21]

Aayush Jain, Huijia Lin, and Amit Sahai. Indistinguishability obfuscation from well-foundedassumptions. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd
Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25,
2021, pages 60–73. ACM, 2021.

[JPY88]David Johnson, Christos Papadimitriou, and Mihalis Yannakakis. How easy is local search?
Journal of Computer and System Sciences, 37(1):79–100, 1988.

[KMR17] Pravesh K. Kothari, Raghu Meka, and Prasad Raghavendra. Approximating rectangles by juntas
and weakly-exponential lower bounds for LP relaxations of csps. In Hamed Hatami, Pierre
McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposiumon Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 590–
603. ACM, 2017.
[KNY19] Ilan Komargodski, Moni Naor, and Eylon Yogev. White-box vs. black-box complexity of search
problems: Ramsey and graph property testing. J. ACM, 66(5):34:1–34:28, 2019.
[LRS15]James R. Lee, Prasad Raghavendra, and David Steurer. Lower bounds on the size of semidefinite
programming relaxations. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings ofthe Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland,
OR, USA, June 14-17, 2015, pages 567–576. ACM, 2015.

[Mor01]

Tsuyoshi Morioka. Classification of search problems and their definability in bounded arithmetic. Master’s thesis, University of Toronto, 2001.

[MP91]

Nimrod Megiddo and Christos Papadimitriou. On total functions, existence theorems and computational complexity. Theoretical Computer Science, 81(2):317–324, 1991.

[Pap94]

Christos Papadimitriou. On the complexity of the parity argument and other inefficient proofs
of existence. Journal of Computer and System Sciences, 48(3):498–532, 1994.

[PPY23]

Amol Pasarkar, Christos H. Papadimitriou, and Mihalis Yannakakis. Extremal combinatorics,
iterated pigeonhole arguments and generalizations of PPP. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT,
Cambridge, Massachusetts, USA, volume 251 of LIPIcs, pages 88:1–88:20. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2023.
34

[Pud15]

Pavel Pudlák. On the complexity of finding falsifying assignments for Herbrand disjunctions.
Archive for Mathematical Logic, 54(7-8):769–783, 2015.

[Raz98]Alexander A. Razborov. Lower bounds for the polynomial calculus. Comput. Complex.,
7(4):291–324, 1998.

[Raz01]

Alexander A. Razborov. Proof complexity of pigeonhole principles. In Werner Kuich, Grzegorz
Rozenberg, and Arto Salomaa, editors, Developments in Language Theory, 5th International
Conference, DLT 2001, Vienna, Austria, July 16-21, 2001, Revised Papers, volume 2295 ofLecture Notes in Computer Science, pages 100–116. Springer, 2001.

[Reg05]

Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In
Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposiumon Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 84–93. ACM, 2005.

[SZZ18]Katerina Sotiraki, Manolis Zampetakis, and Giorgos Zirdelis. PPP-completeness with connections to cryptography. In Proceedings of the 59th IEEE Symposium on Foundations of Computer
Science (FOCS), pages 148–158, 2018.

A

SOS Bounds for Nonadaptive Pigeon

For a clause C =Wi∈I xi ∨W

j∈J ¬xj , the conjunction C isQi∈I (1 − xi )Qj∈J xj .

Definition A.1. Given an unsatisfiable CNF formula F = C1 ∧ . . . ∧ Cm , a Sum-of-Squares derivation of apolynomial p is given by a list of polynomials p1 , . . . , pm , q1 , . . . , qk such thatXX
C i pi +qj2 = p,
i∈[m]

j∈[k]

where all operations are done in multilinear polynomial arithmetic (so x2i = xi ) over R. A Sum-of-Squares
refutation of F is a derivation of the polynomial −t for some t > 0. The degree of the proof is the maximum
degree among the C i pi and qj2 , and the degree required by Sum-of-Squares to refute F is the minimum
degree of any Sum-of-Squares proof of F .
Let [n]0 = {0, . . . , n}. For ease of exposition we will work with n-ary variables p1i , p2i ∈ [n − 1]0
encoding the holes to which the ith pigeon of the first instance and the ith pigeon of the second instance aresent to. These will each be represented by log n boolean variables p1i,ℓ , p2i,ℓ for ℓ ∈ [log n] representing theℓth bit of p1i and p2i respectively. We will denote by [[p1i ̸= h]] the disjunction (p1i,1 )h1 ∨ . . . ∨ (p1i,log n )hlog nstating that pigeon i of the first instance does not fly to hole h, where h1 . . . hlog n is the binary encoding ofh, and (p1i )hi = p1i if hi = 1 and ¬p1i if hi = 0. As well, [[p1i = h]] is the conjunction ¬[[p1i ̸= h]].
P IGEON⊗2n is represented by the unsatisfiable CNF formula formed by the conjunction of the following
clauses,[[p1i ̸= h]] ∨ [[p1j ̸= h]] ∨ [[p2k ̸= h′ ]] ∨ [[p2ℓ ̸= h′ ]] ∀i ̸= j ∈ [n − 1]0 , k ̸= ℓ ∈ [n − 1]0 , h, h′ ∈ [n − 1]0 ,[[pαi ̸= 0]]∀α ∈ {1, 2}, i ∈ [n − 1]0 .

Theorem A.2. There is a O(log n)-degree Sum-of-Squares proof of P IGEON⊗2n .
We make some preliminary observations about our n-ary variables.
(a) [[pαi = h]]2 = [[pαi = h]], as [[pαi = h]] is a conjunction and we are working in multilinear arithmetic.
35

(b)

α
α
h∈[n] [[pi = h]] = 1, as we are summing over all conjunctions over the variables pi,j for j ∈ [log n].

P

The following claim will allow us to transform the clauses of P IGEON⊗2n into a more useful form.
Claim A.3. There is a O(log n)-degree Sum-of-Squares derivation of
1 − [[p1i = h]][[p1j = h]] − [[p2k = h′ ]][[p2ℓ = h′ ]]′from P IGEON⊗2n for every h, h , i ̸= j, k ̸= ℓ ∈ [n].

Proof. Consider the square polynomial(1 − [[p1i = h]][[p1j = h]])2 (1 − [[p2k = h′ ]][[p2ℓ = h′ ]])2=(1 − [[p1i = h]][[p1j = h]])(1 − [[p2k = h′ ]][[p2ℓ = h′ ]])(By (a))=1 − [[p1i = h]][[p1j = h]] − [[p2k = h′ ]][[p2ℓ = h′ ]] + [[p1i = h]][[p1j = h]][[p2k = h′ ]][[p2ℓ = h′ ]]=1 − [[p1i = h]][[p1j = h]] − [[p2k = h′ ]][[p2ℓ = h′ ]](By the first axiom of P IGEON⊗2n )We now prove the theorem.
Proof of Theorem A.2. First, we derive that each pair of holes receives at most one pigeon. Next, we will
derive that each pigeon goes to at least one hole. Summing over the 2n pigeons and 2(n − 1) non-zero holes
will complete the proof.
For a fixed h, h′ ∈ [n − 1],

2 
2
X
X
1−
[[p1i = h]] + 1 −[[p2i = h′ ]]i∈[n−1]0=2 −Xi∈[n−1]0[[p1i = h]] +[[p1i = h]][[p1j = h]] −i̸=ji∈[n−1]0

=1−

X

X

[[p1i = h′ ]] +X[[p2i = h′ ]][[p2j = h′ ]]i̸=ji∈[n−1]0X[[p1i = h]] −i∈[n−1]0X[[p2i = h′ ]].

(By Claim A.3)

i∈[n−1]0

Summing over all h, h′ ∈ [n − 1], we getXX2(n − 1) −[[p1i = h]] −=2(n − 1) −X

X[[p2i = h′ ]]h′ ∈[n−1] i∈[n−1]0h∈[n−1] i∈[n−1]0

X

X
X

X

h′ ∈[n−1]0 i∈[n−1]0[[p1i = h]] −h∈[n−1]0 i∈[n−1]0[[p2i = h′ ]],(5)⊗2
where the second line follows by
P the secondαaxiom of P IGEON .
On the other hand, by (a) h∈[n−1]0 [[pi = h]] − 1 = 0, and so summing over all of the pigeons weobtain
2
2
X  X
X  X
[[p1i = h]] − 1 +[[p2i = h]] − 1i∈[n−1]0=i∈[n−1]0=h∈[n−1]0X X[[p1i = h]] − 1 +Xh∈[n−1]0Xi∈[n−1]0 h∈[n−1]0[[p1i = h]] +i∈[n−1]0h∈[n−1]0X Xi∈[n−1]0X

X

i∈[n+1]0 h∈[n−1]0

Adding this to (5) derives −2.
36[[p2i = h]] − 1h∈[n−1]0[[p2i = h]] − 2n.

We remark that Sum-of-Squares is also capable of proving more general adaptive problems in FPPPP
such
layer,
 as the following: we are given k layers of instances of P IGEONn , with one instance on the firstn
th layerinstanceonthesecond,
and
so
on.
A
solution(apairofcollidingpigeons)toaninstanceonthei2
points to a P IGEON instance on the (i + 1)st layer to solve. The final solution consists of a sequence of ksolutions, for the k P IGEON instances, one per layer, that are associated with the “path” from layer 1 to thelast layer.

37