On the complexity of Boolean matrix ranks

2013/05/25 by Yaroslav Shitov, Shitov, Yaroslav
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #cs.CC #math.CO

paper · pdf · doi:10.48550/arxiv.1306.1114

arxiv created 2013/05/25 · arxiv updated 2013/06/06

Abstract

We construct a reduction which proves that the fooling set number and the determinantal rank of a Boolean matrix are NP-hard to compute.

Related

• Boolean Rank via Monomial Ideals
• Property testing of the Boolean and binary rank
• Fooling-sets and rank in nonzero characteristic (extended abstract)
• On relative OR-complexity of Boolean matrices and their complements
• A Study of the Binary and Boolean Rank of Matrices with Small Constant Real Rank