__
Revision #1 to TR08-098 | 11th April 2009 00:00
__
#### A Hypergraph Dictatorship Test with Perfect Completeness

**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 $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})$.

__
TR08-098 | 12th November 2008 00:00
__

#### A Hypergraph Dictatorship Test with Perfect Completeness

**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 $q\geq3$ queries

and has amortized query complexity $1+O\left(\frac{\log q}{q}\right)$

but has an inherent loss of perfect completeness. In this note, we

give another hypergraph dictatorship test that achieves both perfect

completeness and amortized query complexity $1+O\left(\frac{\log q}{q}\right)$.