The minrank of random graphs

DOI10.4230/LIPIcs.APPROX-RANDOM.2017.46zbMath1467.05244OpenAlexW2898680372MaRDI QIDQ5002652

Omri Weinstein, Alexander Golovnev, Oded Regev

Publication date: 28 July 2021

Full work available at URL: https://dblp.uni-trier.de/db/conf/approx/approx2017.html#Golovnev0W17

zbMATH Keywords

information theorycircuit complexityindex coding

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Source coding (94A29) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (1)

The minrank of random graphs over arbitrary fields

Cites Work

• Min-rank conjecture for log-depth circuits
• Expected values of parameters associated with the minimum rank of a graph
• Information flows, graphs and their guessing numbers
• Towards polynomial lower bounds for dynamic problems
• An Equivalence Between Network Coding and Index Coding
• On the Power of Small-Depth Computation
• On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
• Boolean Circuits, Tensor Ranks, and Communication Complexity
• Network information flow
• Distributed source coding for satellite communications
• Nonlinear Index Coding Outperforming the Linear Optimum
• Index Coding With Side Information
• Linear Index Coding via Semidefinite Programming
• The chromatic number of random graphs
• The chromatic number of random graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The minrank of random graphs