[1]   Josh Alman and R. Ryan Williams: Probabilistic rank and matrix rigidity. In Proc. 49th STOC, pp. 641–652. ACM Press, 2017. [doi:10.1145/3055399.3055484]

[2]   Noga Alon: The Shannon capacity of a union. Combinatorica, 18(3):301–310, 1998. [doi:10.1007/PL00009824]

[3]   Noga Alon and Nabil Kahale: Approximating the independence number via the ϑ-function. Math. Programming, 80(3):253–264, 1998. [doi:10.1007/BF01581168]

[4]   László Babai and Péter Frankl: Linear Algebra Methods in Combinatorics. Unpublished manuscript, 2.2 edition, 1992–2022. Available at author’s website.

[5]   Libor Barto, Jakub Bulín, Andrei A. Krokhin, and Jakub Opršal: Algebraic approach to promise constraint satisfaction. J. ACM, 68(4):28:1–66, 2021. Preliminary version in STOC’19. [doi:10.1145/3457606]

[6]   Jop Briët, Harry Buhrman, Debbie Leung, Teresa Piovesan, and Florian Speelman: Round elimination in exact communication complexity. In Proc. 10th Conf. Theory of Quantum Computation, Communication and Cryptography (TQC’15), volume 44 of LIPIcs, pp. 206–225, 2015. [doi:10.4230/LIPIcs.TQC.2015.206]

[7]   Jop Briët and Jeroen Zuiddam: On the orthogonal rank of Cayley graphs and impossibility of quantum round elimination. Quantum Inf. Comput., 17(1–2):106–116, 2017. ACM DL.

[8]   Boris Bukh and Christopher Cox: On a fractional version of Haemers’ bound. IEEE Trans. Inform. Theory, 65(6):3340–3348, 2019. [doi:10.1109/TIT.2018.2889108]

[9]   Chris Calabro: A lower bound on the size of series-parallel graphs dense in long paths. Electron. Colloq. Comput. Complexity, TR08-110, 2008. [ECCC]

[10]   Peter J. Cameron, Ashley Montanaro, Michael W. Newman, Simone Severini, and Andreas J. Winter: On the quantum chromatic number of a graph. Electr. J. Combinat., 14(1):R81:1–15, 2007. [doi:10.37236/999]

[11]   Eden Chlamtáč and Ishay Haviv: Linear index coding via semidefinite programming. Combin. Probab. Comput., 23(2):223–247, 2014. Preliminary version in SODA’12. [doi:10.1017/S0963548313000564]

[12]   Vašek Chvátal, Michael R. Garey, and David S. Johnson: Two results concerning multicoloring. Ann. Discr. Math., 2:151–154, 1978. [doi:10.1016/S0167-5060(08)70329-7]

[13]   Bruno Codenotti, Pavel Pudlák, and Giovanni Resta: Some structural properties of low-rank matrices related to computational complexity. Theoret. Comput. Sci., 235(1):89–107, 2000. [doi:10.1016/S0304-3975(99)00185-1, ECCC:TR97-043]

[14]   Ronald de Wolf: Quantum Computing and Communication Complexity. Ph. D. thesis, Universiteit van Amsterdam, 2001. Available at author’s home page.

[15]   Tristan Denley: The odd girth of the generalised Kneser graph. Europ. J. Combinat., 18(6):607–611, 1997. [doi:10.1006/eujc.1996.0122]

[16]   Irit Dinur, Elchanan Mossel, and Oded Regev: Conditional hardness for approximate coloring. SIAM J. Comput., 39(3):843–873, 2009. Preliminary version in STOC’06. [doi:10.1137/07068062X]

[17]   Zeev Dvir and Benjamin L. Edelman: Matrix rigidity and the Croot-Lev-Pach lemma. Theory of Computing, 15(8):1–7, 2019. [doi:10.4086/toc.2019.v015a008]

[18]   Zeev Dvir and Allen Liu: Fourier and circulant matrices are not rigid. Theory of Computing, 16(20):1–48, 2020. Preliminary version in CCC’19. [doi:10.4086/toc.2020.v016a020]

[19]   Uriel Feige: Randomized graph products, chromatic numbers, and the Lovász ϑ-function. Combinatorica, 17(1):79–90, 1997. Preliminary version in STOC’95. [doi:10.1007/BF01196133]

[20]   Michael R. Garey and David S. Johnson: The complexity of near-optimal graph coloring. J. ACM, 23(1):43–49, 1976. [doi:10.1145/321921.321926]

[21]   Alexander Golovnev and Ishay Haviv: The (generalized) orthogonality dimension of (generalized) Kneser graphs: Bounds and applications. In Proc. 36th Comput. Complexity Conf. (CCC’21), pp. 8:1–15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2021. [doi:10.4230/LIPIcs.CCC.2021.8]

[22]   Alexander Golovnev, Oded Regev, and Omri Weinstein: The minrank of random graphs. IEEE Trans. Inform. Theory, 64(11):6990–6995, 2018. Preliminary version in RANDOM’17. [doi:10.1109/TIT.2018.2810384]

[23]   Willem H. Haemers: On some problems of Lovász concerning the Shannon capacity of a graph. IEEE Trans. Inform. Theory, 25(2):231–232, 1979. [doi:10.1109/TIT.1979.1056027]

[24]   Willem H. Haemers: An upper bound for the Shannon capacity of a graph. In László Lovász and Vera T. Sós, editors, Algebraic Methods in Graph Theory, Szeged, 1978, volume 25/I of Colloquia Mathematica Societatis János Bolyai, pp. 267–272. Bolyai Society and North-Holland, 1981. Avaliable at Tilburg University.

