A Hypergraph Dictatorship Test with Perfect Completeness

DOI10.1007/978-3-642-03685-9_34MaRDI QIDQ3638897zbMATH OpenOpenAlexFDO

Authors Victor Chen

Publication date 28 October 2009

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

Full work available at URL https://arxiv.org/abs/0811.1922

zbMATH Keywords

Fourier analysisGowers normPCPproperty testing

Mathematics Subject Classification ID

Hypergraphs (05C65) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)

Abstract: 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 $qgeq3$ queries and has amortized query complexity $1+O(fraclogqq)$ 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(fraclogqq)$.

Recommendations

• Query-efficient dictatorship testing with perfect completeness
• An improved dictatorship test with perfect completeness
• Towards an optimal query efficient PCP?
• A query efficient non-adaptive long code test with perfect completeness
• A query efficient non-adaptive long code test with perfect completeness

Cited in

(2)

• Query-efficient dictatorship testing with perfect completeness
• An improved dictatorship test with perfect completeness

This page was built for publication: A Hypergraph Dictatorship Test with Perfect Completeness

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