PaperlayerView exact revision on arXiv

Source-linked AI summary

Lossless Hardness Condensation in Deterministic Communication Complexity

Simon Mackenzie

arXiv:2609.28691v1cs.CC

TL;DR

Hard deterministic communication problems may involve far more inputs than their cost suggests, raising whether hardness survives on a much smaller restriction. The paper counts and covers submatrices equipped with short protocols, then proves that every finite total Boolean matrix of complexity c≥4 contains a near-maximally hard square of original inputs.

  • Problem

    The paper asks whether every hard deterministic communication matrix contains a much smaller restriction that remains hard.

    Source: §1 · p. 2

  • Method

    The proof counts submatrices carrying short protocols and covers inputs with protocol domains that a player can name before the protocol runs.

    Source: §1.1 · p. 3

  • Results

    For every fixed 0<ε<1, a matrix of complexity c≥4 has a 2^k-by-2^k original-input restriction with k linear in c and complexity at least (1−ε)(k+1).

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    The theorem establishes linear input-length condensation with hardness arbitrarily close to the maximum possible on the retained square, without a rank or distributional assumption.

    Source: §1.1 · p. 3

    The constructive algorithm does not provide a small independently checkable certificate for the returned restriction’s complexity lower bound.

    Source: §6.3 · p. 22

Abstract

from arXiv · show

A communication problem can have far more possible inputs than its communication cost would suggest. Must its difficulty already be present on a much smaller set of inputs? We prove that every finite total Boolean matrix of deterministic communication complexity $c\ge4$ has a submatrix on $2^k$ of its original rows and $2^k$ of its original columns, with $k=\Theta_\varepsilon(c)$ and complexity at least $(1-\varepsilon)(k+1)$, for every fixed $0<\varepsilon<1$. Since $k+1$ is the maximum possible cost on such a square, the retained problem can be arbitrarily close to maximally hard. This answers affirmatively the lossless condensation question of Hamed Hatami; G\"o\"os, Newman, Riazanov, and Sokolov (STOC 2024), who recorded it as Open Problem 2, conjectured a negative answer. Hrube\v{s} previously guaranteed input length $\Omega(\sqrt c)$. The same argument gives an original $2^{c-2}$-by-$2^{c-2}$ square retaining at least $c/3-O(\log c)$ bits of communication complexity. The proof builds on Hrube\v{s}'s counting and covering argument. We count submatrices equipped with short communication protocols: a player names a covering submatrix, then the players run its protocol. This avoids the loss from converting rectangle partitions into protocols. A recursion on rectangles makes the argument constructive. For fixed rational $\varepsilon$ and any target depth $d\ge4$, a deterministic algorithm returns either a protocol of depth below $d$, or a square of original inputs at input length $\Theta_\varepsilon(d)$ with the same near-maximal guarantee. Its running time is $2^{O(2^d)}$ times a polynomial in the table size. If the original complexity is at least $d$, the algorithm necessarily returns the square. An extension gives constant-factor condensation for any fixed number of number-in-hand players, with bounds independent of the finite output alphabet.

1 Introduction

The paper asks whether hard deterministic communication problems contain much smaller restrictions that remain hard, and answers yes with near-maximal hardness on a square of original inputs. It develops a rank-sensitive counting and covering proof, makes it constructive, and places the result against earlier condensation bounds.

1.3 Related work

  • The result answers the lossless-condensation question recorded by Göös, Newman, Riazanov, and Sokolov, who conjectured a negative answer; Hrubeš had obtained only an Ω(√c) input-length guarantee.Their positive result for lifted query functions has different scope, while this paper permits arbitrary row and column restrictions.Source: §1 · p. 2, §1.3 · pp. 6–7

1.1 Results

  • For every fixed ε, a total Boolean matrix of complexity c≥4 contains a 2^k-by-2^k restriction of original inputs with k linear in c and D(N)≥(1−ε)(k+1).The retained complexity can approach the maximum k+1 for a square of this size.Source: §1.1 · p. 3
  • At input length c−2 per player, an original 2^(c−2)-by-2^(c−2) restriction retains at least c/3−O(log c) bits of communication complexity.This guarantee measures retained hardness against the original cost rather than approaching the maximum on the smaller square.Source: §1.1 · p. 3

