CS Paper Radar

Nonadaptive One-Sided Testing of Binary Rank

Nader H. Bshouty

cs.DS cs.LG ·submitted 2026-11-10 14:47 UTC · v1
theory

Abstract

The binary rank of a binary matrix is the minimum number of disjoint all-one rectangles that partition its one-entries. We study entry-query testing of binary rank at most $d$, with one-sided error and nonadaptive queries. We give a tester using $\tilde O(d^4/ε^2)$ queries, independent of the matrix dimensions and a general lower bound of $\tilde Ω(d^{3/2}/ε)$.

Closest papers

Nearest neighbours by meaning across the whole index.

Testing the Binary Rank with Polynomial Query Complexity

cs.DS cs.DM ·2026-09-09 ·Michal Parnas
similarity 0.79
Abstract

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)/ε^2)$, where $d$ is the tested binary rank bound and $ε$ 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/ε$. 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(ε)$ 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.

0.40

On the Binary Rank of Matrices with Constant Real Rank

cs.DM math.CO ·2026-09-24 ·Michal Parnas
theory similarity 0.67
Abstract

We study the problem of determining upper bounds on the maximal binary rank, $b_d$, of a $0,1$ matrix with real rank $d$, for small constant $d$. We prove a general upper bound of $b_d \leq \left\lfloor \sqrt{d2^d + 2d}\right\rfloor -1$. We also develop a general dimension reduction technique of bounding $b_d$ using known upper bounds on $b_{d-1}$ and $b_{d-2}$, as well as prove interesting general structural results on extremal matrices with binary rank $b_d$. This allows us to get improved non-trivial upper bounds on $b_d$ for constant values of $d$, which imply tight bounds on $b_d$ for $3 \leq d \leq 5$. Our results also imply bounds on the equivalent problem of finding the minimum number of bicliques needed to partition the edges of a bipartite graph whose reduced adjacency matrix has real rank at most $d$.

0.12

Metric Testing: A Characterization of One-Sided Testability

cs.DM cs.DS ·2026-10-31 ·Zihan Tan, Theo Teske
theory similarity 0.62
Abstract

We give a unified framework for one-sided testability (constant-query testing) of metric families. For a broad class of families defined by fixed local predicates, we prove that testability is equivalent to two structural properties: \emph{packing amplification}, which turns many edge-disjoint local violations into a positive density of violations, and \emph{completion stability}, which allows locally consistent partial matrices with few missing entries to be cheaply completed. This characterization yields a common proof strategy and simpler proofs of classical testability results for ultrametrics, tree pseudometrics, Euclidean pseudometrics in fixed dimension, and several others. Our framework also gives new quantitative bounds for metric testing: a nonadaptive one-sided upper bound for matrices with entries in the bounded range $[1,C]$, and two-sided nonadaptive and adaptive lower bounds for general metrics.

0.23

The rank of the random $k$-XORSAT matrix beyond satisfiability

cs.DM math.PRmath.CO ·2026-10-19 ·Amin Coja-Oghlan, Maurice Rolvien
similarity 0.59
Abstract

The random $k$-XORSAT matrix is an $m\times n$ random matrix $\mathbf A$ over $\mathbb F_2$ that represents a random instance of the $k$-XORSAT problem. Each row of $\mathbf A$ contains precisely $k\geq3$ non-zero entries in random positions. The rows are drawn independently. The matrix $\mathbf A$ is known to have full row rank for $m/n$ below the random $k$-XORSAT satisfiability threshold, which is known explicitly [Dubois, Mandler~2002; Pittel, Sorkin~2016]. Motivated by a problem from quantum game theory and refining a result of Cooper, Frieze and Pegden (2019), we determine the limiting distribution of the rank of $\mathbf A$ beyond the satisfiability threshold.

0.25

Near-Linear Lower Bounds for Testing Directed Acyclicity

cs.DS ·2026-11-03 ·Artur Czumaj, Pan Peng, Yuyang Wang
similarity 0.58
Abstract

We study testing acyclicity of directed graphs in the bounded-degree incidence-lists model, where a tester can query the outneighbors of a vertex but not its inneighbors. Despite significant effort, no tester with $o(n)$ queries is known, while the best established lower bounds are $\widetildeΩ(n^{5/9})$ for one-sided testers (Chen, Randolph, Servedio, and Sun, 2022) and $Ω(n^{1/3})$ for two-sided testers (Bender and Ron, 2002). We show that a query exponent arbitrarily close to one is necessary: for every fixed $η\in(0,1)$, there exists a constant $\varepsilon_η>0$ such that, for every constant $d\ge2$, every randomized adaptive two-sided $\varepsilon_η$-tester for acyclicity of simple $n$-vertex directed graphs whose indegrees and outdegrees are at most $d$ makes $Ω(n^{1-η})$ queries. Our proof overcomes two barriers. First, in previous constructions, the acyclic part of the graph is easy to recognize, which helps an algorithm stay inside the cyclic part. We hide a high-girth cyclic core inside a hierarchy of acyclic masking regions, in which each region imitates the levels below it and can be told apart from them only through rare events, and an iterated information-theoretic argument shows that every exploration observes only small, low-diameter forest components of the core. Second, a two-sided tester may exploit the statistics of collisions without ever seeing a cycle, and at a near-linear budget collisions are unavoidable. We compare complete transcripts with those of an acyclic input built on a fixed core by counting injective embeddings of the observed forest: in high-girth cores, all connected collision patterns of bounded order contribute identically, which makes the two transcript distributions statistically indistinguishable.

