On the approximation resistance of balanced linear threshold functions

DOI10.1145/3313276.3316374zbMath1433.68160arXiv1807.04421OpenAlexW2963649008MaRDI QIDQ5212784

Aaron Potechin

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

constraint satisfaction problemslinear threshold functionshardness of approximation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)