Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
A Hypergraph Dictatorship Test with Perfect Completeness
verfasst von : Victor Chen
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A hypergraph dictatorship test is first introduced by Samorodnitsky and Trevisan and serves as a key component in their unique games based PCP construction. Such a test has oracle access to a collection of functions and determines whether all the functions are the same dictatorship, or all their low degree influences are
o
(1). Their test makes
q
≥ 3 queries, has amortized query complexity
$1+O\left(\frac{\log q}{q}\right)$
, but has an inherent loss of perfect completeness. In this paper we give an (adaptive) hypergraph dictatorship test that achieves both perfect completeness and amortized query complexity
$1+O\left(\frac{\log q}{q}\right)$
.