ECCC-Report TR08-098https://eccc.weizmann.ac.il/report/2008/098Comments and Revisions published for TR08-098en-usSat, 11 Apr 2009 00:00:00 +0300
Revision 1
| A Hypergraph Dictatorship Test with Perfect Completeness |
Victor Chen
https://eccc.weizmann.ac.il/report/2008/098#revision1A 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})$.
Sat, 11 Apr 2009 00:00:00 +0300https://eccc.weizmann.ac.il/report/2008/098#revision1
Paper TR08-098
| A Hypergraph Dictatorship Test with Perfect Completeness |
Victor Chen
https://eccc.weizmann.ac.il/report/2008/098A 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)$.
Fri, 14 Nov 2008 16:34:16 +0200https://eccc.weizmann.ac.il/report/2008/098