Source-linked AI summary
Testing the Binary Rank with Polynomial Query Complexity
Michal Parnas
TL;DR
The paper answers whether binary rank can be tested with query complexity polynomial in d and 1/ϵ. It uses an adaptive tester built around a full-real-rank core, and also provides a route to approximate binary decompositions.
Problem
The paper addresses the open question of whether binary rank can be tested with query complexity polynomial in d and 1/ϵ.
Source: §1 · p. 3Method
Results
The authors answer affirmatively: binary rank admits polynomial query complexity in d and 1/ϵ, with acceptance on rank-at-most-d matrices and rejection when ε-far.
Source: §1 · p. 3, Overview of our Algorithms · p. 4Takeaways & Limitations
Under rankbin(M) ≤ d, the algorithm also finds a binary decomposition differing from M on at most an O(ϵ) fraction of entries with probability at least 5/6.
Source: §1 · p. 3Polynomial query complexity does not imply improved running time: the decomposition algorithm's running time remains 2^O(d^2)(n + m) poly(d, 1/ϵ).
Source: §1 · p. 3
Abstract
from arXiv · showhide
We design an adaptive two-sided error testing algorithm for the binary rank of a $0,1$ matrix $M$ with query complexity $O(d^3\log(d+1)/\epsilon^2)$, where $d$ is the tested binary rank bound and $\epsilon$ is the distance parameter. This answers an open question posed by Parnas, Ron and Shraibman~\cite{parnas2021property}, who asked if the binary rank can be tested with query complexity polynomial in $d$ and $1/\epsilon$. Furthermore, our testing algorithm can be used to find an approximate binary decomposition of $M$ with an additional $d(n+m)$ queries. That is, under the promise that the binary rank of $M$ is at most $d$, we show how to find, with probability at least $5/6$, two $0,1$ matrices $A',B'$ such that $M' = A' \cdot B'$ is a $0,1$ matrix which differs from $M$ on at most an $O(\epsilon)$ fraction of its entries. Our results also imply a testing algorithm with polynomial query complexity for the equivalent problem of testing if the edges of a bipartite graph can be partitioned into at most $d$ bicliques.
1 Introduction
The paper answers whether binary rank can be tested with query complexity polynomial in the rank bound and inverse distance, and outlines a tester based on a small real-rank core. It also gives an approximate binary decomposition and connects the testing problem to biclique partitioning.
1 Introduction
- The adaptive two-sided tester answers the open question of polynomial query complexity in d and 1/ϵ for testing binary rank.Binary rank is the minimum size of a factorization M = A · B using 0,1 matrices and integer operations.Source: §1 · pp. 1, 3
- With rankbin(M) ≤ d, an adaptive randomized algorithm outputs 0,1 factors whose product differs from M on at most an O(ϵ) fraction of entries, with probability at least 5/6.The factors have sizes n × d and d × m, and their product is a 0,1 matrix.Source: §1 · p. 3
- The same testing result applies in the dense adjacency-matrix model to testing whether a bipartite graph’s edges can be partitioned into at most d bicliques.The binary rank of the reduced adjacency matrix equals the graph’s biclique partition number.Source: §1 · p. 3
- The polynomial query complexity is distinct from running time: the testers have 2^O(d²) factors, and decomposition also depends on n and m.Theorem 2’s running time is independent of n and m; the decomposition algorithm’s running time includes an n + m factor.Source: §1 · p. 3
Overview of our Algorithms
- The tester avoids finding all possible rows and columns by extracting a small real linear core, enumerating its binary decompositions, and checking whether they extend to sampled rows and columns.Extensions must respect the core’s real-linear predictions and have pairwise products that are 0,1.Source: Overview of our Algorithms · pp. 3–4
- If rankbin(M) ≤ d, a compact description is consistent with all but a small fraction of rows and columns; if M is ϵ-far, every such description fails on a noticeable fraction.When the core has real rank rankR(M), the description is consistent with every row and column.Source: Overview of our Algorithms · p. 4
2 Preliminaries
The preliminaries establish notation for indexing submatrices and restricted rows and columns, then relate those restrictions to a binary decomposition. They also define vector support and orthogonal complements.
2 Preliminaries
- [s] denotes the indices 1 through s, and M[I, J] selects the submatrix with row indices I and column indices J.I_d denotes the d × d identity matrix.Source: §2 · p. 4
- M[i, J] and M[I, j] are row and column vectors restricted to the specified column and row sets, respectively.Source: §2 · p. 5
- For M = A · B, restricting to I and J gives M[I, J] = A_I · B_J, and a binary factor row-column product lies in {0, 1}.The product of a row of A and a column of B can be read as their inner product.Source: §2 · p. 5
- The support of a binary vector is the set of coordinates equal to 1; W⊥ denotes a subspace's orthogonal complement under the standard inner product.Source: §2 · p. 5
3 Finding a small full real rank core
The first phase adaptively builds a square, full-real-rank core by adding sampled row-column pairs only when they increase rank. With probability at least 5/6, it either finds a core of size d + 1 or stops with prediction error density at most η.
3 Finding a small full real rank core
- The algorithm grows a square core by adding a sampled row and column only when the enlarged submatrix's real rank increases by one.It initializes an empty core and stops after T sampled pairs fail to increase the current core's rank.Source: §3 · pp. 5–6
- For a full-rank core P, the core predicts M_i,j as M[i, J] · P^-1 · M[I, j], the unique entry that preserves the core's real rank.The prediction error density is the fraction of entries that disagree with this prediction.Source: §3 · p. 6
- If M is ε-far from real rank at most d and the current core has rank r ≤ d, at least an ε fraction of row-column pairs increase its rank.Source: §3 · p. 6
- A sampled pair disagrees with the core prediction exactly when adjoining its row and column increases real rank, so δ(I, J) is the probability of that increase.Source: §3 · pp. 6–7
- With probability at least 5/6, Algorithm 1 finds a full-real-rank core of size d + 1 or stops with prediction error density δ(I, J) ≤ η.Source: §3 · p. 7
- The binary-rank tester needs a smaller prediction-error threshold η than real-rank testing because its second phase requires a more accurate core.Source: §3 · p. 8
- When the final core size equals rankR(M), it predicts every entry exactly and has δ(I, J) = 0.Source: §3 · p. 8
- The binary tester has one-sided error when the core reaches rankR(M), but can err on YES instances when it stops early with nonzero prediction error.Source: §3 · p. 8
4 Using the core to test the binary rank
The section presents an algorithm for testing whether a matrix has binary rank at most d, using a full-real-rank core and enumerable candidates built from compatible row and column extensions. Algorithm 2 samples rows and columns to assess candidate decompositions, with two-sided error and query complexity O(d^3 log(d + 1)/ϵ^2).
4 Using the core to test the binary rank
- If the core has real rank r ≥ d + 1, the algorithm rejects; otherwise, it considers binary decompositions of size d of the core and compatible extensions to the full matrix.It considers all size-d core decompositions because a decomposition of the full matrix may use more than r coordinates on the core, even though the core itself has a size-r decomposition.Source: §4 · p. 8
4.1 Separating the core prediction from the residual part
- For each fixed core decomposition, a row–column extension product equals the core prediction plus a residual product factored through a real space of dimension d − r.The residual factorization uses matrices U and V with d − r columns and rows, respectively.Source: §4.1 · pp. 9–10
4.2 Making the residual product vanish
- A subspace W can capture most row residual vectors while its orthogonal complement captures most column residual vectors, making their residual products vanish; W can be spanned by at most d − r row residual vectors.For fixed U and V, the algorithm enumerates relevant subspaces by spanning collections of at most d − r vectors a · U for binary vectors a.Source: §4.2 · pp. 10–12
4.3 Keeping the products binary
- To keep extension products binary, a graph on d vertices represents row supports as cliques and column supports as independent sets, ensuring each row–column pair has at most one common coordinate.This makes the dot product lie in {0, 1}.Source: §4.3 · p. 13
4.4 Candidates
- A candidate is a core decomposition, a relevant subspace, and a d-vertex graph; rows and columns are good when they have extensions satisfying the corresponding subspace and graph conditions.The candidate family is nonempty, and Lemma 11 bounds its size, though the bound’s formatting in the supplied passage is ambiguous.Source: §4.4 · p. 14
4.5 The testing algorithm for the binary rank
- Algorithm 2 uses Algorithm 1 to find a core, then introduces Steps 3–6 as estimating quantities, but the supplied passage ends before specifying them.The excerpt does not identify what those steps estimate.Source: §4.5 · p. 14
- Every candidate with bad-row and bad-column fractions ρC and γC implies a binary matrix M′ of binary rank at most d with dist(M, M′) ≤ ρC + γC + δ(I, J).Thus, if M is ϵ-far from binary rank at most d, every candidate has ρC + γC + δ(I, J) ≥ ϵ.Source: §4.5 · pp. 16–17
- For any full-real-rank core of a matrix with binary rank at most d, some candidate has ρC + γC ≤ 2dδ(I, J).The algorithm samples rows and columns, counts which are bad for each candidate, and accepts if a candidate has sufficiently few sampled bad rows and columns.Source: §4.5 · pp. 15, 17
- Under δ(I, J) ≤ η = ϵ²/(256d), rankbin(M) ≤ d implies some candidate C has ρC + γC ≤ ϵ/8; if M is ϵ-far from binary rank at most d, every candidate has ρC + γC ≥ 255ϵ/256.Source: §4.5 · p. 18
- With probability at least 2/3, Algorithm 2 tests binary rank at most d using O(d^3 log(d + 1)/ϵ^2) queries.The query bound is dominated by Algorithm 1; the second phase uses O(d^3/ϵ) additional queries.Source: §4.5 · pp. 15, 18
5 Proof of Theorem 3
The core found by Algorithm 1 can be used to construct an approximate binary decomposition, with a 5/6 success guarantee. The construction queries core rows and columns, evaluates candidate extensions, and forms a binary product from a selected candidate.
5 Proof of Theorem 3
- With probability at least 5/6, the returned core can be used to construct an approximate decomposition M′ = A′ · B′.The factors are 0,1 matrices, and their product is a 0,1 matrix of binary rank at most d.Source: §5 · pp. 19–20
- At most d(n + m) additional queries reveal every row on core columns and every column on core rows, enabling explicit construction.For each candidate, these entries determine good rows and columns; the construction selects a candidate minimizing ρ_C + γ_C.Source: §5 · pp. 19–20
- The selected candidate supplies row and column extensions whose products match the core prediction and remain binary.For pairs outside the core, the compatibility conditions ensure the product is the predicted matrix entry; pairs involving the core are exact.Source: §5 · p. 20
- The constructed product can differ from M only outside the selected good rows or columns, or where the core prediction is wrong.The fractions of rows and columns omitted from the selected sets are bounded by the candidate’s bad-row and bad-column fractions.Source: §5 · p. 20
- The construction uses 2^O(d^2)(n + m) poly(d) arithmetic operations, in addition to its query cost.The cited query bound is at most d(n + m) additional queries beyond Algorithm 1.Source: §5 · pp. 19, 21
Declaration of generative AI usage
The author used ChatGPT 5.6 Sol interactively to propose proof ideas and explore suggestions. The author directed the mathematical development and states responsibility for verifying and finalizing the manuscript.
Declaration of generative AI usage
- The author used ChatGPT 5.6 Sol interactively for proof ideas and suggestions, while directing the mathematical development and verifying the final manuscript.The author says they take full responsibility for the manuscript’s correctness and content.Source: Declaration of generative AI usage · p. 21