1.2 Proof ideas

  • The proof counts submatrices equipped with short protocols and covers inputs by protocol domains, so naming a domain and running its protocol gives a global protocol.This extends Hrubeš’s counting-and-covering approach to whole protocol domains and yields a linear input-length scale.Source: §1.1 · p. 3, §1.2 · p. 5, §1.3 · p. 6

1.1 Results

  • For rational 0 < ε < 1, given a finite total Boolean matrix M of table size T and integer d ≥ 4, a deterministic algorithm returns either a protocol for M of depth less than d or an original 2k-by-2k submatrix N, in time 2^O(2^d)T^O(1).If D(M) ≥ d, the protocol outcome is impossible, so the algorithm returns the square; obtaining the square does not certify that D(M) ≥ d.Source: §1.1 · pp. 3–4

1.2 Proof ideas

  • Rank either supplies a nonsingular minor with maximal complexity or makes the domain-index overhead cheap enough for a cover to yield a hard square.The proof counts leaf conditions using rank-sensitive row-sum encoding, then combines them along the protocol tree.Source: §1.2 · pp. 5–6

1.3 Related work

  • Earlier partition-based bounds pass through the 1-partition number and yield a square-root scale, whereas counting protocol-bearing domains directly gives a linear scale.The paper also distinguishes its construction from biclique partitions: it seeks protocol-bearing domains containing every cheap restriction.Source: §1.3 · pp. 6–7
  • The paper’s deterministic result does not extend to public-coin randomized complexity, where cited examples rule out condensation even with polynomial loss.Negative query results concern coordinate restrictions, unlike the arbitrary row and column choices allowed here.Source: §1.3 · pp. 6–7

2 Preliminaries

The preliminaries define the deterministic protocol model and the restrictions used throughout the paper. They also establish that deleting duplicate row or column values preserves complexity, provided selected inputs remain original labels.

2 Preliminaries

  • A deterministic protocol is a binary tree whose internal nodes specify a speaker and input-dependent bit, and whose leaves have fixed Boolean outputs.Its depth is the maximum number of transmitted bits; either player may start, and consecutive bits need not alternate.Source: §2 · p. 7
  • A restriction keeps selected original row and column labels, and restricting a correct protocol cannot increase communication complexity.Conversely, enlarging an already hard submatrix with additional original inputs cannot make it easier.Source: §2 · p. 8

2.1 Repeated input values

  • Deleting duplicate row or column values preserves communication complexity and rank, because a protocol can map each label to one representative locally.Representatives are actual original labels, and later enlargements use distinct unused original labels.Source: §2.1 · p. 8

3 Protocol domains

The section defines protocol domains as the column sets compatible with partial protocols, so a cover by domains yields a global protocol after a player names one. Their recursive structure is an intersection/union tree whose leaf conditions require one answer across all associated rows.

3 Protocol domains

  • A cover of Bob’s inputs by protocol domains gives a global protocol: Bob names a domain containing his column, then the players run its protocol.The domain count concerns full sets accepted by fixed Alice instructions, not every cheap subset of columns.Source: §3 · p. 8

3.1 Compatible columns

  • A column is compatible when one assignment to Bob’s protocol nodes makes the protocol correct for every retained row; this is equivalent to a depth-s protocol on the full domain.The assignment may depend on Bob’s column, but not on Alice’s row.Source: §3.1 · pp. 8–9

3.2 The conditions at a leaf

  • Protocol domains form depth-s intersection/union trees: Alice nodes intersect child sets, Bob nodes unite them, and each leaf requires its answer on every associated row.Rows split only at Alice nodes; Bob’s choice must work for the whole row set.Source: §3.2 · pp. 9–10, Figure 4 · p. 10

4 Rank-sensitive counting

The section uses matrix rank to bound both the number of row requirements needed at a leaf and the number of protocol domains. This rank-sensitive counting is the basis for controlling how many inputs short protocols can cover.

4.1 Rank and input values

  • For rank r, there are at most 2^r distinct row values and 2^r distinct column values, and deterministic complexity is at most r + 1.The section also relates depth s to rank at most 2s−1 and establishes nonsingular original-index squares.Source: §4.1 · pp. 10–11

