Randomly supported independence and resistance

DOI10.1145/1536414.1536481MaRDI QIDQ5172743zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Per Austrin, Johan Hastad

Publication date 4 February 2015

Published in Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1536414.1536481

zbMATH Keywords

\(k\)-wise independenceapproximation resistance

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• Randomly Supported Independence and Resistance
• Independence in randomizations
• scientific article; zbMATH DE number 3856078
• scientific article; zbMATH DE number 1979752
• Independence, relative randomness, and PA degrees
• Independence of random variables
• Independence and determination of probabilities
• Independence-domination duality
• scientific article; zbMATH DE number 4067940

Cited in

(4)

• Randomly Supported Independence and Resistance
• On the Approximation Resistance of a Random Predicate
• Approximation resistant predicates from pairwise independence
• On the approximation resistance of a random predicate

This page was built for publication: Randomly supported independence and resistance

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