On the complexity of Boolean matrix ranks

DOI10.1016/J.LAA.2013.06.033zbMATH Open1286.68209arXiv1306.1114OpenAlexW2056165892MaRDI QIDQ2435409FDOQ2435409

Authors: Ya. N. Shitov 

Publication date: 19 February 2014

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

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.

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)

Cites Work

• Strong regularity of matrices -- a survey of results
• Max-algebra: The linear algebra of combinatorics?
• Title not available (Why is that?)
• Title not available (Why is that?)
• Methods and applications of \((\max,+)\) linear algebra
• Combinatorial bounds on nonnegative rank and extended formulations
• Properties of MPC for max-plus-linear systems
• A condition for the strong regularity of matrices in the minimax algebra
• A comparison of two lower-bound methods for communication complexity
• Fooling-sets and rank in nonzero characteristic (extended abstract)

Cited In (13)

• Rank functions of tropical matrices
• Title not available (Why is that?)
• On extremal matrices of second largest exponent by Boolean rank
• 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
• Complexity of Searching for 2 by 2 Submatrices in Boolean Matrices

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)