0.24

Improved Quantum Query Bounds for Boolean Matrix Product Verification

cs.DS quant-ph ·2026-09-30 ·Amin Shiraz Gilani, François Le Gall, Xingyu Zhou
theory similarity 0.57
Abstract · 38 pages

We prove the first non-trivial upper bound for the quantum query complexity of Boolean Matrix Product Verification ($\mathsf{BMPV}$), answering a longstanding open question in quantum query complexity. For $n\times n$ matrices, our upper bound is $\widetilde O(n^{17/12})$, improving on the standard $O(n^{3/2})$ bound obtained using Grover search by Buhrman and Špalek [SODA 2006]. We complement this result by showing an $Ω(n^{5/4})$ lower bound, which improves over the previous best known lower bound of $\widetildeΩ(n^{19/18})$ by Childs, Kimmel, and Kothari [ESA 2012]. Our approach centers on a connection with Orthogonal Vectors ($\mathsf{OV}$), which asks whether an indexed list of $n$ Boolean vectors of dimension $n$ contains two vectors with disjoint supports. In particular, we prove equivalences between $\mathsf{OV}$ and $\mathsf{BMPV}$ and establish the above bounds for $\mathsf{OV}$. We also prove a tight $\widetilde Θ(n^{3/2})$ bound for a variant of $\mathsf{BMPV}$ that asks whether the product contains a given row vector. Together, these results imply a polynomial separation between the quantum query complexities of deciding whether a graph has radius at most two and whether it has diameter at most two.

0.25

Testing MAX-CUT in the Adjacency Matrix Model: Tight Non-Adaptive Bounds and a Cubic Adaptive Lower Bound

cs.DS ·2026-10-31 ·Songhua He
theory similarity 0.56
Abstract

We study the query complexity of approximating the MAX-CUT value to additive error $\varepsilon n^2$ in the adjacency matrix model. This was one of the first problems studied in graph property testing [GGR'98]. Previously, the best known upper bound for both adaptive and non-adaptive algorithms was $O(1/\varepsilon^6)$ [RV'07; MS'08; GMRS'22]. The only known lower bound was a trivial $Ω(1/\varepsilon^2)$ bound. We close this gap from both sides for non-adaptive algorithms, proving that its query complexity is exactly $Θ(1/\varepsilon^4)$. We also prove an adaptive $Ω(1/\varepsilon^3)$ lower bound. Our upper bound is achieved by a canonical tester that samples $O(1/\varepsilon^2)$ vertices in expectation and outputs the rescaled MAX-CUT value of the induced subgraph. We prove its correctness by applying spectral truncation to the adjacency matrix, using a geometric argument to control the sampling error of the retained low-rank part and a cut-norm restriction estimate [RV'07] for the remainder. As an application, an analogous proof also yields a tight $O(1/\varepsilon^4)$ non-adaptive query upper bound for MAX-2CSP. For our lower bounds, we show indistinguishability between a uniform random graph and a random graph with a planted hidden partition. For the non-adaptive lower bound, we observe that one plus the $χ^2$-divergence between the query transcript distributions is exactly a normalized Ising partition function, which can be bounded using Boolean hypercontractivity. For the adaptive lower bound, we relate each query's distinguishing power to the prediction, based on previous answers, of whether its endpoints lie in the same part of the hidden partition. We bound the combined advantage of these predictions using the completed transcript, which lets us analyze the adaptively chosen pairs of vertices together despite their dependence on earlier answers.

0.20

Testing Induced-Subgraph Freeness in Outerplanar Graphs under the Random-Neighbor Oracle

cs.DS ·2026-09-30 ·Pan Peng, Kefan Yu
theory similarity 0.56
Abstract

We prove that, for every fixed nonempty graph $H$, induced-$H$-freeness is testable with $\varepsilon^{-O_H(1)}$ queries on outerplanar graphs with no maximum-degree bound in the $\textit{random-neighbor model}$, where each query at a vertex returns a uniformly random neighbor. Thus, the query complexity is polynomial in $1/\varepsilon$ and independent of the number $n$ of vertices. Previously, the best bound known for this problem was the $\operatorname{poly}(\log n)$-query guarantee that follows from the general outerplanar-graph tester of Babu, Khoury, and Newman (2016) in the stronger $\textit{adjacency-list model}$, which provides exact degree queries and indexed access to neighbors. Our tester has $\textit{two-sided error}$, which is necessary in general: induced-$P_3$-freeness has no one-sided constant-query tester in the random-neighbor model, even on outerplanar graphs of maximum degree two.

0.16