Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > INDEX CODING:
Reports tagged with Index Coding:
TR16-110 | 19th July 2016
Alexander Golovnev, Oded Regev, Omri Weinstein

The Minrank of Random Graphs

Revisions: 1

The minrank of a graph $G$ is the minimum rank of a matrix $M$ that can be obtained from the adjacency matrix of $G$ by switching ones to zeros (i.e., deleting edges) and setting all diagonal entries to one. This quantity is closely related to the fundamental information-theoretic problems of ... more >>>




ISSN 1433-8092 | Imprint