On the Approximability of Presidential Type Predicates

DOI10.4230/lipics.approx/random.2020.58arXiv1907.04451OpenAlexW3081989770MaRDI QIDQ6058187

Neng Huang, Aaron Potechin

Publication date: 31 October 2023

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

zbMATH Keywords

approximation algorithmsconstraint satisfaction problemspresidential type predicates

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Approximation resistant predicates from pairwise independence
• On the usefulness of predicates
• A characterization of approximation resistance for even k-partite CSPs
• Randomly Supported Independence and Resistance
• Approximation Resistance from Pairwise-Independent Subgroups
• On Quadratic Threshold CSPs
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Some optimal inapproximability results

This page was built for publication: On the Approximability of Presidential Type Predicates