On the approximation resistance of balanced linear threshold functions

DOI10.1145/3313276.3316374zbMATH Open1433.68160arXiv1807.04421OpenAlexW2963649008MaRDI QIDQ5212784FDOQ5212784

Authors: 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)

Abstract: In this paper, we show that there exists a balanced linear threshold function (LTF) which is unique games hard to approximate, refuting a conjecture of Austrin, Benabbas, and Magen. We also show that the almost monarchy predicate on k variables is approximable for sufficiently large k.

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

Recommendations

• Approximating linear threshold predicates
• Approximating linear threshold predicates
• Improved approximation of linear threshold functions
• Approximation resistant predicates from pairwise independence
• On quadratic threshold CSPs

zbMATH Keywords

constraint satisfaction problemshardness of approximationlinear threshold functions

Mathematics Subject Classification ID

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

Cited In (2)

• Approximating linear threshold predicates
• Approximating linear threshold predicates

This page was built for publication: On the approximation resistance of balanced linear threshold functions

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