4 Rank-sensitive counting

  • A rank-r matrix needs at most r distinct row-value requirements to describe any same-answer leaf condition.An inclusion-minimal list has a witness column for each requirement; the resulting witness submatrix has rank equal to the list length.Source: §4 · p. 10, §4.2 · p. 12

4.2 Short lists of row requirements

  • Minimal same-answer requirements are rank-bounded because their witness columns produce an identity matrix for answer zero or J_q − I_q for answer one.Both witness matrices have rank q, so the number q of necessary requirements cannot exceed rank r.Source: §4.2 · p. 12

4.3 The domain count

  • A depth-s protocol domain is an intersection/union tree with 2^s leaves, and rank-sensitive leaf descriptions bound the number of such domains by 2^(B(r)2^s−1).Each leaf description records at most r sum entries, a row count, and an output bit; the count is independent of the original input-set sizes.Source: §4.3 · p. 13

5 Lossless condensation

The proof converts local protocols into covers of the input domain, then restricts columns and rows while tracking the depth lost. A rank dichotomy yields squares that are either maximally hard minors or nearly maximally hard restrictions.

5.1 Hitting sets and protocol covers

  • A hitting set meeting every protocol-domain complement of mass at least 1/2 forces a short-protocol domain to cover more than half of the remaining columns.Repeated strict halvings cover all representatives; Bob names one of at most r domains and the players run its protocol.Source: §5.1 · pp. 14–15

5.2 Both input sets

  • Applying the cover argument first to columns and then to rows produces an original submatrix with depth above s and side sizes at most a(r,s) and a(r,s+H).The first restriction must retain an extra H bits to pay for the second application.Source: §5.2 · pp. 15–16

5.3 A rank-sensitive square

  • A rank-sensitive square of side 2^(c−2) has depth at least c−2h−ℓ−1, where h=⌈log(r+1)⌉ and ℓ=⌈log(c+1)⌉.The argument combines a square obtained from the rank-sensitive bound with a padded nonsingular minor when rank is large.Source: §5.3 · pp. 16–17
  • For every fixed 0<ε<1, a complexity-c matrix contains an original 2^k-by-2^k square with k=Θε(c) and depth at least (1−ε)(k+1).The proof uses a maximally hard nonsingular minor at high rank and a controlled-loss square at low rank.Source: §5.3 · p. 17

6 Constructive condensation

The constructive proof enumerates protocol domains together with the protocols they carry, then uses their coverage properties to find either an easy global protocol or hard original inputs. A rank-sensitive extraction step yields the near-maximal square guarantee.

6.1 Leaf domains

  • For rank at most r, all same-answer leaf domains can be listed in time 2^O(r log(r+1))T^O(1), with at most 2(r+1)^(r+1) output-labelled pairs.The list is generated by iterated intersections of row-compatible column sets.Source: §6.1 · p. 18

6.2 Protocols on rectangles

  • At an Alice node, child row sets combine by union and column sets by intersection; at a Bob node, those operations reverse, yielding a correct protocol on the resulting rectangle.The constructed sets and message functions can be computed in 2^O(s)T^O(1) time.Source: Figure 8 · p. 19, §6.2 · pp. 19–20
  • A deterministic list of protocol domains, each carrying a depth-at-most-s protocol, contains a domain covering every nonempty column set with a depth-at-most-s protocol.The list has at most 2a(r,s)−1 distinct members.Source: §6.2 · pp. 20–21

6.3 Protocol covers and hard column sets

  • The constructive one-sided alternative returns either a global protocol of depth at most s+⌈log r⌉ or a nonempty original column set of size at most a(r,s) with depth greater than s.The cover phase and protocol-elimination phase halve different objects to produce the alternative.Source: §6.3 · p. 21
  • The two-sided alternative returns either a global protocol of depth at most s+2⌈log r⌉ or original row and column sets yielding depth greater than s.The row set is found by applying the procedure to the transpose of the first, hard column restriction.Source: §6.3 · p. 22

6.4 Near-maximal extraction

  • For fixed ε and target depth d≥4, extraction returns a protocol below d or an original square of side 2^(d−2) with depth greater than (1−ε)(d−1).The constructive near-maximal extraction runs in 2^O(2^d)T^O(1) time.Source: §6.4 · p. 23

7 Further questions

