Property testing of the Boolean and binary rank

DOI10.1007/S00224-021-10047-8MaRDI QIDQ825974zbMATH OpenOpenAlexFDO

Authors Michal Parnas, Dana Ron, Adi Shraibman

Publication date 18 December 2021

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.11632

zbMATH Keywords

property testingbinary rankBoolean rank

Mathematics Subject Classification ID

Randomized algorithms (68W20) Boolean and Hadamard matrices (15B34) Matrices over special rings (quaternions, finite fields, etc.) (15B33)

Abstract: We present algorithms for testing if a $(0,1)$-matrix $M$ has Boolean/binary rank at most $d$, or is $epsilon$-far from Boolean/binary rank $d$ (i.e., at least an $epsilon$-fraction of the entries in $M$ must be modified so that it has rank at most $d$). The query complexity of our testing algorithm for the Boolean rank is $ildeOleft(d^4/epsilo{n}^{6}ight)$. For the binary rank we present a testing algorithm whose query complexity is $O(2^{2d}/epsilon)$. Both algorithms are $1$-sided error algorithms that always accept $M$ if it has Boolean/binary rank at most $d$, and reject with probability at least $2/3$ if $M$ is $epsilon$-far from Boolean/binary rank $d$.

Recommendations

• Testing matrix rank, optimally
• Testing of matrix properties
• Publication:4938660
• The augmentation property of binary matrices for the binary and Boolean rank
• Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries

Cites work

• scientific article; zbMATH DE number 3582190 (Why is no real title available?)
• scientific article; zbMATH DE number 2079317 (Why is no real title available?)
• Abstract Combinatorial Programs and Efficient Property Testers
• Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices
• Communication Complexity
• Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
• Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
• Nearly tight approximability results for minimum biclique cover and partition
• On Approximate Solutions for Combinatorial Optimization Problems
• On the testability of graph partition properties
• Property testing and its connection to learning and approximation
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing \(k\)-colorability
• Testing matrix rank, optimally
• The augmentation property of binary matrices for the binary and Boolean rank
• Tolerant property testing and distance approximation

Cited in

(2)

• Testing matrix rank, optimally
• The augmentation property of binary matrices for the binary and Boolean rank

This page was built for publication: Property testing of the Boolean and binary rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q825974)