On the approximation resistance of a random predicate

DOI10.1007/S00037-009-0262-8MaRDI QIDQ626662zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Johan Hastad

Publication date 18 February 2011

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-009-0262-8

zbMATH Keywords

approximation algorithmsapproximation resistanceconstraint satisfaction problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• On the Approximation Resistance of a Random Predicate
• Randomly supported independence and resistance
• Randomly Supported Independence and Resistance
• Approximation resistance on satisfiable instances for predicates with few accepting inputs
• A characterization of strong approximation resistance

Cited in

(10)

• Circumventing d-to-1 for approximation resistance of satisfiable predicates strictly containing parity of width four (extended abstract)
• Circumventing d-to-1 for approximation resistance of satisfiable predicates strictly containing parity of width at least four
• A query efficient non-adaptive long code test with perfect completeness
• On the Approximation Resistance of a Random Predicate
• The Complexity of Somewhat Approximation Resistant Predicates
• A characterization of strong approximation resistance
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Approximation resistance on satisfiable instances for predicates with few accepting inputs
• Approximation resistance on satisfiable instances for predicates with few accepting inputs
• Approximation algorithm for DNF under distributions with limited independence

This page was built for publication: On the approximation resistance of a random predicate

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