3-bit dictator testing: 1 vs. 5/8

MaRDI QIDQ4633845zbMATH OpenFDO

Authors Ryan O'Donnell, Yi Wu

Publication date 6 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=1496811

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Conditional hardness for satisfiable 3-CSPs
• The Nonapproximability of Non-Boolean Predicates
• scientific article; zbMATH DE number 1833417
• Approximating satisfiable satisfiability problems
• An improved dictatorship test with perfect completeness

Cited in

(2)

• scientific article; zbMATH DE number 7716602 (Why is no real title available?)
• An improved dictatorship test with perfect completeness

This page was built for publication: 3-bit dictator testing: 1 vs. 5/8

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