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

zbMATH Open1422.68131MaRDI QIDQ4633845FDOQ4633845

Authors: Ryan O'Donnell, Yi Wu 

Publication date: 6 May 2019

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

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

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)

Cited In (2)

• Title not available (Why is that?)
• 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)