[25]   Ishay Haviv: On minrank and the Lovász theta function. In Proc. 21st Internat. Conf. on Approximation Algorithms for Combinat. Opt. Probl. (APPROX’18), pp. 13:1–15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.APPROX-RANDOM.2018.13]

[26]   Ishay Haviv: Approximating the orthogonality dimension of graphs and hypergraphs. In Proc. Internat. Symp. Math. Foundations of Comp. Sci. (MFCS’19), pp. 39:1–15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.MFCS.2019.39]

[27]   Ishay Haviv: On minrank and forbidden subgraphs. ACM Trans. Comput. Theory, 11(4):20:1–13, 2019. Preliminary version in RANDOM’18. [doi:10.1145/3322817]

[28]   Ishay Haviv: Topological bounds on the dimension of orthogonal representations of graphs. Europ. J. Combinat., 81:84–97, 2019. [doi:10.1016/j.ejc.2019.04.006]

[29]   Sihuang Hu, Itzhak Tamo, and Ofer Shayevitz: A bound on the Shannon capacity via a linear programming variation. SIAM J. Discr. Math., 32(3):2229–2241, 2018. Preliminary version in ISIT’17. [doi:10.1137/17M115565X]

[30]   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. [doi:10.1145/274787.274791]

[31]   Donald E. Knuth: The sandwich theorem. Electr. J. Combinat., 1(1):A1:1–48, 1994. [doi:10.37236/1193]

[32]   Michael Langberg and Alexander Sprintson: On the hardness of approximating the network coding capacity. IEEE Trans. Inform. Theory, 57(2):1008–1014, 2011. Preliminary version in ISIT’08. [doi:10.1109/TIT.2010.2094910]

[33]   Abraham Lempel: Matrix factorization over GF(2) and trace-orthogonal bases of GF(2ⁿ). SIAM J. Comput., 4(2):175–186, 1975. [doi:10.1137/0204014]

[34]   László Lovász: Kneser’s conjecture, chromatic number, and homotopy. J. Combin. Theory–A, 25(3):319–324, 1978. [doi:10.1016/0097-3165(78)90022-5]

[35]   László Lovász: On the Shannon capacity of a graph. IEEE Trans. Inform. Theory, 25(1):1–7, 1979. [doi:10.1109/TIT.1979.1055985]

[36]   László Lovász: Graphs and Geometry. Volume 65 of Colloquium Publications. Amer. Math. Soc., 2019. [doi:10.1090/coll/065]

[37]   László Lovász, Michael Saks, and Alexander Schrijver: Orthogonal representations and connectivity of graphs. Lin. Alg. Appl., 114–115:439–454, 1989. Special Issue Dedicated to Alan J. Hoffman. [doi:10.1016/0024-3795(89)90475-8]

[38]   Laura Mančinska and David E. Roberson: Quantum homomorphisms. J. Combin. Theory–B, 118:228–267, 2016. [doi:10.1016/j.jctb.2015.12.009]

[39]   René Peeters: Orthogonal representations over finite fields and the chromatic number of graphs. Combinatorica, 16(3):417–431, 1996. [doi:10.1007/BF01261326]

[40]   Søren Riis: Information flows, graphs and their guessing numbers. Electr. J. Combinat., 14(1):R44:1–17, 2007. Preliminary version in WiOpt’06. [doi:10.37236/962]

[41]   Moshe Rosenfeld: Almost orthogonal lines in E^d. In Bernd Sturmfels and Peter Gritzmann, editors, Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, volume 4 of DIMACS Ser. in Discr. Math., pp. 489–492. 1991. [doi:10.1090/dimacs/004]

[42]   Giannicola Scarpa and Simone Severini: Kochen-Specker sets and the rank-1 quantum chromatic number. IEEE Trans. Inform. Theory, 58(4):2524–2529, 2012. [doi:10.1109/TIT.2011.2178018]

[43]   Saul Stahl: n-tuple colorings and associated graphs. J. Combin. Theory–B, 20(2):185–203, 1976. [doi:10.1016/0095-8956(76)90010-1]

[44]   Saul Stahl: The multichromatic numbers of some Kneser graphs. Discr. Math., 185(1–3):287–291, 1998. [doi:10.1016/S0012-365X(97)00211-2]

[45]   Claude Tardif and Xuding Zhu: A note on Hedetniemi’s conjecture, Stahl’s conjecture and the Poljak-Rödl function. Electr. J. Combinat., 26(4):P4.32:1–5, 2019. [doi:10.37236/8787]

[46]   Éva Tardos: The gap between monotone and non-monotone circuit complexity is exponential. Combinatorica, 8(1):141–142, 1988. [doi:10.1007/BF02122563]

[47]   Leslie G. Valiant: Graph-theoretic arguments in low-level complexity. In Proc. Internat. Symp. Math. Foundations of Comp. Sci. (MFCS’77), pp. 162–176. Springer, 1977. [doi:10.1007/3-540-08353-7_135]

[48]   Marcin Wrochna and Stanislav Živný: Improved hardness for H-colourings of G-colourable graphs. In Proc. 31st Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’20), pp. 1426–1435. SIAM, 2020. ACM DL.

[49]   David Zuckerman: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3(6):103–128, 2007. Preliminary version in STOC’06. [doi:10.4086/toc.2007.v003a006]