On the binary and Boolean rank of regular matrices
From MaRDI portal
Publication:2689370
DOI10.1016/j.jcss.2023.01.005OpenAlexW4318978770MaRDI QIDQ2689370
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
complexitycommunication complexityBoolean rankbinary rankAlon-Saks-Seymour conjectureregular matricesnon-deterministic communicationunambiguous non-deterministic
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)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Clique-stable set separation in perfect graphs with no balanced skew-partitions
- Clique versus independent set
- A counterexample to the Alon-Saks-Seymour conjecture and related problems
- More counterexamples to the Alon-Saks-Seymour and rank-coloring conjectures
- Boolean function complexity. Advances and frontiers.
- Biclique coverings of regular bigraphs and minimum semiring ranks of regular matrices
- On the minimum rank of regular classes of matrices of zeros and ones
- Expressing combinatorial optimization problems by linear programs
- The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear
- Decomposition techniques applied to the clique-stable set separation problem
- Improving the Hadamard extractor
- Subdivided claws and the clique-stable set separation property
- Ordered biclique partitions and communication complexity problems
- Some improved bounds on communication complexity via new decomposition of cliques
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- Deterministic Communication vs. Partition Number
- Low-Sensitivity Functions from Unambiguous Certificates.
- Recent advances on the log-rank conjecture in communication complexity
- Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
- On the Addressing Problem for Loop Switching
- Query-to-Communication Lifting Using Low-Discrepancy Gadgets
- Rectangles Are Nonnegative Juntas
This page was built for publication: On the binary and Boolean rank of regular matrices