The paper leaves open whether every hard Boolean matrix has a square at a linear input-length scale that is exactly maximally hard. It also asks whether near-maximal condensation can be found faster and whether the multiparty result can retain a larger fraction of the communication complexity.

7 Further questions

  • Whether every hard Boolean matrix has a 2^k-by-2^k restriction of complexity exactly k+1 at linear input-length scale remains open.A nonsingular minor already gives this when the logarithm of rank is linear in the original complexity.Source: §7 · p. 23
  • The paper asks whether near-maximal condensation can be found substantially faster, perhaps in time polynomial in the original table size.The question concerns finding hard original inputs, not computing the exact value of D(M).Source: §7 · p. 23
  • For the multiparty extension, the open question is whether a larger fraction of communication complexity can be retained.Source: §7 · p. 23

A Further two-party bounds

This appendix section records additional two-party bounds, including a local-to-global form, a faster constructive tradeoff, and an exhaustive-search comparison. The paper says these results are not needed for its main proofs.

A Further two-party bounds

A.1 A local-to-global theorem

The local-to-global theorem bounds the complexity of the whole matrix when all sufficiently small restrictions have bounded depth. Equivalently, a matrix exceeding that global bound contains a small restriction of greater depth.

A.1 A local-to-global theorem

  • If every nonempty restriction with at most 24s rows and columns has depth at most s, then D(M) ≤ 3s − 2.Equivalently, if D(M) > 3s − 2, some submatrix within those size bounds has depth at least s + 1.Source: §A.1 · p. 24
  • A rank bound follows because any nonsingular minor of order 2s has depth greater than s, contradicting the local hypothesis.The proof therefore bounds rank(M) by 2s − 1 before applying the protocol-cover argument.Source: §A.1 · p. 24
  • The size hypothesis applies to existing restrictions with at most the stated dimensions, even when the matrix itself is smaller.There is no requirement for a square larger than the matrix.Source: §A.1 · p. 24

A.2 An alternative constructive tradeoff

An alternative parameter choice in the constructive local-to-global algorithm trades retained hardness for faster extraction. It yields a square near the supplied input-length bound, with a constant-fraction hardness guarantee.

A.2 An alternative constructive tradeoff

  • The alternative extraction tradeoff retains one-quarter hardness and runs in time 2^O(d·2^(3d/4)) times a polynomial in the table size.The running-time bound is stated for the almost-full-input-length corollary.Source: §A.2 · pp. 24–25
  • For each integer t ≥ 1, the algorithm returns either a protocol of depth at most 3t − 2 or an original restriction of at most 24t rows and columns with depth greater than t.Its running time is 2^O(t·8^t) times a polynomial in the table size; the two outcomes need not be disjoint.Source: §A.2 · p. 24
  • When rank exceeds 2t − 1, exact elimination extracts a nonsingular minor of depth greater than t using original row and column indices.Otherwise, the rank-based covering argument supplies the protocol or restriction outcome; rank computation and original-index bookkeeping have polynomial table cost.Source: §A.2 · pp. 24–25
  • For d ≥ 6 and D(M) ≥ d, a deterministic algorithm returns an original square of side 2k, where k = 4⌊(d − 2)/4⌋.The retained square has depth at least t + 1 for t = ⌊(d − 2)/4⌋, and its input length is within five bits of d.Source: §A.2 · p. 25

A.3 Exhaustive search

The section compares exhaustive square search with rank preprocessing and the constructive algorithm. The search relies on a supplied hardness promise, while the constructive algorithm can also return a short protocol.

A.3 Exhaustive search

  • A supplied lower bound d ≤ D(M) yields an existence argument for a restriction of depth d, but finding the minimal row set is not efficient.After adding one row to an inclusion-minimal set, Alice can indicate whether she holds that row and Bob can send the answer.Source: §A.3 · p. 25
  • Direct search enumerates original power-of-two squares and computes each candidate’s depth by dynamic programming over row and column subsets.For candidates with at most L rows and columns, the tests take 2^O(L) time each; the full search takes 2^O(2d)T^O(2d).Source: §A.3 · p. 25
  • Rank preprocessing removes the parameter-dependent exponent of T, while a nonsingular minor immediately gives depth k + 1 when j ≥ q.The preprocessing and minor extraction have polynomial bit cost in T.Source: §A.3 · p. 26
  • The exhaustive-search comparison assumes D(M) ≥ d, whereas Theorem 1.3 runs without that promise and may instead return a protocol of depth below d.The rank-preprocessed search uses the existence theorem and does not provide an independent proof of condensation.Source: §A.3 · p. 26

