The rectangle covering number of random Boolean matrices
From MaRDI portal
Publication:2363099
zbMath1415.05167MaRDI QIDQ2363099
Mozhgan Pourmoradnasseri, Dirk Oliver Theis
Publication date: 13 July 2017
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p37
Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
- Smallest compact formulation for the permutahedron
- Expressing combinatorial optimization problems by linear programs
- Communication complexity and combinatorial lattice theory
- A comparison of two lower-bound methods for communication complexity
- Fooling sets and the spanning tree polytope
- Some new bounds for cover-free families through biclique covers
- Combinatorial bounds on nonnegative rank and extended formulations
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- On the complexity of Boolean matrix ranks
- On biclique coverings
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization
- Average Case Polyhedral Complexity of the Maximum Stable Set Problem
- Nondeterministic Communication Complexity of Random Boolean Functions (Extended Abstract)
- Fractional Covers and Communication Complexity
- Communication Complexity
- Strong Isometric Dimension, Biclique Coverings, and Sperner's Theorem
- Secure Frameproof Code Through Biclique Cover
- Linear vs. semidefinite extended formulations
- Fooling-sets and rank in nonzero characteristic (extended abstract)
- Probability and Computing
- Superboolean rank and the size of the largest triangular submatrix of a random matrix
This page was built for publication: The rectangle covering number of random Boolean matrices
