# News for May 2016

Last month witnessed two new property testing papers go online, which May be of interest to the community.

Reducing testing affine spaces to testing linearity, by Oded Goldreich (ECCC). In his recent guest post, the author outlined a reduction between testing if a Boolean function is an $$(n-k)$$-dimensional affine subspace of $$\{0,1\}^n$$, and testing linearity of functions $$f\colon\{0,1\}^n\to \{0,1\}$$. This preprint encompasses details of this reduction, as part as a general approach to testing monomials (resolving along the way one of the open problems from April). Namely, it shows that testing if $$f$$ is a $$k$$-monomial can be reduced to testing two properties, of $$f$$ and of a (related) function $$g\colon\{0,1\}^n\to \{0,1\}^k$$. Moreover, it establishes that the general case ($$k\geq 1$$) of the second part  can itself be reduced to the simpler case ($$k=1$$), giving a unified argument.

Testing Equality in Communication Graphs, by Noga Alon, Klim Efremenko, Benny Sudakov (ECCC). Given a connected graph on $$k$$ nodes, where each node has an $$n$$-bit string, how many bits of communication are needed to test if all strings are equal? This paper investigates this problem for many interesting graphs, resolving the complexity up to lower order terms. For example, if the graph is Hamiltonian, they show that $$\frac{kn}{2} + o(n)$$ bits are sufficient, while at least $$\frac{kn}{2}$$ bits are required.

Edit (06/16): updated the description of the first preprint, which was not entirely accurate.

# Call for feedback: upcoming “Introduction to Property Testing”

Forwarding an announcement by Oded Goldreich:

I would like to seek the help of this community regarding my forthcoming book Introduction to Property Testing (see http://www.wisdom.weizmann.ac.il/~oded/pt-intro.html). Specifically, I would be grateful for feedback regarding any aspect and part of the current text, although detailed comments are likely to be more helpful at this time than suggestions for drastic and/or structural changes. Please do not shy from indicating relevant works that may be mentioned (rather than described in detail), since it is quite possible that I was not aware of them or forgot to mention them (rather than chose not to include a detailed description due to various considerations).

Since I am likely to continue revising the text and posting the revisions on the website, please indicate the text-locations to which you refer in a manner that is most robust to revision (e.g., indicate relative location with respect to sectioning and/or theorem-environment numbers rather than with respect to page numbers).

# Open problem for April 2016

As open problems of the month, we state here the two questions discussed in our recent guest post by Oded Goldreich:

Open Problem 1 (obtaining a one-sided error reduction): The reduction from testing affinity of a subspace to that of testing affinity of a function has two-sided error probability. We wonder whether a one-sided error reduction of similar complexity can be found.

Note that this will yield a one-sided error tester for affinity, which we believe is not known. Actually, we would also welcome a two-sided error reduction that, when combined with the linearity tester, yields a tester of complexity $$O(1/\epsilon)$$ rather than $$\tilde{O}(1/\epsilon)$$.

Turning to the task of testing monomials, we recall that the solution of [PRS02] is based on employing self-correction to the following test that refers to the case that $$H=\{x:AX=b\}$$ is an $$(\ell-k)$$-dimensional affine space. Basically, the test selects a random $$x\in H$$ and a random $$y\in\{0,1\}^\ell$$, and checks whether it holds that $$y\in H$$ if and only if $$x\wedge y \in H$$, where $$\wedge$$ denotes the bit-by-bit product of vectors. It is painfully shown in [5] that if $$H$$ is not a translation by $$1^\ell$$ of an axis-aligned linear space, then the check fails with probability $$\Omega(2^{-k})$$. Furthermore, it is shown that for a constant fraction of the $$x$$’s (in $$H$$), the check fails on a $$\Omega(2^{-k})$$ fraction of the $$y$$’s (in $$\{0,1\}^\ell$$). This strengthening is important, since selecting $$x\in H$$ uniformly requires $$\Theta(2^k)$$ trials. Recall that proving the foregoing assertion for $$k=1$$ is quite easy (cf. [5]), which leads us to ask

Open Problem 2 (can a simpler proof be found for the case of $$k>1$$): Is there a relatively simple reduction of the foregoing claim for general $$k$$ to the special case of $$k=1$$?

[PRS02] M. Parnas, D. Ron, and A. Samorodnitsky. Testing Basic Boolean Formulae. SIAM Journal on Disc. Math. and Alg., Vol. 16 (1), pages 20–46, 2002.

# Guest Post: Oded Goldreich, “Reducing testing affine spaces to testing linearity”

[We are delighted to have this month a blog post by Oded Goldreich, on a reduction from testing affinity of subspaces to testing linearity of Boolean functions. Oded also gave us open problems directly related to this post.]

We consider the task of testing whether a Boolean function $$f\colon \{0,1\}^\ell\to\{0,1\}$$ is the indicator function of an $$(\ell-k)$$-dimensional space. An optimal tester for this property was presented by Parnas, Ron, and Samorodnitsky (SIDMA, 2002), by mimicking the celebrated linearity tester (of Blum, Luby and Rubinfeld, JCSS, 1993) and its analysis. We show that this task can be reduced to testing the linearity of a related function $$g\colon\{0,1\}^\ell\to\{0,1\}^k$$, yielding an almost optimal tester.

# News for March 2016

While March 2016 has been rather low in terms of property testing, we did see a new paper appear:

A Note on Tolerant Testing with One-Sided Error, by Roei Tell (ECCC). A natural generalization of property testing is that of tolerant testing, as introduced by Parnas, Ron, and Rubinfeld [PRR06]: where the tester still must reject all objects that are far from satisfying the property, but now also has to accept those that are sufficiently close (all that with constant probability). In this work is considered the question of one-sidedness of tolerant testers: namely, is it possible to only err on the farness side, but accept close output with probability one? As it turns out, it is not — the author shows that any such one-sided tolerant tester, for basically any property of interest, must essentially query the whole input…

Universal Locally Testable Codes, by Oded Goldreich and Tom Gur (ECCC). In this work, the authors introduce and initiate the study of an extension of locally testable codes they name universal locally testable codes (universal-LTC). At a high-level, a universal-LTC (with regard to a family of functions $$\cal F$$) is a locally testable code $$C$$ “for which the restrictions (subcodes) of $$C$$ by functions in $$\cal F$$ are also locally testable.” In other terms, one is then able to test efficiently, given an encoded string $$w$$, if (i) $$w=C(x)$$ for some $$x$$; but also, for any $$f\in \cal F$$, if (ii) $$w=C(x)$$ for some $$x$$ that satisfies $$f(x)=1$$.

Edit (04/06): added the work of Goldreich and Gur, which was overlooked in our first version of the article.