B Several players and finite output alphabets

For a fixed number of players, the extension retains linear communication complexity on restrictions of the original inputs, with bounds independent of the finite output alphabet. Output indicators and successive covering arguments support the extension.

B Several players and finite output alphabets

  • If every product restriction has complexity at most s, the multiparty local-to-global principle gives D_p(F) ≤ (p + 1)s.This is the local-to-global statement used to prove the multiparty condensation result.Source: B Several players and finite output… · p. 27
  • For fixed p and c ≥ p + 2, Theorem B.1 retains Ω_p(c) communication complexity on restricted original inputs requiring O_p(c) bits to index, independently of the finite output alphabet.The theorem sets s = ⌊(c − 1)/(p + 1)⌋.Source: B Several players and finite output… · p. 27

B.1 Output indicators

  • The one-hot flattening H_i records whether the function outputs z for each tuple of other inputs and player i’s input; it is used only in the analysis.Inputs with identical columns give the same output for every choice of the other inputs, so one representative can stand for each such column.Source: §B.1 · p. 27

B.2 Compatible input sets

  • A compatible input set consists of player i’s inputs for which one assignment to that player’s open protocol nodes works for every retained tuple of the other inputs.At a leaf labelled z, the condition tests whether the required output equals z; the count includes all output labels.Source: §B.2 · p. 28
  • If every restriction of player i’s inputs up to the stated cap has a depth-s protocol, at most r compatible sets cover its representatives.Player i names the first covering set containing its input using ⌈log r⌉ bits, then the players run that set’s protocol.Source: §B.2 · pp. 28–29
  • Extending players’ input sets in order adds earlier announcement costs to later depth thresholds, with each announcement made by the owner of the input being extended.The proof allows the protocol to vary with the still-restricted input sets.Source: §B.2 · p. 29

B.3 Rank witnesses

The multiparty rank-witness argument turns shallow communication on small product restrictions into rank bounds, then uses those bounds to derive a global depth bound. Its contrapositive yields a small restriction retaining a guaranteed amount of communication complexity.

B.3 Rank witnesses

  • If every product restriction with at most 2s+1 inputs per player has depth at most s, then each one-hot flattening Hi has rank at most 2s.Each protocol leaf contributes a rank-one indicator, and a larger-rank minor would persist on a product restriction of at most 2s+1 inputs per player.Source: §B.3 · pp. 29–30
  • The flattening-rank bounds and extension lemma imply Dp(F) ≤ (p+1)s under the same local-depth hypothesis.The proof applies the extension lemma with ri = 2s and λi = s.Source: §B.3 · pp. 29–30
  • A product restriction with at most 2(p+2)s+1 inputs per player has complexity at least s+1 = ⌈c/(p+1)⌉ when the original complexity is c.The local hypothesis must fail because (p+1)s ≤ c−1 < Dp(F).Source: §B.3 · p. 30
  • For Boolean outputs, flattenings have rank at most 2s−1, yielding the alternative global depth bound s + p(s−1).This uses ordinary Boolean flattenings and announcement cost λ = s−1.Source: §B.3 · p. 30
  • The multiparty extension is existential for a fixed number of number-in-hand players, while the constructive algorithm in the main text is for two parties.The extension restricts each player’s input set while retaining all players; its constants depend on the player count.Source: §B.3 · p. 30

AI methodologies

The paper reports AI assistance in developing mathematical results and revising exposition. The author takes responsibility for the claims, proofs, citations, and presentation.

AI methodologies

  • Astra assisted with developing and revising mathematical results and proofs in Sections 3–6 and Appendices A and B, and with drafting and revising exposition throughout the paper.Its assistance included the counting arguments, two-party condensation theorems, extraction algorithm and analysis, and finite-output multiparty extension.Source: AI methodologies · p. 31
  • Claude models reviewed proof drafts and exposition and suggested editorial revisions.Source: AI methodologies · p. 31
  • The author takes responsibility for the claims, proofs, citations, and presentation.Source: AI methodologies · p. 31
Loading 2609.28691v1…