On the complexity of Boolean matrix ranks

DOI10.1016/J.LAA.2013.06.033MaRDI QIDQ2435409zbMATH OpenOpenAlexFDO

Authors Ya. N. Shitov

Publication date 19 February 2014

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityrank functionsBoolean matrices

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean and Hadamard matrices (15B34) Vector spaces, linear dependence, rank, lineability (15A03)

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.

Cites work

• scientific article; zbMATH DE number 3786527 (Why is no real title available?)
• scientific article; zbMATH DE number 5019906 (Why is no real title available?)
• A comparison of two lower-bound methods for communication complexity
• A condition for the strong regularity of matrices in the minimax algebra
• Combinatorial bounds on nonnegative rank and extended formulations
• Fooling-sets and rank in nonzero characteristic
• Max-algebra: The linear algebra of combinatorics?
• Methods and applications of \((\max,+)\) linear algebra
• Properties of MPC for max-plus-linear systems
• Strong regularity of matrices -- a survey of results

Cited in

(13)

• Complexity of Searching for 2 by 2 Submatrices in Boolean Matrices
• Rank functions of tropical matrices
• On extremal matrices of second largest exponent by Boolean rank
• scientific article; zbMATH DE number 7391091 (Why is no real title available?)
• The rectangle covering number of random Boolean matrices
• Upper bounds on the Boolean rank of Kronecker products
• The nonnegative rank of a matrix: hard problems, easy solutions
• A bound on the generalized competition index of a primitive matrix using Boolean rank
• Circulant almost cross intersecting families
• Alternating sign matrices, related (0,1)-matrices, and the Smith normal form
• Approximating the volume of tropical polytopes is difficult
• Fooling-sets and rank
• The Boolean rank of the uniform intersection matrix and a family of its submatrices

This page was built for publication: On the complexity of Boolean matrix ranks

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