Nonnegative rank vs. binary rank

DOI10.4086/CJTCS.2016.002zbMATH Open1356.68085arXiv1603.07779OpenAlexW2303197778MaRDI QIDQ2808527FDOQ2808527

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

Recommendations

• On the nonnegative rank of distance matrices
• Real rank versus nonnegative rank
• scientific article; zbMATH DE number 4008576
• Extended formulations, nonnegative factorizations, and randomized communication protocols
• Lower bounds on nonnegative rank via nonnegative nuclear norms

zbMATH Keywords

communication complexitynonnegative rankbinary rank

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• The Nonnegative Rank of a Matrix: Hard Problems, Easy Solutions
• Binary ranks and binary factorizations of nonnegative integer matrices
• The augmentation property of binary matrices for the binary and Boolean rank
• Rectangles are nonnegative juntas
• On the nonnegative rank of distance matrices
• Title not available (Why is that?)
• Alternating sign matrices, related (0,1)-matrices, and the Smith normal form
• Communication complexity with small advantage

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)