STACS 2005
From MaRDI portal
Publication:5710674
DOI10.1007/b106485zbMath1118.68499OpenAlexW4230940848MaRDI QIDQ5710674
Jonas Holmerin, Lars Engebretsen
Publication date: 2 December 2005
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/b106485
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Query-Efficient Dictatorship Testing with Perfect Completeness ⋮ More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP