Property testing of the Boolean and binary rank

DOI10.1007/S00224-021-10047-8zbMATH Open1503.68304arXiv1908.11632OpenAlexW3166150802MaRDI QIDQ825974FDOQ825974

Authors: Michal Parnas, Dana Ron, Adi Shraibman 

Publication date: 18 December 2021

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

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$.

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

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

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)

Cites Work

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

Cited In (2)

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

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)