scientific article; zbMATH DE number 7640716

DOI10.4086/toc.2022.v018a022OpenAlexW4313317676MaRDI QIDQ5060749

Ishay Haviv, Alexander Golovnev

Publication date: 11 January 2023

Published in: Theory of Computing (Search for Journal in Brave)

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

circuit complexityhardness of approximationKneser graphsminrankorthogonality dimension

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Theory of computing (68Qxx) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (2)

Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank ⋮ Local orthogonality dimension

Cites Work

• The gap between monotone and non-monotone circuit complexity is exponential
• Improved hardness for H-colourings of G-colourable graphs
• Unnamed Item

This page was built for publication: