On the approximation resistance of a random predicate

DOI10.1007/S00037-009-0262-8zbMATH Open1213.68706DBLPjournals/cc/Hastad09OpenAlexW2162784288WikidataQ56958874 ScholiaQ56958874MaRDI QIDQ626662FDOQ626662

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

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

zbMATH Keywords

approximation algorithmsconstraint satisfaction problemapproximation resistance

Mathematics Subject Classification ID

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

Cited In (10)

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