Document Open Access Logo

On Minrank and the Lovász Theta Function

Author Ishay Haviv

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.13.pdf
  • Filesize: 366 kB
  • 15 pages

Document Identifiers

Author Details

Ishay Haviv
  • School of Computer Science, The Academic College of Tel Aviv-Yaffo, Tel Aviv 61083, Israel

Cite AsGet BibTex

Ishay Haviv. On Minrank and the Lovász Theta Function. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.13

Abstract

Two classical upper bounds on the Shannon capacity of graphs are the theta-function due to Lovász and the minrank parameter due to Haemers. We provide several explicit constructions of n-vertex graphs with a constant theta-function and minrank at least n^delta for a constant delta>0 (over various prime order fields). This implies a limitation on the theta-function-based algorithmic approach to approximating the minrank parameter of graphs. The proofs involve linear spaces of multivariate polynomials and the method of higher incidence matrices.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Information theory
Keywords
  • Minrank
  • Theta Function
  • Shannon capacity
  • Multivariate polynomials
  • Higher incidence matrices

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. Inform. Theory, 46(4):1204-1216, 2000. Google Scholar
  2. Noga Alon. The Shannon capacity of a union. Combinatorica, 18(3):301-310, 1998. Google Scholar
  3. Noga Alon, László Babai, and H. Suzuki. Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems. J. Comb. Theory, Ser. A, 58(2):165-180, 1991. Google Scholar
  4. Noga Alon and Nabil Kahale. Approximating the independence number via the ϑ-function. Math. Program., 80:253-264, 1998. Google Scholar
  5. Noga Alon and Yuval Peres. A note on Euclidean Ramsey theory and a construction of Bourgain. Acta Math. Hungar., 57(1-2):61-64, 1991. Google Scholar
  6. László Babai and Peter Frankl. Linear Algebra Methods in Combinatorics With Applications to Geometry and Computer Science. Wiley-Interscience Series in Discrete Mathematics and Optimization. The University of Chicago, second edition, 1992. Google Scholar
  7. Ziv Bar-Yossef, Yitzhak Birk, T. S. Jayram, and Tomer Kol. Index coding with side information. In FOCS, pages 197-206, 2006. Google Scholar
  8. Piotr Berman and Georg Schnitger. On the complexity of approximating the independent set problem. Inf. Comput., 96(1):77-94, 1992. Preliminary version in STACS'89. Google Scholar
  9. 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. Inform. Theory, 52(6):2825-2830, 2006. Preliminary version in INFOCOM'98. Google Scholar
  10. Anna Blasiak, Robert Kleinberg, and Eyal Lubetzky. Broadcasting with side information: Bounding and approximating the broadcast rate. IEEE Trans. Information Theory, 59(9):5811-5823, 2013. Google Scholar
  11. Aart Blokhuis. On the Sperner capacity of the cyclic triangle. Journal of Algebraic Combinatorics, 2(2):123-124, 1993. Google Scholar
  12. Moses Charikar. On semidefinite programming relaxations for graph coloring and vertex cover. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 616-620, 2002. Google Scholar
  13. Eden Chlamtáč and Ishay Haviv. Linear index coding via semidefinite programming. Combinatorics, Probability & Computing, 23(2):223-247, 2014. Preliminary version in SODA'12. Google Scholar
  14. Amin Coja-Oghlan. The Lovász number of random graphs. Combinatorics, Probability & Computing, 14(4):439-465, 2005. Preliminary version in RANDOM'03. Google Scholar
  15. Irit Dinur and Igor Shinkar. On the conditional hardness of coloring a 4-colorable graph with super-constant number of colors. In APPROX-RANDOM, pages 138-151, 2010. Google Scholar
  16. Zeev Dvir, Parikshit Gopalan, and Sergey Yekhanin. Matching vector codes. SIAM J. Comput., 40(4):1154-1178, 2011. Preliminary version in FOCS'10. Google Scholar
  17. Salim El Rouayheb, Alex Sprintson, and Costas Georghiades. On the relation between the index coding and the network coding problems. In proceedings of IEEE International Symposium on Information Theory, pages 1823-1827. IEEE Press, 2008. Google Scholar
  18. Uriel Feige. Randomized graph products, chromatic numbers, and the Lovász ϑ-function. Combinatorica, 17(1):79-90, 1997. Preliminary version in STOC'95. Google Scholar
  19. Uriel Feige, Michael Langberg, and Gideon Schechtman. Graphs with tiny vector chromatic numbers and huge chromatic numbers. SIAM J. Comput., 33(6):1338-1368, 2004. Preliminary version in FOCS'02. Google Scholar
  20. Peter Frankl and Vojtěch Rödl. Forbidden intersections. Trans. Amer. Math. Soc., 300(1):259-286, 1987. Google Scholar
  21. Peter Frankl and Richard M. Wilson. Intersection theorems with geometric consequences. Combinatorica, 1(4):357-368, 1981. Google Scholar
  22. Alexander Golovnev, Oded Regev, and Omri Weinstein. The minrank of random graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, pages 46:1-46:13, 2017. Google Scholar
  23. Martin Grötschel, László Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169-197, 1981. Google Scholar
  24. Willem Haemers. On some problems of Lovász concerning the Shannon capacity of a graph. IEEE Trans. Inform. Theory, 25(2):231-232, 1979. Google Scholar
  25. Willem Haemers. An upper bound for the Shannon capacity of a graph. In Algebraic methods in graph theory, Vol. I, II (Szeged, 1978), volume 25 of Colloq. Math. Soc. János Bolyai, pages 267-272. North-Holland, Amsterdam, 1981. Google Scholar
  26. Ishay Haviv and Michael Langberg. On linear index coding for random graphs. In IEEE International Symposium on Information Theory, pages 2231-2235, 2012. Google Scholar
  27. Ishay Haviv and Michael Langberg. H-wise independence. In Innovations in Theoretical Computer Science (ITCS'13), pages 541-552, 2013. Google Scholar
  28. Syed A. Jafar. Topological interference management through index coding. IEEE Transactions on Information Theory, 60(1):529-568, 2014. Google Scholar
  29. Mingyue Ji, Antonia M. Tulino, Jaime Llorca, and Giuseppe Caire. Caching and coded multicasting: Multiple groupcast index coding. In IEEE Global Conference on Signal and Information Processing, pages 881-885, 2014. Google Scholar
  30. Jeff Kahn and Gil Kalai. A counterexample to Borsuk’s conjecture. Bull. Amer. Math. Soc., 29(1):60-62, 1993. Google Scholar
  31. David R. Karger, Rajeev Motwani, and Madhu Sudan. Approximate graph coloring by semidefinite programming. J. ACM, 45(2):246-265, 1998. Preliminary version in FOCS'94. Google Scholar
  32. Donald E. Knuth. The sandwich theorem. Electronic J. Combinatorics, 1:1, 1994. Google Scholar
  33. Michael Langberg and Alexander Sprintson. On the hardness of approximating the network coding capacity. IEEE Transactions on Information Theory, 57(2):1008-1014, 2011. Preliminary version in ISIT'08. Google Scholar
  34. László Lovász. On the Shannon capacity of a graph. IEEE Trans. Inform. Theory, 25(1):1-7, 1979. Google Scholar
  35. Eyal Lubetzky and Uri Stav. Nonlinear index coding outperforming the linear optimum. IEEE Trans. Inform. Theory, 55(8):3544-3551, 2009. Preliminary version in FOCS'07. Google Scholar
  36. Hamed Maleki, Viveck R Cadambe, and Syed A Jafar. Index coding - An interference alignment perspective. IEEE Transactions on Information Theory, 60(9):5402-5432, 2014. Google Scholar
  37. Arya Mazumdar. On a duality between recoverable distributed storage and index coding. In IEEE International Symposium on Information Theory, pages 1977-1981, 2014. Google Scholar
  38. Eran Ofek and Uriel Feige. Random 3CNF formulas elude the Lovász theta function. Electronic Colloquium on Computational Complexity (ECCC), 13(043), 2006. Google Scholar
  39. René Peeters. Orthogonal representations over finite fields and the chromatic number of graphs. Combinatorica, 16(3):417-431, 1996. Google Scholar
  40. 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
  41. Dijen K. Ray-Chaudhuri and Richard M. Wilson. On t-designs. Osaka J. Math., 12(3):737-744, 1975. Google Scholar
  42. Søren Riis. Information flows, graphs and their guessing numbers. Electr. J. Comb., 14(1), 2007. Google Scholar
  43. Claude E. Shannon. The zero error capacity of a noisy channel. Institute of Radio Engineers, Transactions on Information Theory, IT-2:8-19, 1956. Google Scholar
  44. Leslie G. Valiant. Why is Boolean complexity theory difficult? In Poceedings of the London Mathematical Society symposium on Boolean function complexity, volume 169, pages 84-94, 1992. Google Scholar
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 Imprint Privacy Contact