ECCC-Report TR09-074https://eccc.weizmann.ac.il/report/2009/074Comments and Revisions published for TR09-074en-usSun, 13 Sep 2009 12:21:13 +0300
Paper TR09-074
| A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness |
Suguru Tamaki,
Yuichi Yoshida
https://eccc.weizmann.ac.il/report/2009/074Long Code testing is a fundamental problem in the area of property
testing and hardness of approximation.
Long Code is a function of the form $f(x)=x_i$ for some index $i$.
In the Long Code testing, the problem is, given oracle access to a
collection of Boolean functions, to decide whether all the functions
are the same Long Code, or cross-influences of any two functions are
small.
In this paper, we study the following problem:
How small the soundness $s$ of the Long Code test with perfect
completeness can be by using non-adaptive $q$ queries?
We give a Long Code test with $s=(2q+3)/2^q$, where $q$ is of the form
$2^k-1$ for any integer $k>2$.
Our test is a ``noisy'' version of Samorodnitsky-Trevisan's Hyper Graph
linearity test with suitably chosen noise distribution.
To bound the soundness, we use Invariance-Principle style analysis
in the spirit of O'Donnell and Wu (STOC 2009).
Previously, H\r{a}stad and Khot (Theory of Computing, 2005) have shown
$s=2^{4\sqrt{q}}/2^q$ for infinitely many $q$.
Chen (RANDOM 2009) has improved this to $s=q^3/2^q$ for infinitely many
$q$ with ``adaptive'' queries.
As for the Long Code test with ``almost'' perfect completeness,
Trevisan and Samorodnitsky (SICOMP, 2009) have shown
$s=2q/2^q$ (or even $(q+1)/2^q$ for infinitely many $q$).
Austrin and Mossel (Computational Complexity) have improved this to
$s=(q+o(q))/2^q$ (or even $(q+4)/2^q$ assuming the famous Hadamard
Conjecture) for any $q$.Sun, 13 Sep 2009 12:21:13 +0300https://eccc.weizmann.ac.il/report/2009/074