Nonnegative rank vs. binary rank

DOI10.4086/CJTCS.2016.002MaRDI QIDQ2808527zbMATH OpenOpenAlexFDO

Authors Thomas Watson

Publication date 24 May 2016

Published in Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

binary rankcommunication complexitynonnegative rank

Mathematics Subject Classification ID

Boolean and Hadamard matrices (15B34) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On the nonnegative rank of distance matrices
• Real rank versus nonnegative rank
• scientific article; zbMATH DE number 4008576
• Lower bounds on nonnegative rank via nonnegative nuclear norms

Cites work

• An upper bound for nonnegative rank
• Communication complexity and combinatorial lattice theory
• Expressing combinatorial optimization problems by linear programs
• On rank vs. communication complexity
• Ordered biclique partitions and communication complexity problems
• The pattern matrix method

Cited in

(12)

• The augmentation property of binary matrices for the binary and Boolean rank
• Information-theoretic approximations of the nonnegative rank
• Communication complexity with small advantage
• Alternating sign matrices, related (0,1)-matrices, and the Smith normal form
• Binary ranks and binary factorizations of nonnegative integer matrices
• On the nonnegative rank of distance matrices
• The nonnegative rank of a matrix: hard problems, easy solutions
• Approximate nonnegative rank is equivalent to the smooth rectangle bound
• scientific article; zbMATH DE number 7650118 (Why is no real title available?)
• Rectangles are nonnegative juntas
• Sampling, flowers and communication
• A study of the binary and Boolean rank of matrices with small constant real rank

This page was built for publication: Nonnegative rank vs. binary rank

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