cs.DSNov 10, 2026
SaveNonadaptive One-Sided Testing of Binary Rank
Organizations: Faculty of Computer Science, Technion Israel Institute of Technology
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 , with one-sided error and nonadaptive queries. We give a tester using queries, independent of the matrix dimensions and a general lower bound of .
Figures & tables
| Upper-bound source | Model | Queries |
|---|---|---|
| Nakar–Ron [ 4 , 5 ] | Nonadaptive, one-sided | |
| Parnas–Ron–Shraibman [ 5 ] | Nonadaptive, one-sided | |
| Bshouty [ 2 ] | Nonadaptive, one-sided | |
| Parnas [ 7 ] | Adaptive, two-sided | |
| Theorem 3.4 | Nonadaptive, one-sided |
Table 1: Selected upper bounds for binary rank at most . The models differ as indicated.
| Result | Query complexity |
|---|---|
| Upper bound (Theorem 3.4 ) | |
| Lower bound (Theorem 5.3 ) |
Table 2: General nonadaptive one-sided testing of binary rank at most .
Low-rank approximation can require additional matrix--vector products to verify that its error meets a prescribed tolerance. We characterize this certification cost for both relative matrix error and mean-square output error. For a single approximation matrix candidate, we determine the exact dimension-uniform minimax query constant as the allowed failure probability vanishes. Our main result concerns reusing validation responses as the approximation space expands. For a candidate family constructed independently of validation, one batch supports an entire nested path without increasing the query budget with the number of checks. Across paths, a concentration bound exploiting shared residual energy yields a dependence. A matching lower bound establishes its optimality for fixed interior error targets and sufficiently small separation gaps. Finally, we compare two uniformly valid certificates on the same dispersed-spectrum family. Optimizing the validation budget within each rule family yields costs of orders and for validation and construction beyond the true target. Code is available at https://anonymous.4open.science/r/Low-rank-approximation-1275/
Exact Risk Certificates for Pairwise-Judged Reranking
Pairwise relevance judgments constrain both the loss numerator and the ideal-ranking denominator of nDCG. We characterize the exact worst-case loss of replacing a ranking with a fixed proposal. Binary gains attain this loss and provide an inspectable witness. Threshold verification reduces to at most maximum-closure problems. Our exposure-flow ablation isolates denominator coupling: on shared judge trajectories, exact verification saves 2.34 comparisons per TREC-DL development query and 1.98 per confirmation query at a budget of 32. Savings transfer to BEIR and a second proposer. Predictive gates achieve higher deployment gains, while certificates expose the worst gains still permitted by accepted comparisons.
Sorting from Counterexamples
Consider the following problem of learning an unknown linear order on items. In each round, the learner guesses a complete ordering of the items and receives either confirmation that the guess is correct or a counterexample: a pair of items in the wrong order. The goal is to identify the unknown order using as few queries as possible. We study this problem when up to of the returned counterexamples may be untruthful, where is not known in advance. We determine the optimal query complexity up to constant factors:
Thus, while the noiseless complexity matches the classical complexity of sorting, each untruthful counterexample incurs an additional cost of order . The upper bound is based on a geometric representation of permutations and Grünbaum's theorem, while the lower bound combines sorting arguments with a Condorcet-type construction. We also study the case where the target ranking has a low-dimensional geometric representation: each item is represented by a point in , and the ranking is obtained by projecting the points onto an unknown direction. For these classes we give an upper bound of and a lower bound of , leaving a factor of gap in the noiseless term.