On the Approximation Resistance of a Random Predicate

DOI10.1007/978-3-540-74208-1_11MaRDI QIDQ3603462zbMATH OpenOpenAlexFDO

Authors Johan Hastad

Publication date 17 February 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74208-1_11

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• On the approximation resistance of a random predicate
• Randomly supported independence and resistance
• Randomly Supported Independence and Resistance
• Approximation resistant predicates from pairwise independence
• A characterization of strong approximation resistance

Cited in

(3)

• The Complexity of Somewhat Approximation Resistant Predicates
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• On the approximation resistance of a random predicate

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 Q3603462)