A few years ago, Blais, Brody, and Matulef (2012) presented a methodology for proving lower bounds for property testing problems by reducing them from problems in communication complexity. Recently, Bhrushundi, Chakraborty, and Kulkarni (2014) showed that some reductions of this type can be deconstructed to two separate reductions, from communication complexity to parity decision trees and from the latter to property testing.

We introduce a model called \emph{linear-access algorithms}, which is a generalization of randomized parity decision trees, and show several methods to reduce communication complexity problems to problems for linear-access algorithms and problems for linear-access algorithms to property testing problems. This approach yields a new interpretation for several well-known reductions, since we present these reductions as a composition of two steps with fundamentally different functionalities.

Furthermore, we demonstrate the potential of proving lower bounds on property testing problems by reducing them directly from problems for linear-access algorithms. In particular, we provide an alternative and simple proof for a known lower bound of $\Omega(k)$ queries on testing ``$k$-linearity''; that is, the property of $k$-sparse linear functions over $\mathbb{F}_2$. This alternative proof relies on a theorem by Linial and Samorodnitsky (2002). We then extend this result to a new lower bound of $\Omega(s)$ queries for testing $s$-sparse degree-$d$ polynomials over $\mathbb{F}_2$, for any $d\in\mathbb{N}$. In addition we provide a simple proof for the hardness of testing some families of linear subcodes.

We present an unrelated result in an appendix. In property testing, testers that always accept inputs that are in the property (i.e., testers with one-sided error) are natural and common. We show that the dual notion, testers that always reject inputs that are far from the property, seems to be a notion of limited scope.

Slightly revised the exposition in some places. Mainly, added an alternative title, and made minor changes to the abstract, introduction, and digest.

A few years ago, Blais, Brody, and Matulef (2012) presented a methodology for proving lower bounds for property testing problems by reducing them from problems in communication complexity. Recently, Bhrushundi, Chakraborty, and Kulkarni (2014) showed that some reductions of this type can be deconstructed to two separate reductions, from communication complexity to parity decision trees and from the latter to property testing.

This work follows up on these ideas. We present a method for deconstructing reductions from communication complexity to property testing, using an intermediary model that is a generalization of parity decision trees. This method yields a new interpretation for several well-known reductions, since we present the reductions as a composition of two steps with fundamentally different functionalities.

Furthermore, we show a technique for proving lower bounds directly in the intermediary model, apply this technique to prove several lower bounds for natural problems in the model, and derive corresponding lower bounds in property testing. In particular, we provide an alternative proof for a known $\Omega(k)$ lower bound on testing $k$-sparse linear functions over $\mathbb{F}_2$, relying on a theorem by Linial and Samorodnitsky (2002). We then extend this result to a new lower bound of $\Omega(s)$ for testing $s$-sparse degree-$d$ polynomials over $\mathbb{F}_2$, for any $d\in\mathbb{N}$. In addition we provide a simple proof for the hardness of testing some families of linear subcodes.

We present an unrelated result in an appendix. In property testing, testers that always accept inputs that are in the property (i.e., testers with one-sided error) are natural and common. We show that the dual notion, testers that always reject inputs that are far from the property, seems to be a notion of limited scope.