The pigeonhole principle, which asserts that there is no injective function f : [m] → [n] for m > n, is a cornerstone problem in the study of proof complexity. It is typically encoded as unsatisfiable conjunctive normal form formula (CNF), henceforth denoted PHP m n , on the variables y i,j , each of which is an indicator that "pigeon" i is mapped to "hole" j.
It is well known that any refutation of PHP n+1 n using resolution proofs requires size 2 Ω(n) [13] and the same asymptotic bound holds for all m that are O(n) [6]. On the other hand, if we allow our proof system to reason about linear inequalities (for example using cutting-planes proofs), then it is easy to see that refuting PHP n+1 n becomes easy -indeed, there exist polynomial size refutations of PHP n+1 n . Despite the pigeonhole principle having short cutting-planes refutations, the related clique-coloring formulas, which state that a graph cannot have both k-cliques and k -1-colorings, requires exponential-size cutting-planes refutation [26]. 1 The clique-coloring formula can be viewed as a kind of indirect pigeonhole principle: The k nodes of the clique correspond to the pigeons and k -1 colors correspond to the holes, but the representation of possible mappings is quite indirect.
It is natural to wonder about the extent to which indirection is required for the pigeonhole principle to be hard for cutting-planes reasoning. As part of studying techniques for cutting-planes proofs, Hrubeš and Pudlák [17] considered a very natural compact and direct way of expressing the pigeonhole principle, known as the bit or binary pigeonhole principle 2 . The bit pigeonhole principle analog of PHP m n (henceforth denoted BPHP m n ) has m log n variables x i,j for i ∈ [m], j ∈ [log n] and the principle asserts that, when we organize these variables as an m × [log n] matrix, the rows of the matrix all have distinct values. BPHP m n is the following CNF formula: for each i ̸ = j ∈ [m], include the clauses of a CNF encoding that x i ̸ = x j . One can achieve this by including a clause for each α ∈ {0, 1} log n expressing that x i ̸ = α ∨ x j ̸ = α. The end result is a CNF with ( m 2 )n clauses of size 2 log n. Using techniques related to those of [26], Hrubeš and Pudlák [17] showed that BPHP m n requires cuttingplanes refutations of size 2 Ω(n 1/8 ) for any m > n, proving that even a very direct representation of the pigeonhole principle is hard for cutting-planes proofs. Their arguments, like those of Pudlák, also apply to any proof system that has proof lines consisting of integer linear inequalities with two antecedents per inference that are sound with respect to 01-valued variables; such proofs are known alternatively as semantic cutting-planes proofs or Th(1) proofs [2].
Recently, Dantchev, Galesi, Ghani, and Martin [8] exhibited a 2 Ω(n/ log n) lower bound on the size of any general resolution refutation of BPHP m n for all m > n. In fact, they showed that BPHP m n requires proofs of size 2 Ω(n 1-ε ) for a more powerful class of proof systems that extend resolution by operating on k-DNFs (known as Res(k) proofs) for k ≤ log 1/2-ε ′ n. (Note that any sound proof system operating on DNFs requires size at least 2 n Ω (1) to refute PHP n+1 n [25,21,15].) In addition, [8] showed that BPHP m n has no refutations in the Sherali-Adams proof system [29] of size smaller than 2 Ω(n/ log 2 n) . Finally, just as PHP m n has polynomial-size Sum-of-Squares refutations [12], Dantchev et al. showed that BPHP m n has polynomial-sized Sum-of-Squares refutations.
Given the large lower bounds for resolution, Res(k), and Sherali-Adams refutations of BPHP m n , it is natural to ask the extent to which the sub-exponential lower bounds can be improved for cutting-planes proofs; how close to a 2 Ω(n) lower bound is possible?
In prior work there has been progress towards this question for the restricted class of tree-like refutations. Tree-like proofs require that any time an inequality is used, it must be re-derived (i.e., the underlying graph of deductions is a tree); the polynomial-size cutting-planes refutations of PHP n+1 n can be made tree-like. In contrast, Itsykson and Riazanov [19] showed that BPHP m n requires tree-like cutting-planes refutations of size 2 Ω( √ n) when m ≤ n + √ n. Our first result pushes this bound almost to its limit. Specifically, we prove that any tree-like semantic cutting-planes refutation of BPHP m n requires size 2 n 1-o (1) whenever m ≤ n + 2 2
In order to show this, we utilize a well-known connection between tree-like refutations and communication complexity. While the results of [19] for cutting planes rely on two-party communication complexity (and number-on-forehead multiparty communication for other results that we mention below), our stronger results are based on multiparty number-in-hand communication. In particular they are based on a similar natural collision-finding communication problem Coll k m,ℓ , in which each player p ∈ [k] in the number-in-hand model receives an input in x (p) ∈ [ℓ] m , and their goal is to communicate and find a pair
Such a communication problem is well-defined (in the sense that such a pair i, j always exists) when m > ℓ k . This collision-finding problem is intimately related to the unsatisfiable BPHP m n formula via the following natural search problem associated with any unsatisfiable CNF formula: Given unsatisfiable CNF φ, the associated search problem Search φ takes as input a truth assignment α to the variables of φ and requires the output of the index of a clause of φ that is falsified by α. In particular the connection follows by considering a natural k-party number-in-hand communication game that we denote by Search k φ wherein the assignment α to the variables of φ is evenly distributed among the k players. and the players must communicate to find an answer for Search φ (α).
It is not hard to see that if we have a communication protocol solving Search k BPHP m n (α) then such a protocol also solves Coll k m,n 1/k on input α. Our first result is a lower bound on Coll k m,n 1/k that holds even when we allow randomized protocols. Theorem 1.1. The randomized number-in-hand communication complexity of Coll
We pause here to note that this bound is nearly tight. There is a deterministic protocol wherein the first player sends a subset of coordinates of size ⌈m/n 1/k ⌉ in which their inputs are all equal. This requires log
Player two then announces a subset of these coordinates on which they are equal of size ⌈m/n 2/k ⌉. The players can continue in this manner until they have found a collision (which is guaranteed by the pigeonhole principle). Note that the amount of communication is bounded by a geometric series, and is dominated by the first term, which results in communication O(n 1-1/k log n /k). This shows that up to logarithmic factors and a factor of 2 k , Theorem 1.1 is tight.
We state here a simplified corollaryfoot_1 of Theorem 1.1 which formalizes our lower bounds for cutting-planes refutations of BPHP m n .
Theorem 1.2. Any tree-like semantic cutting-planes refutation of BPHP m n requires size
We remark that Itsykson and Riazanov [19] utilized the same connection between communication and proof complexity to achieve their results. They were also interested in a k-party number-on-forehead version of Coll k m,ℓ (in particular, in their version, the matrices are added rather than concatenated), which leads to weaker lower bounds in stronger proof systems Th(k -1) that manipulate degree k -1 polynomial inequalities.
Itsykson and Riazanov also left as an open problem whether their bounds for Search BPHP m n could be extended to the regime of the "weak" pigeonhole principle when m = n + Ω(n). Göös and Jain [10] first answered this in the affirmative, giving an Ω(n 1/12 ) lower bound on the randomized communication complexity of Coll 2 2n,n 1/2 . Yang and Zhang [34] subsequently improved this to an Ω(n 1/4 ) bound, which is tight for randomized computation. Because of the connection between communication protocols and tree-like communication, Yang and Zhang's bound showed that any tree-like cutting planes refutation of BPHP m n requires size 2 Ω(n 1/4 ) . We extend the lower bounds of Yang and Zhang for all k ≥ 2 as follows:
This bound, whose proof combines techniques of Yang, Zhang, and Wang [33,34], is much weaker than that of Theorem 1.1 when m is close to n but it is tight, up to an O(log n) factor, for randomized protocols when m is n + Ω(n). For k = Ω(log n), it also implies the following proof complexity bound which asymptotically matches the bound of [19], but applies for all m > n.
Corollary 1.4. For all m > n, any tree-like semantic cutting-planes refutation of BPHP m n requires size 2 Ω( √ n) .
Our second result improves on the 2 Ω(n 1/8 ) lower bound on the size of cutting-planes refutations of BPHP m n (for all m > n) of Hrubeš and Pudlák [17], and subsumes the 2 Ω(n 1/4 ) lower bound for tree-like proofs of Yang and Zhang [34]. Hrubeš and Pudlák used the method of interpolation involving a version of the method of approximation due to Jukna [20]. On the other hand, we use a bottleneck-counting method inspired by recent work of Sokolov [31] that refines a method introduced by Haken and Cook [14].
Theorem 1.5. Any semantic cutting planes refutation of BPHP m n requires size at least 2 n 1/foot_2 / √ 2-2 , for any m > n.
We prove Theorem 1.5 via a connection between cutting-planes refutations and certain types of DAGlike communication protocols [16,30]. Specifically, we prove a lower bound on the size of any two party triangle-DAG protocol computing Search BPHP m n . We define such protocols formally in Section 2.3. For now, we state the connection as the following proposition, originally due to Sokolov and Hrubeš and Pudlák [30,16]. Its proof can be found in Section 2.3 for completeness. Proposition 1.6. [30,16] Given a semantic cutting planes refutation for CNF formula φ of size s and any partition of the variables of φ into two sets, there is a size s triangle-DAG computing Search φ .
In our setting, for BPHP m n , there is a natural partition of the variables such that each clause has exactly half of its variables coming from V x and half of its variables coming from V y . This can be achieved, for example, by letting V x be the set of variables corresponding to the first 1 2 log n columns of the matrix associated with BPHP m n . In light of Proposition 1.6, we derive Theorem 1.5 by proving the following.
Proof complexity studies how the size required for refutations of unsatisfiable formulas depends on the size of the formulas themselves. The size of a refutation in general depends on the allowable structure (lines, derivation rules, etc.) of a proof. In general, a proof system corresponds to a polynomial-time verifier that can check proofs of a certain format. It generally suffices to derive refutations of unsatisfiable CNF formulas; so it is usual to focus solely on inputs of this form. For most proof systems, a sequence of deductions can be thought of as a directed graph, where two (or possibly more) lines (whether given or derived) are combined soundly to create a new line. The underlying graph then has edges pointing from the derived inequality to its antecedents. 4 We say that a proof is tree-like if every inequality is used as an antecedent at most once in the proof -that is, if we want to use an inequality twice, we must derive it twice.
For example, in the resolution proof system the lines are clauses, and we have the derivation rule
A more powerful proof system is the cutting planes proof systemfoot_3 , denoted CP, where lines are linear inequalities. Clauses can be trivially converted into linear inequalitiesfoot_4 but, more generally, cutting planes can start with any system of inequalities Ax ≤ b where A is a matrix with integer entries. We say that the system is unsatisfiable iff it is unsatisfiable for any x ∈ {0, 1} n . The most basic form of the cutting planes proof system consists of three rules: addition of inequalities, multiplication of inequalities by positive integers, and most crucially, the rounded division rule, also known as the Gomory-Chvátal rule. The rounded division rule is the simple but powerful observation that if a 1 , . . . , a n are all integers with a common factor c, and we have the inequality a T x ≤ b, then we can derive that 1 c a T x ≤ ⌊ b c ⌋. In general, there are many more sound derivation rules for integer/linear inequalities than just rounded division (such as saturation [9] for example), and even more generally, one may allow any sound derivation rule for linear inequalities, which yields what is known as semantic cutting planes or Th(1) -we use the two names interchangeably.
There is a well-known connection between communication complexity and tree-like proofs, which we will now detail. Given any unsatisfiable formula φ, an assignment α to the variables can be distributed among k players, who must then communicate in order to find a a violated clause in φ. This is a search problem, and is denoted Search φ (α). Short tree-like proofs of the unsatisfiability of φ can often be converted into short protocols for Search φ using standard techniques.
For example, a short tree-like proof of unsatisfiability of φ using the resolution rule naturally corresponds to a decision tree for finding a violated clause of φ in the following way. For every derivation of the form (A ∨ x) ∧ (B ∨ ¬x) ⊢ (A ∨ B) where A ∨ B is known to be false, we query x in order see whether A ∨ x or B ∨ ¬x is necessarily false. We can continue in this manner, from the root of the tree-like refutation, until we hit an unsatisfied clause in the original formula.
On the other hand, tree-like semantic cutting planes refutations naturally correspond to threshold decision trees, which we now define.
A threshold decision tree is a tree whose vertices are labeled with inequalities of the form a 1 x 1 + • • • a n x n ≤ b where a 1 , . . . , a n , b are integers. Edges are labelled with 0 or 1, and leaves are axioms of a system of inequalities Ax ≤ b.
We traverse a threshold decision tree by computing the threshold function at the root, following the corresponding edge, and continuing in this manner until we hit a leaf. We say that a threshold decision tree computes the search problem for a formula φ if this process leads to a leaf corresponding to a violated clause in φ.
First, we have the following well-known lemma, which states that one can derive a low-depth threshold decision tree from a small Th(1) refutation. 7Proposition 2.2. Given a size S tree-like Th(1) refutation of an unsatisfiable system Ax ≤ b, there is a depth O(log S) threshold decision tree finding a violated axiom. Proposition 2.2 goes back to the work of Impagliazzo, Pitassi, and Urquhart [18], and can also be found for instance in [20]. We omit the proof, but the idea is a common one: find a node in the tree with roughly half (between 1/3 and 2/3) of the leaves as its descendants, make that the root of the threshold decision tree, and recurse.
We mainly focus on k-party number-in-hand communication, wherein each player p receives an input x (p) , and the players' goal is to communicate as little as possible in order to compute a known function or relation involving their collective inputs. In general, players may have access to shared randomness, and we allow incorrect answers with probability 1/3.
An important function for us is the number-in-hand disjointness problem with k players and input size n, henceforth denoted DISJ k n . This is the communication problem wherein each player and input in {0, 1} n , and they must decide if there exists a coordinate i for which they all have a 1 in that coordinate. Disjointness in general is an extremely well-studied problem [7,27], and for the specific case of the NIH model, we have the following lower bound due to Braverman and Oshman.
Our results rely on the following connection between threshold decision trees for finding violated clauses and k-party NIH communication. It is closely related to previous work. Lemma 2.4. For x ∈ {0, 1} n , if an unsatisfiable system Ax ≤ b on has a threshold decision tree of depth d ≤ n finding a violated axiom, then for any partition of the input variables into k parts there is a randomized protocol for
Lemma 2.4 is similar for example to Lemma 5 in [18] or Lemma 19.11 in [20], but is slightly stronger, so we include a proof. The idea is that the players can use the given threshold decision tree to construct a protocol. Without loss of generality, using a well-known theorem of Muroga [23] without communication the players can replace each of the inequalities in the decision tree with an equivalent one over the Boolean hypercube with coefficients that are not too large.
The players then start at the root and evaluate each associated inequality using an efficient randomized protocol to evaluate each threshold function with high probability and moving to the appropriate child node until it reaches a leaf. Such a protocol dates back to Nisan [24] and was tightened by Viola [32].
We first state the results of Muroga and Viola required to formalize this construction.
Proposition 2.5 ([22, 23]). Consider a threshold function f : {0,
In particular, Proposition 2.5 implies that we may assume in a Th(1) proof that, up to a factor of two in the size, every derived inequality has coefficients of magnitude at most O(n n ).
Then there is a randomized number-in-hand protocol with error at most ε that determines whether ∑ p x (p) > s and communicates O(k log k log(n/ε)) bits.
Corollary 2.7. Suppose that each player p ∈ [k] receives an input x (p) ∈ [2 t ]. Then they can execute a randomized number-in-hand protocol to determine whether ∑ p a p x (p) ≤ b, where each |a p | ≤ 2 w with error at most ε using at most O(k log k log((w + t)/ε)) bits of communication.
Proof of Lemma 2.4. Given a threshold decision tree of depth d, we simply traverse it from the root. For each inequality, if the magnitudes of its weights are not bounded by 2 O(n log n) , then we replace it with an equivalent threshold function whose weights are bounded using Proposition 2.5. Then, using Corollary 2.7, the players communicate O(k log((n log n)/ε) log k) bits to compute the threshold function with error probability ε. Setting ε = Θ(1/d) and continuing in this manner, by a union bound the threshold functions are all computed correctly with constant probability.
Using the assumption that d ≤ n, this yields a protocol communicating O(dk log k log n) bits.
Given a system of unsatisfiable inequalities Ax ≤ b, and a partition of an assignment α ∈ {0, 1} n between k players, there is a natural (number-in-hand) communication game wherein players must communicate to a find an axiom violated by α. Lemma 2.4 implies the following result connecting communication complexity and proof complexity. Lemma 2.8. For any partition of n variables into k parts, if Search k N I H (Ax ≤ b) requires t bits of communication, then any tree-like Th(1) refutation of Ax ≤ b requires size 2 Ω(t/(k log k log n) ).
Proof. By Proposition 2.2, given a size S tree-like Th(1) proof, we get a depth d = O(log S) threshold decision tree finding a violated axiom. By Lemma 2.4, there exists a communication protocol finding a violated axiom using O(log S k log k log n) bits of communication. This implies that log(S)k log k log n ≥ ct for constant c, which in turn implies S is 2 Ω(t/(k log k log n) , as desired.
Given a bipartite domain X × Y, a triangle T ⊆ X × Y is any set that can be written as T = {(x, y) : a T (x) < b T (y)} for some labelling a T : X → R and b T : Y → R.
A triangle-DAG computing a search problem Search ⊆ (X × Y × O) is a directed acyclic graph D of fan-out at most 2 where each node u ∈ D is associated with a triangle T u ⊆ X × Y satisfying the following:
• there is a distinguished root node r with fan-in zero, and T r = X × Y, and
• each sink node u is labeled with an output o such that T u ⊆ Search -1 (o).
Given these definitions, we restate Proposition 1.6 and include its proof for completeness. Proposition 1.6. [30,16] Given a semantic cutting planes refutation for CNF formula φ of size s and any partition of the variables of φ into two sets, there is a size s triangle-DAG computing Search φ .
Proof. Let D be the DAG associated with the semantic CP refutation of φ. As we usually do, we orient the edges so that the last line of the proof, 0 ≥ 1, is the root of D. Each node u ∈ D is associated with some linear inequality of the form f (x) + g(y) ≥ c. If we then let a T h (x) = f (x)c and b T h (y) = -g(y), then we have that (x, y) ∈ T u iff f (x) + g(y) < c, i.e iff (x, y) does not satisfy the inequality associated with u.
By definition, the root of D is associated with X × Y. Since the inequalities corresponding to the children v and v ′ of node u imply the inequality associated with u, at least one of the children must not be satisfied by (x, y), i.e. we have that
Definition 2.9. For a distribution X defined on space Ω, define its min-entropy to be H ∞ (X)
.
Conversely, define the deficiency of X to be D ∞ (X)
In this section we prove Theorem 1.1, which we now recall.
Theorem 1.1. The randomized number-in-hand communication complexity of
The idea for the proof is to exhibit a random reduction from the decision problem DISJ k m k-1 to the collision problem. This is analogous to the approach of Itsykson and Riazanov [19] for number-on-forehead communication complexity which used lower bounds for disjointness in that model and a randomized decision-to-search reduction paradigm introduced by Raz and Wigderson [28] to prove lower bounds on the monotone depth complexity of matching. The details and parameters of our reduction are necessarily quite different.
In our setting, we embed k players' inputs to a disjointness problem into k matrices such that, when these matrices are concatenated, the resulting matrix has distinct rows if and only if the players' inputs were disjoint. We can then add a few "fake" rows to this matrix and run our algorithm for Coll k m,n 1/k , and see if the collisions it finds involve the fake rows or not. If so, we conclude that the inputs were disjoint and if not, we know that they were not disjoint.
The following key combinatorial lemma allows us to carry out the first step of this process. The players get x (1) , . . . , x (k) ⊆ [m k-1 ] (viewed as bit strings of length m k-1 ), and need to determine whether x (1)
First, we define
where we have repeated the same row 2 k times.
i , . . . , x
i ) from Lemma 3.1. Note that each player p knows the p-th column of M k (x
i ) for all i, but without communication the other players do not know this column.
Then we can define
2 , . . . , x
2 ) B m k (2m -1) . . . . . . . . . . . .
Observe that each player p can construct their "part" of this matrix without communicating by constructing the p-th column of every M S i k matrix (which only depends on x (p) ), and then taking the the p-th part of each of the B m k (j) matrices.
Lemma 3.1 lets us connect the distinctness property of this matrix with the disjointness property of the players' inputs. Claim 3.2. If (x (1) , . . . , x (k) ) are disjoint, then M has distinct rows.
Proof. The only possible collisions happen in every group of 2 k rows, since B m k (j) has every row different from B m k (i) for all i ̸ = j. Within these groups, by Lemma 3.1, if the inputs are disjoint then there are no collisions.
Claim 3.3. If X is not disjoint, then there are at least 2 k-1 m pairs of colliding rows in M.
Proof. Any coordinate i for which x (p) i = 1 for all p generates S i = ∅, which by Lemma 3.1 generates 2 k-1 m such pairs, since input i was repeated m times.
We cannot run any collision protocol for M yet, as there are not guaranteed collisions. To address this, the players use shared randomness to put an additional 2 k-1 m rows at the bottom of M. These rows will be chosen randomly with the following two properties:
1. Each fake row will be distinct.
2. Each player's "part" of the matrix (which consists of log m + 1 columns) when restricted to these rows will repeat the 2m unique possible bit strings an addition 2 k-1 m/(2m) = 2 k-2 times. 8Denote this new matrix M. M now has "fake" collisions which involve any of the last 2 k-1 m rows. Let A denote the randomized protocol solving the Coll k (2m) k +2 k-1 m,2m problem. Observe that if the inputs are disjoint, then the only collisions in M involve fake rows. The players would like to feed their parts of this matrix into A and conclude that their inputs are disjoint if the output involves a fake row, and conclude that they were not disjoint if the output involves two non-fake rows. However, this is problematic, as we have no guarantees over how A behaves, and it could always find a collision involving one of the last 2m rows (which it knows are fake), regardless of if there are other collisions.
This necessitates the following random shuffling.
1. Each player applies (the same) random permutation π :
which shuffles the rows of M.
2. Each player applies an individual random permutation π (p) : [2m] → [2m] to each of their rows. Note that this preserves collisions/distinctness in the concatenation.
Denote ⃗ π := (π, π (1) , . . . , π (k) ), and call this final matrix M ⃗ π . Algorithm: The algorithm for disjointness is as follows: the players use their inputs and shared randomness to compute (without communication) their respective parts of 5 independent copies of an M ⃗ π constructed in the above manner, and run A using these as inputs. The players then examine the outputs (i 1 , j 1 ), . . . (i 5 , j 5 ) of the algorithm on these five inputs. They then exchange an additional O(k log m) bits to determine if each claimed collision actually was a collision. Finally, if any of the claimed collisions were actually collisions on rows that were not fake (under the appropriate permutation), then the players can conclude with certainty that their inputs were not disjoint. Otherwise, if A only ever finds colliding pairs that involve a row the players know is fake (or otherwise fail to find any collisions), then players guess that (x (1) , . . . , x (k) ) were disjoint.
We analyze one iteration of the algorithm. Suppose A has error probability at most 1/3 -that is, with probability at least 2/3, it outputs two rows i, j that are equal.
Suppose (x (1) , . . . , x (k) ) are disjoint. Then by assumption, A finds a collision with probability at least 2/3, and we know this collision will always involve a fake row by Claim 3.2. Therefore the players will correctly output that their inputs were distinct with probability at least 2/3, and this is only improved by the five-fold repetition.
Otherwise, suppose that the players' inputs were not disjoint. Suppose further that A successfully finds a collision -this happens with probability at least 2/3. Recall that by Claim 3.3 M ⃗ π will have at least 2 k-1 m distinct pairs of real collisions. Adding the 2 k-1 m fake rows produced additional "fake" collisions. These fake rows could have created up to 2 k-1 m additional unique pairs of fake collisions, or could have "joined" the real collisions, creating up to 2 k-1 m groups of 3 equal rows in M ⃗ π . If A outputs a collision from one of the groups of three, then because we applied random permutations to the rows, it is equally likely to have chosen any of the 3 possible pairs. Therefore, with probability at least 1/3, it outputs a real collision, and the players successfully discover that they are not disjoint. Otherwise, if A outputs one of the unique collision pairs, then (again because we have applied random permutations to the rows), any such unique collision is equally likely to be output. If t of the fake rows formed a group of three with real collisions, then that leaves at most 2 k-1 mt fake rows to collide with a different unique row. It also leaves 2 k-1 mt untouched real collisions, so A outputs a real collision with probability at least 1/2. Either way, the probability that A outputs a real collision is at least 2/3 • 1/3 = 2/9.
Therefore, after repeating this 5 times independently, the probability of seeing at least one real collision is at least 1 -(7/9) 5 > 2/3.
Let n := (2m) k . We have shown that if Coll k m, ℓ with input size m = 2 k m k + 2 k-1 m = n + 2 k-2 n 1/k can be solved with o(n 1-1/k log k/2 k ) communication, then we can solve the decision disjointness problem with o(n 1-1/k log k/2 k ) + O(k log m) which is at most o(m k-1 log k), contradicting the Ω(m k-1 log k) lower bound from Theorem 2.3.
We first recall Lemma 3.1. Proof. Let E k ⊆ {0, . . . , k -1} be the set of integers with an even number of 1s in their binary representation.
Define
where y i is the i-th smallest number in E k .
We pause here to note that each of the columns of M 1 k are actually each the truth table of a linear function. Let f 1 : {0, 1} k → {0, 1} be the linear function f 1 (x) = ⟨x, e 1 ⟩, where e 1 is the first standard basis vector. Then we can describe the first column of M 1 k as the truth table of f 1 . More generally, we have that for i < k the i-th column of M 1 k is the truth table of f i (x) = ⟨x, e i ⟩, and the last column is the truth table of
If we define F 1 k to be the matrix whose column i is the vector whose inner product we are taking with x in f i , and B k ∈ F 2 k ×k 2 whose rows are the binary strings written in order, then we have that
where all operations are over F 2 . M 1 k has repeated rows precisely because F 1 k has linearly dependent columns. With this perspective in mind, if we can find a k × k matrix F 0 k over F 2 such that replacing any (nonzero) number of columns of F 1 k with corresponding columns in F 0 k produces a matrix with linearly independent columns, then we are done, as we can let M 0 k := B k F 0 k .
We define F 0 k to be the following lower triangular matrix:
Clearly F 0 k is full rank. We claim that replacing any set nonempty set S of columns of F 1 k with the corresponding columns in F 0 k produces a matrix F S k with linearly independent columns. Consider arbitrary k, and arbitrary nonempty S ⊆ [k].
Case 1: Suppose k ∈ S, that is, the last column of F S k is e k . Then our matrix is lower triangular with 1s on the diagonal, and so has linearly independent columns.
Case 2: Suppose k ̸ ∈ S, that is, the last column of
In this case, the first k -1 columns are lower triangular with 1s on the diagonal, and therefore their span is equal to span{e 1 , . . . , e k-1 }. It suffices then to show that also e k is in the column span. Towards this goal, take the minimal 0 < i < k such that i ∈ S, and observe that summing the first i columns of F S k equals ⃗ 1, the all 1s vector. Adding this to the last column produces e k , so we are done.
In this section, we prove the following more detailed version of Theorem 1.2. Lemma 2.8 then says that any tree-like semantic cutting planes proof of the unsatisfiability of BPHP m n must have size at least 2 Ω(t/(k log k log n) . By Theorem 1.1, t = Ω(n 1-1/k 2 -k log k). Plugging this in yields that the tree-like size must be at least 2 Ω(n 1-1/kfoot_7 -k /(k log n) .
From Theorem 4.1 we achieve Theorem 1.2, which we restate now.
Corollary 4.2. Any tree-like semantic cutting planes refutation of BPHP m n requires size
In this section, we prove Theorem 1.7, which we restate here for convenience. Before proving Theorem 1.7, we need the following notion of triangle slices. For a triangle T ⊆ X × Y and a given x ∈ X, we define the slice T x to be T ∩ ({x} × Y), and define the slice T y analogously. Note that for any triangle T defined by functions a and b there is a natural total pre-order on X where x ⪯ x ′ iff a(x ′ ) ≤ a(x) and hence T x ⊆ T x ′ ; similarly, there is an total pre-order on Y where y ⪯ y ′ iff b(y) ≤ b(y ′ ) and hence T y ⊆ T y ′ . This immediately implies the following. Proposition 5.1. Given a triangle T, if y ∈ Y is such that |T y | is maximized, then for all (x, y ′ ) ∈ T we have (x, y) ∈ T.
We will have the following proposition. Proposition 5.2. For any triangle T and rectangle R, T ∩ R is a triangle.
The proof of Theorem 1.7 uses the bottleneck counting method of Haken and Cook for cutting planes proofs [14] as adapted for direct use on triangle-DAGs by Sokolov [31].
Let V(D) denote the nodes of a triangle-DAG D computing Search BPHP m n under the natural partition of variables. At a high level, to prove Theorem 1.7, we will construct a partial function µ : X ∪ Y → V(D) such that (a) (Lemma 5.5) most x ∈ X and y ∈ Y are mapped by µ to a node of D, and (b) (Lemma 5.6) there is no node of D with too many x or y assigned to it by µ.
It will then be trivial to combine these two properties and conclude that |V(D)| must be large 9 .
For any i ̸ = j ∈ [m], there is an associated rectangle R i,j ⊆ X × Y of inputs that violate at least one of the n clauses enforcing an inequality between coordinates i and j given by
Observe that the set of all rectangles {R i,j : i ̸ = j ∈ [m]} covers the entire space X × Y as long as m > n. (That is, X × Y = i̸ =j∈[m] R i,j .) Note that in order for a triangle-DAG to correctly compute Search BPHP m n , it must, at the very least, have each sink be contained in a single R i,j . Definition 5.3. For a node u ∈ V(D), let T u denote the triangle associated with that node. Define the width w(T, z) of z in triangle T to be the minimal size of any subset S ⊆ {R i,j
With this definition in hand, we can define our µ : X ∪ Y → V(D) using Algorithm 1 which depends on a parameter k that we will eventually set to √ n/4. Intuitively, in using Algorithm 1 we are going backwards through our DAG D, and whenever the protocol had too many options for what clause to output when the protocol was at a node u for a fixed z ∈ X ∪ Y 9 The name bottleneck counting came from its original version due to Haken [13] in which a class of full input assignments was mapped by a function µ to nodes in a proof DAG and each input assignment could be viewed as 'flowing' from the root to a particular sink node (defined by the assignment). In that case, µ identified a node on such a path, a bottleneck node, that did not permit many assignments to flow through it. Since there were many assignments, only few of which could pass through any bottleneck node identified by µ, there must be many bottleneck nodes in the DAG. In the modified form for cutting planes/triangle-DAGs, while the full assignment is flowing through the triangle-DAG, the mapping µ is based on half of the input assignment, either the x or y portion, and the sink node is not unique; not all assignments are assigned in this way, but many are.
Input: triangle-DAG D on input set X × Y with node set V(D) Output: a partial map µ : X ∪ Y → V(D) 1 Let X ′ := X and Y ′ := Y be the remaining coordinates we have not yet assigned by µ 2 for u in some topological ordering of V(D), starting from the sinks do 3
12 return µ (which corresponds to large width), we assign z to u. Arguing that |µ -1 (u)| is not too large is thus arguing that a protocol cannot make huge strides in learning about which clause to output for too many z ∈ X ∪ Y suddenly in one single node u.
We now make some basic observations about our definition of µ. First, note that no z ∈ X ∪ Y is assigned to any sink node of D, since every sink node s ∈ V(D) is wholly contained in an R i,j , and therefore we have that w(T s , z) = 1 for all z. The following observation will be of critical importance in our analysis.
Proof of Claim. By definition in a triangle-DAG, if v and v ′ are children of node u, then we have that T u ⊆ T v ∪ T v ′ . In particular, we know that if z ∈ X ∪ Y was not assigned to nodes v or v ′ , then w( T u , z) ≤ 2k, since we can take the union of the coverings for T z v and T z v ′ . □
Finally, we note that at the end of Algorithm 1 at the root r, for all z ∈ X ′ ∪ Y ′ , we have that w( T r , z) < k.
Lemma 5.5. Let k ≤ √ n/2. For µ constructed using Algorithm 1, at least |X|/2 elements of X are assigned by µ or at least |Y|/2 elements of Y are assigned by µ.
Proof. At the end of Algorithm 1 after processing the root r of D, since T r = X × Y, we have T r = X ′ × Y ′ which is the rectangle of unassigned inputs. If |X ′ | ≤ |X|/2 then we are done; otherwise, let x ∈ X ′ . Since w( T r , x) < k, there exists a set S, |S| < k, such that for all y ∈ Y ′ , y i = y j for at least one (i, j) ∈ S.
So, we obtain
This shows that a large number of elements of X ∪ Y are assigned by µ. It remains to show that each node in the protocol D only has a bounded number of elements of X ∪ Y assigned by µ. Lemma 5.6. Let µ be defined by Algorithm 1 with k = √ n/4. For all all u ∈ V(D),
elements of X to u; the analogous bound also holds for Y.
in Algorithm 2 along with Proposition 5.1. We define the set of equality constraints of a leaf t ∈ T to be the set E(t) := {i ̸ = j ∈ [m] : (i, j) is on the unique path to t in T }. Observe that we have the desired property that if x is consistent with a leaf t of T , then T x u is covered by {R i,j : (i, j) ∈ E(t)}, thereby ensuring that w( T u , x) ≤ depth T (t).
Therefore, if µ maps x ∈ X ′ to u then x must be consistent with a leaf of T of depth at least k. Let T ′ denote tree T truncated at depth k. Thus, the total number of x ∈ X ′ that µ maps to u is at most
Remark 5.7. Before explaining the details of our analysis, it is useful to discuss a naive bound on (1) that does not suffice to yield our bounds: Naively, there could be (2k) k leaves in T ′ at depth k, and each such leaf t could have the property that E(t) forms a clique on ℓ = O( √ k) coordinates when viewed as a graph. In this case, the fraction of x ∈ X that could be consistent with the intersection
If we simply take a union bound over all (2k) k paths, the upper bound we would get on ( 1) is (2k
In light of Remark 5.7, we need to be more careful about how we bound (1). For t ∈ V(T ′ ), we define its equality graph G(t) to be a graph with vertex set [m] and edge set E(t). We use this name because if x is consistent with t, then x i = x j for all (i, j) ∈ E(t). We say that an edge (i, j) denoting x i = x j is implied by equality graph G(t) if adding it completes a cycle in G(t).
The key observation is the following.
Claim 5.8. Let t be a node in T ′ , and G(t) its associated equality graph. If t has out-degree strictly larger than 1 in T ′ , then none of the outgoing edges can be labelled by an (i, j) that is implied by G(t).
Proof of Claim. We prove the contrapositive. Consider any x consistent with the path to t in T ′ (meaning x i = x j for all (i, j) ∈ E(t)). Let T be the triangle labelling node t and consider the y that we choose when processing T in Algorithm 2. If there is some outgoing edge from t labelled (i, j) that is implied by G(t), then R i,j ∩ T y ̸ = ∅ and hence y i = y j . Since we know that x i = x j is already implied in T, the single rectangle R i,j covers all of T y , so t will have out-degree 1 in T . □ Claim 5.8 implies that every path in T ′ goes through a node that branches at least √ 2k times, since k edges must imply equality constraints on at least √ 2k coordinates (the worst case is a clique). We simplify T ′ further by collapsing nodes of T ′ with out-degree 1. Then we are left with T ′′ , which is a tree with every path of length between √ 2k and k. Since, the input distribution on X is uniform and none of the out-degree 1 edges of T ′ involve new constraints by Claim 5.8, the probability that x is consistent with any leaf t ∈ T ′′ is precisely (1/ √ n) depth T ′′ (t) . Then we can bound (1) as follows:
since T and hence T ′′ has out-degree at most 2k by construction
This implies that the number of x ∈ X that get assigned to u by µ is at most
as required. The analogous bound holds for the number of y assigned to u by µ.
We now have all we need to prove our main theorem. Remark 5.9. Hrubeš and Pudlák [17] proved their lower bound using the interpolation method combined with a modified form of a general monotone switching lemma of Jukna [20]. The construction of Algorithm 2 has some flavor of the monotone switching lemma arguments, but the overall argument here seems fairly different. It would not be surprising that if one could modify this method to yield a similar lower bound to the one we give here, but exactly how to do that is not clear. In any case, we find the form of the bottleneck counting argument appealing.
In this section, we prove:
Theorem 1.3. For all m > n and 2 ≤ k ≤ log n /4, the randomized number-in-hand communication complexity of Coll k m,n 1/k is Ω(n 1/2-1/(2k) /k).
Before proving Theorem 1.3, we show that it is essentially optimal by a showing a simple protocol nearly matches our lower bound. Proposition 6.1. For m ≥ n + n 1-1/k and k ≤ log n /4, there is a randomized k-party number-in-hand protocol for Coll k m,n 1/k with complexity O(n 1/2-1/(2k) log n).
Proof Sketch. Without loss of generality, m = n + n 1-1/k , since we can always ignore the remaining coordinates. By the pigeonhole principle there must exist a subset of at least ℓ = m/n 1/k coordinates on which Player 1's input is the same. The protocol is as follows. Player 1 first announces a random subset S of these coordinates of size t = 16n 1/2-1/(2k) . Players 2 through k -1 send vectors of length t giving their values on each element of S. Player k announces a collision among the pairs of elements of S, if there is one. Player 1's announcement requires O(n 1/2-1/(2k) log n) bits, while the remaining k -1 announcements require at most O(n 1/2-1/(2k) log(n 1/k )) bits each. The total bound on the communication is therefore O(n 1/2-1/(2k) log n), as desired. It suffices to now argue that player k will have a collision to announce with good probability. For any input x, it will be convenient to think of of a graph G x whose vertices are coordinates i ∈ [m], and where an edge (i, j) exists iff x i = x j . Observe that, for any input, G x is a collection of non-trivial cliques, where the sum of the number of vertices in the cliques is at least r = mn. This implies that there are at least r/2 vertex-disjoint edges in G x .
When viewed in this way, Player 1's announcement is equivalent to them outputting a random clique on t vertices (out of ℓ possible vertices). In order for the players to succeed, it is sufficient for this clique to contain one of the r/2 vertex-disjoint edges.
Consider sampling our random clique by first sampling t/2 random vertices of the t vertices that Player 1 samples. Of our r/2 vertex-disjoint edges, in expectation q = (r/2)(t/2)/ℓ = rt/(4ℓ) of them have a vertex we sampled in this first phase. By Hoeffding's bound on the tail of the hypergeometric distribution, with probability at least 1 -2 -q/2 we see at least q/4 vertices. If any have both endpoints already sampled, then we are done, so assume this is not the case.
We then sample the remaining t/2 disjoint vertices to include in Player 1's clique. In order to succeed, one of these t/2 additional vertices must complete one of our q/4 edges. The probability that this does not happen is at most (1 -t/2 ℓ ) q/4 ≤ e -tq/(8ℓ) = e -(t/ℓ) 2 •r/32 . Now, plugging in (t/ℓ) 2 = (16n 1/2+1/2k /m) 2 = 16 2 n 1+1/k /m 2 , we see that since m = n + n 1-1/k , we have r = n 1-1/k and hence, conditioned on finding sampling at least q/4 vertices for the first set, the probability of failure is at most e
There the total failure probability is at most 2 -q/2 + e -2 ≤ 1/4.
For the proof of Theorem 1.3 we simplify and generalize ideas of Yang, Zhang, and Wang [34,33] to the k > 2-party setting for Coll k m,n 1/k Suppose that we have a randomized protocol Π solving Coll k m,n 1/k . We follow [33] and decompose each rectangle in protocol tree further into "structured" subrectangles for which we need the following definition. Definition 6.2 (Pseudorandomness/density). For a random variable X supported on Ω J , we say it is (1δ)dense if for all I ⊆ J, H ∞ (X(I)) ≥ (1δ) |I| log |Ω|, where X(I) denotes the random variable marginalized to the coordinates in I.
For Coll k m,n 1/k we have supp(X i ) = Ω m for Ω = [n 1/k ] and we will choose δ = 1 log n . Definition 6.3 (Structured rectangle). Given a rectangle R = X 1 × . . . × X k , where each X i ⊆ Ω m , we say that R is structured iff there exist J 1 , . . . , J k ⊆ [m] and τ 1 , . . . , τ k where each τ
• X i is (1δ)-dense on the coordinates in J i and
The high level idea in [34,33] is to recursively partition each rectangle in the protocol into structured subrectangles so that, if the players have not communicated much, then the average number of fixed coordinates in a random leaf subrectangle is small.
Let us now detail this algorithm. It is similar to the algorithm in [34], but crucially different in that we do not keep track of error sets/subrectangles as we go. 10We shall need one important tool from [11], which decomposes an arbitrary random variable into structured subparts. Lemma 6.4 (Density-restoring partition from [11]). Given X on Ω J , we can partition it as X = i X i such that 1. X i has an associated I i and τ i so that for all x ∈ X i , x(
We now focus on errors in protocols Π specifically for Coll k m,n 1/k . Definition 6.8. Let R be a subrectangle in the support of R leaf . Call R bad if either
• there exists a pair s ̸ = t ∈ [m] such that s, t ∈ i J i and τ i (s) = τ i (t) for all i ∈ [k], or
Otherwise call R good.
Note that, since we are focussed on proving a lower bound, our definition labels subrectangles as bad if they correspond to confirmed successes of Π. Lemma 6.9.
Proof. First, we observe that the probability in question, Pr R∼R leaf [R is bad], is equivalent to the probability over a uniformly random input x that x ends up in a bad subrectangle, since our sampling is always proportional to the size of the subrectangles.
For simplicity we assume without loss of generality that Π is a full binary tree. Define R ℓ to be the support of subrectangles at the ℓ-th layer of the protocol tree in Algorithm 3, and let R ℓ (x) (which has corresponding J 1 , . . . , J k and τ 1 , . . . , τ k ) be the subrectangle containing x in R ℓ .
Define G ℓ ⊆ R ℓ to be the set of R ∈ R ℓ such that ∑ i |J i | 2 < 400 (k • CC(Π)) 2 ≤ 0.04n 1-1/k and let B ℓ (x) = 1{R ℓ (x) ̸ ∈ G ℓ or ∃ s ̸ = t ∈ [m] and j ∈ [k] s.t. τ j (s) = τ j (t) and x j ′ (s) = x j ′ (t) for all j ′ ̸ = j}.
We shall prove by induction on the layers of the sampling process given by Algorithm 3 that
The base case is clearly true, since at the root we have ∑ x B 0 (x) = 0. Assume that (2) is true up to level ℓ. For every R ̸ ∈ G ℓ , none of its subrectangles will be in G ℓ+1 since we only ever increase the size of |J i | in our sampling process.
For the R ∈ G ℓ , suppose that player i speaks on R at level ℓ. We give convenient names to some of the objects produced during the sampling process. Algorithm 3 first partitions R into R b for b ∈ {0, 1}, and then further partitions R b using the density restoring partition into R b 1 , . . . , R b r , where each R b t has corresponding I b t new fixed coordinates for player i. In this way, for every R ∈ R ℓ we have that |R| = ∑ b∈{0,1} ∑ r t=1 |R b t |, since these form a partition.
Its possible that some of these subrectangles are no longer in G ℓ+1 . We bound the size of these trivially. For those in G ℓ+1 , using Proposition 6.7 we can bound the probability that the fixed variables for player i up level ℓ + 1 include a collision on s ̸ = t ∈ [m] that extends to a collision for all players. Fixing the coordinates in I b t creates at most
2 ) fixed colliding pairs for player i that have not previously been fixed collisions for other players. By Proposition 6.7 and a union bound over these (s, t) pairs, the fraction of inputs in R b t that have collisions involving these pairs that have not previously been accounted for is at most
Thus, we have that 2 n 1-1/k |J i ∪ I b t | 2 -|J i | 2 |R b t | + ∑ t:R b t ̸ ∈G ℓ+1 |R b t | ≤ ∑ R∈G ℓ 2 n 1-1/k ∑ i∈[k] |J i (R)| 2 • ∑ b ∑ t |R b t | + 1.04 ∑ R̸ ∈G ℓ |R| + ∑ R∈G ℓ ∑ b∈{0,1} ∑ t:R b t ∈G ℓ+1 2 n 1-1/k |J i (R) ∪ I b t | 2 -|J i (R)| 2 |R b t | + ∑ t:R b t ̸ ∈G ℓ+1 |R b t | = ∑ R∈G ℓ ∑ b ∑ t:R b t ∈G ℓ+1 |R b t | 2 n 1-1/k ∑ i∈[k] |J i (R b t )| 2 + 1.04 ∑ R̸ ∈G ℓ ∑ b ∑ t |R b t | + ∑ R∈G ℓ ∑ b ∑ t:R b t ̸ ∈G ℓ+1 1 + 2 n 1-1/k ∑ i∈[k]
|R|, as desired. The first inequality used a union bound and Proposition 6.7, as described above, and the second inequality used the inductive hypothesis. The third line recollected terms, while the last inequality used the fact that 2
Finally, we let ℓ = CC(Π). By Corollary 6.6, we can bound 1.04 ∑ R̸ ∈G CC(Π) |R| ≤ 0.104 ∑ R∈R leaf |R| = 0.104n m . We can also bound
Combining, we get that the probability over uniformly random input of landing in a bad rectangle is at most 0.144 < 1/6.
Next, we have a simple lemma which says that the probability of producing a correct answer in any good leaf subrectangle is small. Lemma 6.10. Suppose that k ≤ log n /4. For any fixed s ̸ = t ∈ [m] and good subrectangle R, the probability Pr x∈R [x i (s) = x i (t) for all i ∈ [k]] ≤ 1/8. Proof. We use Proposition 6.7 with ℓ = 1. In a good rectangle, for any pair s, t ∈ [m], there must be some J i such that {s, t} ̸ ⊆ J i , in which case we can apply Proposition 6.7 with ℓ = 1 to say that the probability that x i (s) = x i (t) ≤ 2n -1/k ≤ 2n -4/ log n = 1/8.
We are now ready to prove Theorem 1.3.
Proof of Theorem 1.3. Suppose that the protocol Π communicated fewer than 0.01n 1/2-1/2k /k bits. Then the probability of correctly outputting a collision is at most the probability of ending up in a bad subrectangle, plus the probability of outputting a correct collision given the input falls in a good subrectangle. We can thus bound the success probability of the protocol using Lemma 6.9 and Lemma 6.10 as at most 1/6 + 1/8 < 1/3.
We end by discussing some related problems and directions for future study. In particular, we highlight three possible directions.
1. Multiparty DAG-like communication lower bounds. In general, it would be interesting to see if the 2 Ω(n 1/4 ) we give can be further improved, or if any nontrivial (size 2 o(n) ) cutting planes refutation
This encoding of the pigeonhole principle was introduced in[1].
When m is somewhat larger, we can obtain somewhat weaker lower bounds.
The direction of arrows in this digraph may seem counterintuitive, but it is convenient when thinking of the graph as a search problem for a violated axiom. In this case, we can follow a path in the graph to find such a a violated axiom on one of the leaves/sources.
Cutting planes proofs can simulate resolution proofs, see e.g.[20,27].
For example, x ∨ y ∨ z could be converted to the inequality x + y + z ≥ 1.
As noted in[20], there is no meaningful converse to this statement, since if there are m inequalities in our unsatisfiable system, there exists a trivial depth m threshold decision tree finding one that is violated.
This is important because if we bias and have a certain fake row appear more often in the input for player p, then A could potentially detect and use this to its advantage.
Ω(n 1-1/ √ log n n -1/ √ log n /(log
3/2 n)) = 2 cn 1-2/ √ log n-1.5 log log n/ log n ,for appropriate constant c. Using the fact that c = n log c/ log n , the bound becomes2 n 1-2/ √ log n-o(1/ √ log n).
Keeping track of the errors as we go seems to lead to cylinder intersections when k > 2 and more complicated analyses when k = 2. For that reason, our decomposition algorithm and analysis is more similar in spirit to what can be found in[33].