Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees.
Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni · 2013
In this paper, we study linear and quadratic Boolean functions in the context of property testing. We do this by observing that the query complexity of testing properties of linear and quadratic functions can be characterized in terms of complexity in another model of computation called parity decision trees.