Fooling-sets and rank

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

zbMATH Keywords

fooling-set matrix

Mathematics Subject Classification ID

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