Approximating the orthogonality dimension of graphs and hypergraphs

DOI10.4230/LIPICS.MFCS.2019.39MaRDI QIDQ5092401zbMATH OpenFDO

Authors Ishay Haviv

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1906.05005

zbMATH Keywords

hardness of approximationKneser and Schrijver graphsorthogonal representations of hypergraphsorthogonality dimensionsemidefinite programming

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Approximating the orthogonality dimension of graphs and hypergraphs
• Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
• The (generalized) orthogonality dimension of (generalized) Kneser graphs: bounds and applications
• The (generalized) orthogonality dimension of (generalized) kneser graphs: bounds and applications
• Local orthogonality dimension

Cites work

• Algebraic approach to promise constraint satisfaction
• An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
• Approximate graph coloring by semidefinite programming
• Approximating coloring and maximum independent sets in 3-uniform hypergraphs
• Coloring -colorable graphs using relatively small palettes
• Coloring 3-colorable graphs with less than \(n^{1/5}\) colors
• Coloring bipartite hypergraphs
• Conditional Hardness for Approximate Coloring
• Extremal problems concerning Kneser-graphs
• Forbidden Intersections
• Hardness of Approximate Hypergraph Coloring
• scientific article; zbMATH DE number 1002208 (Why is no real title available?)
• scientific article; zbMATH DE number 3672329 (Why is no real title available?)
• scientific article; zbMATH DE number 3745081 (Why is no real title available?)
• scientific article; zbMATH DE number 3503283 (Why is no real title available?)
• scientific article; zbMATH DE number 3251317 (Why is no real title available?)
• Improving the performance guarantee for approximate graph coloring
• Kneser's conjecture, chromatic number, and homotopy
• Kochen–Specker Sets and the Rank-1 Quantum Chromatic Number
• Linear index coding via semidefinite programming
• n-tuple colorings and associated graphs
• New approximation algorithms for graph coloring
• New approximation guarantee for chromatic number
• New hardness results for graph and hypergraph colorings
• NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
• On a Fractional Version of Haemers’ Bound
• On the Hardness of 4-Coloring a 3-Colorable Graph
• On the hardness of approximating minimum vertex cover
• On the hardness of approximating the chromatic number
• On the quantum chromatic number of a graph
• On the Shannon capacity of a graph
• Orthogonal representations and connectivity of graphs
• Orthogonal representations over finite fields and the chromatic number of graphs
• Reducibility among combinatorial problems
• Round elimination in exact communication complexity
• The Complexity of Near-Optimal Graph Coloring
• The hardness of 3-uniform hypergraph coloring
• The Minrank of Random Graphs
• The multichromatic numbers of some Kneser graphs
• Topological bounds on the dimension of orthogonal representations of graphs
• Two-query PCP with subconstant error

Cited in

(6)

• The (generalized) orthogonality dimension of (generalized) Kneser graphs: bounds and applications
• Topological bounds for graph representations over any field
• Approximating the orthogonality dimension of graphs and hypergraphs
• Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
• The (generalized) orthogonality dimension of (generalized) kneser graphs: bounds and applications
• Approximating the Orthogonality Dimension of Graphs and Hypergraphs

This page was built for publication: Approximating the orthogonality dimension of graphs and hypergraphs

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