Nonnegative rank vs. binary rank

DOI10.4086/CJTCS.2016.002MaRDI QIDQ2808527zbMATHOpenAlexFDO

Authors Thomas Watson

Publication date 24 May 2016

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

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

zbMATH Keywords

communication complexitynonnegative rankbinary 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

(10)

• On the nonnegative rank of distance matrices
• Binary ranks and binary factorizations of nonnegative integer matrices
• Information-theoretic approximations of the nonnegative rank
• Alternating sign matrices, related (0,1)-matrices, and the Smith normal form
• The augmentation property of binary matrices for the binary and Boolean rank
• 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
• Communication complexity with small advantage
• The nonnegative rank of a matrix: hard problems, easy solutions

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)