Document Open Access Logo

The Minrank of Random Graphs

Authors Alexander Golovnev, Oded Regev, Omri Weinstein

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.46.pdf
  • Filesize: 0.5 MB
  • 13 pages

Document Identifiers

Author Details

Alexander Golovnev
Oded Regev
Omri Weinstein

Cite As Get BibTex

Alexander Golovnev, Oded Regev, and Omri Weinstein. The Minrank of Random Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 46:1-46:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.46

Abstract

The minrank of a directed graph G is the minimum rank of a matrix M that can be obtained from the adjacency matrix of G by switching some ones to zeros (i.e., deleting edges) and then setting all diagonal entries to one. This quantity is closely related to the fundamental information-theoretic problems of (linear) index coding (Bar-Yossef et al., FOCS'06), network coding and distributed storage, and to Valiant's approach for proving superlinear circuit lower bounds (Valiant, Boolean Function Complexity '92). 

We prove tight bounds on the minrank of directed Erdos-Renyi random graphs G(n,p) for all regimes of 0<p<1. In particular, for any constant p, we show that minrk(G) = Theta(n/log n) with high probability, where G is chosen from G(n,p). This bound gives a near quadratic improvement over the previous best lower bound of Omega(sqrt{n}) (Haviv and Langberg, ISIT'12), and partially settles an open problem raised by Lubetzky and Stav (FOCS '07). Our lower bound matches the well-known upper bound obtained by the "clique covering" solution, and settles the linear index coding problem for random graphs. 

Finally, our result suggests a new avenue of attack, via derandomization, on Valiant's approach for proving superlinear lower bounds for logarithmic-depth semilinear circuits.

Subject Classification

Keywords
  • circuit complexity
  • index coding
  • information theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li, and Raymond W. Yeung. Network information flow. IEEE Trans. Inf. Theory, 46(4):1204-1216, 2000. Google Scholar
  2. Noga Alon and Joel H. Spencer. The Probabilistic Method. Wiley Series in Discrete Mathematics and Optimization. Wiley, 2016. Google Scholar
  3. Fatemeh Arbabjolfaei and Young-Han Kim. Three stories on a two-sided coin: Index coding, locally recoverable distributed storage, and guessing games on graphs. In Allerton Conf. Control, Communication and Computing 2015, pages 843-850. IEEE, 2015. Google Scholar
  4. Ziv Bar-Yossef, Yitzhak Birk, T. S. Jayram, and Tomer Kol. Index coding with side information. In FOCS 2006, pages 197-206. IEEE, 2006. Google Scholar
  5. Yitzhak Birk and Tomer Kol. Informed-source coding-on-demand (ISCOD) over broadcast channels. In INFOCOM 1998, pages 1257-1264, 1998. Google Scholar
  6. Yitzhak Birk and Tomer Kol. Coding on demand by an informed source (ISCOD) for efficient broadcast of different supplemental data to caching clients. IEEE Trans. Information Theory, 52(6):2825-2830, 2006. URL: http://dx.doi.org/10.1109/TIT.2006.874540.
  7. Béla Bollobás. The chromatic number of random graphs. Combinatorica, 8(1):49-55, 1988. Google Scholar
  8. Chris Calabro. A lower bound on the size of series-parallel graphs dense in long paths, 2008. ECCC, TR08-110. Google Scholar
  9. Eden Chlamtac and Ishay Haviv. Linear index coding via semidefinite programming. Combinatorics, Probability & Computing, 23(2):223-247, 2014. URL: http://dx.doi.org/10.1017/S0963548313000564.
  10. Michelle Effros, Salim Y. El Rouayheb, and Michael Langberg. An equivalence between network coding and index coding. IEEE Trans. Information Theory, 61(5):2478-2487, 2015. URL: http://dx.doi.org/10.1109/TIT.2015.2414926.
  11. Willem Haemers. An upper bound for the Shannon capacity of a graph. In Colloq. Math. Soc. János Bolyai, volume 25, pages 267-272, 1978. Google Scholar
  12. Willem Haemers. On some problems of Lovász concerning the Shannon capacity of a graph. IEEE Trans. Inf. Theory, 25(2):231-232, 1979. Google Scholar
  13. H. Tracy Hall, Leslie Hogben, Ryan Martin, and Bryan Shader. Expected values of parameters associated with the minimum rank of a graph. Linear Algebra and its Applications, 433(1):101-117, 2010. Google Scholar
  14. Ishay Haviv and Michael Langberg. On linear index coding for random graphs. In ISIT 2012, pages 2231-2235. IEEE, 2012. Google Scholar
  15. Roger A. Horn and Charles R. Johnson. Matrix analysis. Cambridge University Press, Cambridge, second edition, 2013. Google Scholar
  16. Stasys Jukna and Georg Schnitger. Min-rank conjecture for log-depth circuits. J. Comput. Syst. Sci., 77(6):1023-1038, 2011. URL: http://dx.doi.org/10.1016/j.jcss.2009.09.003.
  17. Ilan Kremer, Noam Nisan, and Dana Ron. On randomized one-round communication complexity. In STOC 1995, pages 596-605, New York, NY, USA, 1995. ACM. URL: http://dx.doi.org/10.1145/225058.225277.
  18. Eyal Lubetzky and Uri Stav. Non-linear index coding outperforming the linear optimum. In FOCS 2007, pages 161-168. IEEE, 2007. Google Scholar
  19. Tomasz Łuczak. The chromatic number of random graphs. Combinatorica, 11(1):45-54, 1991. Google Scholar
  20. Mihai Patrascu. Towards polynomial lower bounds for dynamic problems. In STOC 2010, pages 603-610, 2010. URL: http://dx.doi.org/10.1145/1806689.1806772.
  21. Pavel Pudlák, Vojtech Rödl, and Jirí Sgall. Boolean circuits, tensor ranks, and communication complexity. SIAM J. Comput., 26(3):605-633, 1997. Google Scholar
  22. Søren Riis. Information flows, graphs and their guessing numbers. Electr. J. Comb., 14(1), 2007. URL: http://www.combinatorics.org/Volume_14/Abstracts/v14i1r44.html.
  23. Leslie G. Valiant. Graph-theoretic arguments in low-level complexity. In MFCS 1977, pages 162-176, 1977. Google Scholar
  24. Leslie G. Valiant. Exponential lower bounds for restricted monotone circuits. In STOC 1983, pages 110-117. ACM, 1983. Google Scholar
  25. Leslie G. Valiant. Why is Boolean complexity theory difficult. Boolean Function Complexity, 169:84-94, 1992. Google Scholar
  26. Emanuele Viola. On the power of small-depth computation. Foundations and Trends in Theoretical Computer Science, 5(1):1-72, 2009. Google Scholar
  27. Raymond W. Yeung and Zhen Zhang. Distributed source coding for satellite communications. IEEE Trans. Inf. Theory, 45(4):1111-1120, 1999. URL: http://dx.doi.org/10.1109/18.761254.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact