Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-074 | 10th September 2009 08:52

A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness


Authors: Suguru Tamaki, Yuichi Yoshida
Publication: 13th September 2009 12:21
Downloads: 4127


Long 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
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$.

ISSN 1433-8092 | Imprint