cs.DSNov 10, 2026

Nonadaptive One-Sided Testing of Binary Rank

Authors: Nader H. Bshouty

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 dd, with one-sided error and nonadaptive queries. We give a tester using O~(d4/ε2)\tilde O(d^4/ε^2) queries, independent of the matrix dimensions and a general lower bound of Ω~(d3/2/ε)\tilde Ω(d^{3/2}/ε).

Figures & tables

Explore similar work

CardsList
  1. Information Limits of Low-Rank Approximation Certification

    Oct 2, 2026Kang Liu, Bohao QuLow-Rank ApproximationInformation-Theoretic Lower Bounds

  2. Exact Risk Certificates for Pairwise-Judged Reranking

    Oct 17, 2026Xinyu Wang, Jingrui Tian, Sicheng Lyu +4IR EvaluationPairwise Ranking

  3. Sorting from Counterexamples

    Aug 21, 2026Noga Alon, Shay Moran, Shlomo MoranQuery ComplexityPairwise Ranking