CS Paper Radar

Lossless Hardness Condensation in Deterministic Communication Complexity

Simon Mackenzie

cs.CC ·submitted 2026-09-23 18:30 UTC · v1
theory

Abstract

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=Θ_\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öös, Newman, Riazanov, and Sokolov (STOC 2024), who recorded it as Open Problem 2, conjectured a negative answer. Hrubeš previously guaranteed input length $Ω(\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š'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 $Θ_\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.

Comment
33 pages, 8 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Combinatorial Boolean Matrix Multiplication in $n^3 / 2^{Ω(\sqrt{\log n})}$ Time

cs.DS ·2026-11-04 ·Piaoyang Cui, Yiming Liu, David P. Woodruff
similarity 0.65
Abstract

For over fifty years, combinatorial algorithms for Boolean matrix multiplication (BMM) and triangle detection saved only polylogarithmic factors over cubic time. At STOC 2024, Abboud, Fischer, Kelley, Lovett, and Meka broke this barrier with a deterministic $O(n^3 / 2^{Ω((\log n)^{1/7})})$-time algorithm, and asked whether $n^3 / 2^{Ω(\sqrt{\log n})}$ time is achievable. We answer this question in the affirmative, giving deterministic combinatorial algorithms for both BMM and triangle detection running in $O(n^3 / 2^{Ω(\sqrt{\log n})})$ time. Following Abboud et al., we decompose $(A,B)$ into pairs of submatrices $(A_k,B_k)$, called \emph{pieces}, each of which is either sparse or pseudorandom in a sense that forces $A_k\star B_k$ to be nearly all-ones on its vertex sets. Whereas their decomposition produces $2^{O(d^7)}$ pieces at regularity parameter $d$, we obtain $2^{O(d^2)}$ pieces, directly improving the runtime exponent from $(\log n)^{1/7}$ to $\sqrt{\log n}$. Prior work found pseudorandom pieces by repeatedly restricting to denser submatrices, paying worst-case vertex losses at each step that compounded across nested recursion levels, together with an expensive derandomization step. We eliminate the extra powers of $d$ by matching the vertex loss at each step to the size of its density jump so losses telescope across scales, derandomizing witness search via $L_d$-norm estimation so the sampler length stays $2^{O(d)}$, and bounding overlap across the recursion with a fractional density-weighted volume budget rather than raw submatrix volume.

0.20

Quadratic bounds for uncompletable words and matrix mortality

cs.FL math.CO ·2026-09-25 ·Rahul Chandelkar, Samrath Singh Chadha
similarity 0.63
Abstract · Lean formalization and implementation pilot included as ancillary material

Every finite nonempty incomplete uniquely decipherable code with maximum word length $k$ has an uncompletable word of length at most $4k^2-3k$. The bound is independent of the number of codewords and their total length. Deleting a complete codeword cycle gives a finite path-counting identity; Kraft equality then supplies a short word of deficient compressed mass. Cyclic averaging and padding turn it into an uncompletable word. Conditional expectation makes the construction polynomial-time and also decides completeness. First-return words extend the bound to mortal families of nonnegative integer $n\times n$ matrices with joint spectral radius at most one, provided every strongly connected component has a vertex meeting every cycle. Such a family has a zero product of length at most $4n^2-3n$. A binary partial deterministic family with $2k-1$ states has shortest zero product of length $k^2+k-1$, establishing the optimal quadratic order. The bounds and the explicit-code algorithm, including its polynomial work bound, are proved in Lean.

0.32

Beyond the Bethe Approximation of the Permanent

cs.DS math.CO ·2026-08-28 ·Nima Anari
theorycode/data similarity 0.61
Abstract · 34 pages. Accompanying Lean 4 formalization: https://github.com/nimaanari/formalization-beyond-bethe. Palomar Registry entry: https://paloma…

The canonical Bethe approximation gives a deterministic approximation to the permanent of every nonnegative matrix within a factor of $(\sqrt{2})^n$. We improve the base of this exponential factor: for some absolute constant $c<\sqrt{2}$, there is a deterministic polynomial-time $c^n$-approximation for the permanent of every nonnegative matrix. This shows that the canonical Bethe guarantee is not a barrier for deterministic approximation of the permanent. The proof augments the Bethe lower bound with a new certificate tailored to matrices on which that lower bound loses nearly the full factor. The author supplied the high-level plan of attack, and the proof was developed in an interaction with ChatGPT 5.6 Sol Pro. The author subsequently verified the results. Codex assisted with proof checking, manuscript assembly, and typesetting.

0.67

An Exposition of the $\widetilde{O}(\log^{1/4} n)$ Bound for the Komlós Problem

cs.DM math.COcs.DSmath.PR ·2026-08-28 ·Nikhil Bansal, Haotian Jiang
publishedtheory similarity 0.61
Abstract · An extended abstract of this work appeared in STOC 2026: https://arxiv.org/pdf/2508.03961. The present article treats only the Komlós proble…

A conjecture of Komlós states that the combinatorial discrepancy of any matrix $A\in\mathbb R^{m\times n}$ whose columns have Euclidean norm at most one is bounded by a universal constant. We prove that the combinatorial discrepancy of every such matrix is at most $O((\log n)^{1/4}(\log\log n)^{7/4})$. This is the first asymptotic improvement over the $O(\sqrt{\log n})$ bound established by Banaszczyk [Banaszczyk, Random Struct.\ Algorithms, 1998], and it refutes a conjecture of Hajela [Hajela, European J.\ Combin., 1988] that a lower bound of order $Ω(\sqrt{\log n})$ should hold.

0.38

Information Complexity of Inner Product and Matrix Multiplication via Shannon-to-Min-Entropy Conversion

cs.IT cs.CC ·2026-11-02 ·Xiaohong Cai, Mingyang Zhu
theoryhot direction similarity 0.61
Abstract · 38 pages, including appendices

We determine the information complexity of matrix multiplication over finite fields under independent uniform inputs, up to a universal additive constant. The binary inner-product case resolves the open question of Braverman, Garg, Pankratov, and Weinstein on the optimal dependence of information complexity on the error probability. For inputs in $\mathbb F_2^m$ and error at most $\varepsilon\in[0,1/2]$, the information complexity with output at Bob lies between $(1-2\varepsilon)m-c_0$ and $(1-2\varepsilon)m$, where $c_0<4.772$ is a universal constant. For independent uniform matrices $X\in\mathbb F_q^{t\times m}$ and $Y\in\mathbb F_q^{s\times m}$, where $t\le s$, computing $XY^{\mathsf T}$ with output at Bob and error at most $\varepsilon\in[0,1]$ has information complexity $(1-q^{ts}\varepsilon/(q^{ts}-1))^+mt\log_2q$, up to an additive gap of less than $9.544$ bits. This gap is independent of the matrix dimensions, field size, and error. At zero error, the information complexity is exactly $mt\log_2q$. The information lower bounds for both inner product and matrix multiplication follow from a new Shannon-to-min-entropy theorem for convolution on discrete groups. Let $Q_1,\ldots,Q_k$ be the finitely supported distributions of independent random variables taking values in a discrete group, and let $s$ be the largest support size. We show that if $k\ge\lceil\lfloor\log_2s\rfloor\ln2\rceil$, then the min-entropy of their ordered product is at least the average Shannon entropy of the $Q_i$ minus $c_0$ bits. This holds for arbitrary discrete groups, including infinite and noncommutative groups, even when the input distributions differ. The leading coefficient of the logarithmic threshold is optimal.

0.38

Quantum Černý complexity of binary words

cs.DM quant-ph ·2026-09-30 ·Pui Hang Lee, Pui-Yee Lee, Bjørn Kjos-Hanssen
theory similarity 0.61
Abstract

We introduce the quantum Černý complexity $\mathrm{qc}(w)$ of a binary word $w$: the least dimension $d$ for which there exist quantum channels $A_0,A_1$ on $d\times d$ density matrices and a start state $ρ_0$ such that $w$ is the unique shortest word whose associated channel is constant on the reachable set. We show that $2\le\mathrm{qc}(w)\le\lceil\sqrt{|w|+1}\,\rceil$ for every nonempty $w$, a quadratic saving over the classical analogue, and that constant words are extremal: $\mathrm{qc}(0^m)=\lceil\sqrt{m+1}\,\rceil$. In contrast, $\mathrm{qc}(01^n0)=2$ for every $n\ge 1$, realized by a single qubit whose rotation angle acts as a counter; consequently there is no quantum analogue of the Černý function, and $\mathrm{qc}$ is strongly anti-correlated with intuitive notions of descriptive complexity. We further study the variant $\mathrm{qcp}$ in which the synchronization target is required to be a pure state. We prove that in dimension $2$ no word of length at least $2$ can be a unique shortest synchronizing word with pure target, and we exhibit an explicit qutrit instance, combining a coherent rotation with a measure-and-funnel channel, achieving $\mathrm{qcp}(01^n0)=3$ with target a computational basis state and with synchronization holding universally over all input states. Thus purity of the reset state costs exactly one dimension on this family. We also observe that $\mathrm{qc}$ is computable, by reduction to the first-order theory of the reals.

0.28

UPP$^{\text{cc}}$ is Not Closed Under Intersection

cs.CC ·2026-10-27 ·Mark Bun, Mandar Juvekar
theory similarity 0.60
Abstract

The sign rank of a ${\pm 1}$-valued matrix $A$ is the minimum rank of a real matrix that agrees with $A$ entrywise in sign. For every sufficiently large $d$, we give an explicit matrix $A$ with $2^{Θ(d^2)}$ rows and columns and sign rank $Θ(d)$ such that $A \land A$ has sign rank $2^{Θ(d)}$. Here, $A \land A$ is the communication matrix of the problem obtained by evaluating $A$ on disjoint inputs and taking the conjunction of the results. As the logarithm of sign rank characterizes unbounded-error communication complexity, this implies that the communication class $\mathsf{UPP}^{\mathsf{cc}}$ is not closed under intersection. The starting point for our lower bound is Forster's method, which relates the sign rank of a matrix to the average margin of representations of its rows and columns by points and halfspaces. We study a continuous analog for conjunctions of inner-product sign tests on the unit sphere. Rotational symmetry connects this problem to polynomial sign representations, yielding an exponentially small upper bound on the average margin. This bound holds even when sign constraints are relaxed near the sign tests' decision boundary, allowing us to transfer it to explicit finite sign matrices arising from intersections of integer halfspaces.

0.22

Optimal-Size Strong Connectivity Preservers under Two Edge Failures in Subcubic Time

cs.DS ·2026-11-12 ·Wanhee Lee, Chenglin Fan
theory similarity 0.59
Abstract · 43 pages

A $k$-edge-failure strong connectivity preserver of a directed graph on $N$ vertices is a spanning subgraph that has the same strongly connected components as the input after each set of at most $k$ edge deletions. The lower-bound construction of Baswana, Choudhary, and Roditty [BCR18], adapted to strong connectivity in [CC20], gives the previous best bound of $Ω(2^kN)$ necessary edges. Hoppenworth, Saranurak, and Wang [HSW25] prove an $O(k4^kN\log N)$ upper bound, leaving a logarithmic gap for fixed $k$. We close this gap by giving an explicit strongly connected graph on $N=2^d$ vertices with $N-1+(N/2)\log_2N$ edges, every one of which is necessary in a two-failure preserver. Together with the upper bound of [HSW25], this proves that the optimal size in the worst case is $Θ_k(N\log N)$ for every fixed $k\geq2$, whereas it is $Θ(N)$ for $k=1$ [GIP20]. The same graph has a one-failure preserver with at most $3(N-1)$ edges. We also give a randomized algorithm that either returns a spanning subgraph or reports failure. For every fixed $c,\varepsilon>0$, with probability at least $1-N^{-c}$ it returns a correct preserver for $k=2$ with $O(N\log N)$ edges, in $\widetilde O(N^{(ω+3)/2+\varepsilon})$ time and $\widetilde O(N^2)$ space. Here $ω$ is the matrix multiplication exponent over a fixed finite field.

0.18