scientific article; zbMATH DE number 7639160

DOI10.4086/CJTCS.2022.002OpenAlexW4365130787MaRDI QIDQ5870293FDOQ5870293

Authors: Ishay Haviv 

Publication date: 6 January 2023

Published in: Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/cjtcs.2022.002

Title of this publication is not available (Why is that?)

zbMATH Keywords

semidefinite programminghardness of approximationorthogonality dimensionKneser and Schrijver graphsorthogonal representations of hypergraphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Reducibility among Combinatorial Problems
• On the quantum chromatic number of a graph
• Forbidden Intersections
• Approximate graph coloring by semidefinite programming
• On the Shannon capacity of a graph
• Kochen–Specker Sets and the Rank-1 Quantum Chromatic Number
• Proof verification and the hardness of approximation problems
• Probabilistic checking of proofs
• Title not available (Why is that?)
• Kneser's conjecture, chromatic number, and homotopy
• On the hardness of approximating minimum vertex cover
• Title not available (Why is that?)
• Conditional Hardness for Approximate Coloring
• Title not available (Why is that?)
• An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
• Improving the performance guarantee for approximate graph coloring
• New approximation algorithms for graph coloring
• n-tuple colorings and associated graphs
• A Parallel Repetition Theorem
• The multichromatic numbers of some Kneser graphs
• New approximation guarantee for chromatic number
• Extremal problems concerning Kneser-graphs
• Orthogonal representations and connectivity of graphs
• The Complexity of Near-Optimal Graph Coloring
• Approximating coloring and maximum independent sets in 3-uniform hypergraphs
• Orthogonal representations over finite fields and the chromatic number of graphs
• Two-query PCP with subconstant error
• New hardness results for graph and hypergraph colorings
• Coloring -colorable graphs using relatively small palettes
• The hardness of 3-uniform hypergraph coloring
• Topological bounds on the dimension of orthogonal representations of graphs
• Title not available (Why is that?)
• Coloring bipartite hypergraphs
• Hardness of Approximate Hypergraph Coloring
• On the hardness of approximating the chromatic number
• The Minrank of Random Graphs
• On the Hardness of 4-Coloring a 3-Colorable Graph
• Coloring 3-Colorable Graphs with Less than n ^1/5 Colors
• Title not available (Why is that?)
• Improved hardness for H-colourings of G-colourable graphs
• Algebraic Approach to Promise Constraint Satisfaction
• On a Fractional Version of Haemers’ Bound
• Graphs and Geometry
• The (generalized) orthogonality dimension of (generalized) kneser graphs: bounds and applications
• Topological Bounds for Graph Representations over Any Field
• Title not available (Why is that?)
• Linear index coding via semidefinite programming
• Title not available (Why is that?)

Cited In (4)

• The (generalized) orthogonality dimension of (generalized) kneser graphs: bounds and applications
• A correction: Orthogonal representations and connectivity of graphs
• Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
• Local orthogonality dimension

This page was built for publication:

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