Fooling-sets and rank
From MaRDI portal
Publication:2346587
DOI10.1016/j.ejc.2015.02.016zbMath1314.05028arXiv1208.2920OpenAlexW1996089856MaRDI QIDQ2346587
Mirjam Friesen, Dirk Oliver Theis, Troy Lee, Aya Hamed
Publication date: 2 June 2015
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1208.2920
Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)
Related Items (5)
Essential sign change numbers of full sign pattern matrices ⋮ The (minimum) rank of typical fooling-set matrices ⋮ Fooling sets and the spanning tree polytope ⋮ Rational realization of the minimum ranks of nonnegative sign pattern matrices ⋮ Ordered biclique partitions and communication complexity problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
- On covering graphs by complete bipartite subgraphs
- A notion of cross-perfect bipartite graphs
- Expressing combinatorial optimization problems by linear programs
- A comparison of two lower-bound methods for communication complexity
- Combinatorial bounds on nonnegative rank and extended formulations
- On the complexity of Boolean matrix ranks
- The minimum rank problem: A counterexample
- Jump Number of Two-Directional Orthogonal Ray Graphs
- Finding Lower Bounds for Nondeterministic State Complexity Is Hard
- Communication Complexity
- Computational Complexity
- Fooling-sets and rank in nonzero characteristic (extended abstract)
This page was built for publication: Fooling-sets and rank
