The minrank of random graphs

DOI10.4230/LIPICS.APPROX-RANDOM.2017.46MaRDI QIDQ5002652zbMATH OpenOpenAlexFDO

Authors Alexander Golovnev, O. Weinstein, 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

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

Recommendations

• The minrank of random graphs over arbitrary fields
• On minrank and forbidden subgraphs
• On minrank and forbidden subgraphs
• Polynomial time algorithm for min-ranks of graphs with simple tree structures
• Linear index coding via semidefinite programming

Cites work

• scientific article; zbMATH DE number 5454110 (Why is no real title available?)
• scientific article; zbMATH DE number 3745081 (Why is no real title available?)
• scientific article; zbMATH DE number 176871 (Why is no real title available?)
• scientific article; zbMATH DE number 3597878 (Why is no real title available?)
• scientific article; zbMATH DE number 1263236 (Why is no real title available?)
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• An Equivalence Between Network Coding and Index Coding
• Boolean Circuits, Tensor Ranks, and Communication Complexity
• Distributed source coding for satellite communications
• Expected values of parameters associated with the minimum rank of a graph
• Index Coding With Side Information
• Information flows, graphs and their guessing numbers
• Linear index coding via semidefinite programming
• Min-rank conjecture for log-depth circuits
• Network information flow
• Nonlinear Index Coding Outperforming the Linear Optimum
• On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
• On the power of small-depth computation
• The chromatic number of random graphs
• The chromatic number of random graphs
• The probabilistic method
• Towards polynomial lower bounds for dynamic problems

Cited in

(9)

• On minrank and forbidden subgraphs
• Linear index coding via semidefinite programming
• Polynomial time algorithm for min-ranks of graphs with simple tree structures
• The Min Mean-Weight Cycle in a Random Network
• The Minrank of Random Graphs
• Linear index coding via semidefinite programming
• Minimal functions on the random graph
• Expected values of parameters associated with the minimum rank of a graph
• The minrank of random graphs over arbitrary fields

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5002652)