On the complexity of Boolean matrix ranks

DOI10.1016/j.laa.2013.06.033zbMath1286.68209arXiv1306.1114OpenAlexW2056165892MaRDI QIDQ2435409

Yaroslav 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) Vector spaces, linear dependence, rank, lineability (15A03) Boolean and Hadamard matrices (15B34)

Related Items

Rank functions of tropical matrices, The rectangle covering number of random Boolean matrices, Circulant almost cross intersecting families, Alternating sign matrices, related (0,1)-matrices, and the Smith normal form, The Nonnegative Rank of a Matrix: Hard Problems, Easy Solutions, Approximating the volume of tropical polytopes is difficult, Fooling-sets and rank

Cites Work

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