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
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.
Joint work with Tamaki Suguru.
