Mathematics – Combinatorics
Scientific paper
2008-11-12
Mathematics
Combinatorics
Some minor corrections
Scientific paper
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\geq3$ queries and has amortized query complexity $1+O(\frac{\log q}{q})$ 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(\frac{\log q}{q})$.
No associations
LandOfFree
A Hypergraph Dictatorship Test with Perfect Completeness does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Hypergraph Dictatorship Test with Perfect Completeness, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Hypergraph Dictatorship Test with Perfect Completeness will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-434212