TR09-074 Authors: Suguru Tamaki, Yuichi Yoshida

Publication: 13th September 2009 12:21

Downloads: 1796

Keywords:

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