On the binary and Boolean rank of regular matrices

DOI10.1016/J.JCSS.2023.01.005MaRDI QIDQ2689370zbMATH OpenOpenAlexFDO

Authors Ishay Haviv, Michal Parnas

Publication date 10 March 2023

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

Alon-Saks-Seymour conjecturebinary rankBoolean rankcommunication complexitycomplexitynon-deterministic communicationregular matricesunambiguous non-deterministic

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vector spaces, linear dependence, rank, lineability (15A03) Boolean and Hadamard matrices (15B34) Communication complexity, information complexity (68Q11)

Recommendations

• Minimum matrix rank of k-regular (0,1) matrices
• Further results on the minimum rank of regular classes of (0,1)-matrices
• Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices
• On upper bounds for the minimum rank of regular classes of (0,1)-matrices
• Publication:4207933

Cites work

• A counterexample to the Alon-Saks-Seymour conjecture and related problems
• Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
• Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices
• Boolean function complexity. Advances and frontiers.
• Clique versus independent set
• Clique-stable set separation in perfect graphs with no balanced skew-partitions
• Decomposition techniques applied to the clique-stable set separation problem
• Deterministic communication vs. partition number
• Expressing combinatorial optimization problems by linear programs
• scientific article; zbMATH DE number 3781471 (Why is no real title available?)
• scientific article; zbMATH DE number 4128849 (Why is no real title available?)
• scientific article; zbMATH DE number 736299 (Why is no real title available?)
• scientific article; zbMATH DE number 790476 (Why is no real title available?)
• Improving the Hadamard extractor
• Low-sensitivity functions from unambiguous certificates
• More counterexamples to the Alon-Saks-Seymour and rank-coloring conjectures
• On the Addressing Problem for Loop Switching
• On the minimum rank of regular classes of matrices of zeros and ones
• Ordered biclique partitions and communication complexity problems
• Query-to-communication lifting using low-discrepancy gadgets
• Recent advances on the log-rank conjecture in communication complexity
• Rectangles are nonnegative juntas
• Some improved bounds on communication complexity via new decomposition of cliques
• Subdivided claws and the clique-stable set separation property
• The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity

Cited in

(10)

• A class of binary matrices preserving rank under matrix addition and its application
• The binary rank of circulant block matrices
• The Boolean rank of the uniform intersection matrix and a family of its submatrices
• Further results on the minimum rank of regular classes of (0,1)-matrices
• scientific article; zbMATH DE number 7391091 (Why is no real title available?)
• Biwhitening Reveals the Rank of a Count Matrix
• On minimally non-firm binary matrices
• On the Binary and Boolean Rank of Regular Matrices
• The -rank of a (0, 1)-matrix
• On extremal matrices of second largest exponent by Boolean rank

This page was built for publication: On the binary and Boolean rank of regular matrices

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