On the approximation resistance of balanced linear threshold functions

DOI10.1145/3313276.3316374MaRDI QIDQ5212784zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cited in

(4)

• Approximating linear threshold predicates
• Approximating linear threshold predicates
• On the mysteries of MAX NAE-SAT
• Sketching approximability of all finite CSPs

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)