Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR13-142 | 24th February 2014 18:02

Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees

RSS-Feed




Revision #2
Authors: Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni
Accepted on: 24th February 2014 18:02
Downloads: 866
Keywords: 


Abstract:

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 {\em parity decision trees}.

The observation allows us to characterize testable properties of linear functions in terms of the approximate $l_1$ norm of the Fourier spectrum of an associated function. It also allows us to reprove the $\Omega(k)$ lower bound for testing $k$-linearity due to Blais et al. More interestingly, it rekindles the hope of closing the gap of $\Omega(k)$ vs $O(k\log k)$ for testing $k$-linearity by analyzing the randomized parity decision tree complexity of a fairly simple function called $E_k$ that evaluates to $1$ if and only if the number of $1$s in the input is exactly $k$. The approach of Blais et al. using communication complexity is unlikely to give anything better than $\Omega(k)$ as a lower bound.

In the case of quadratic functions, we prove an adaptive two-sided $\Omega(n^2)$ lower bound for testing affine isomorphism to the inner product function. We remark that this bound is tight and furnishes an example of a function for which the trivial algorithm for testing affine isomorphism is the best possible. As a corollary, we obtain an $\Omega(n^2)$ lower bound for testing the class of {\em Bent} functions.

We believe that our techniques might be of independent interest and may be useful in proving other testing bounds.



Changes to previous version:

Revision meant as a full version to the conference version to appear in the proceedings of the 9th International Computer Science Symposium in Russia (CSR 2014).


Revision #1 to TR13-142 | 11th October 2013 17:23

Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees





Revision #1
Authors: Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni
Accepted on: 11th October 2013 17:23
Downloads: 1724
Keywords: 


Abstract:

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 the complexity in another model of computation called parity decision trees.

The observation allows us to characterize the testable properties of linear functions in terms of the approximate $l_1$ norm of the Fourier spectrum of an associated function. It also allows us to reprove the $\Omega(k)$ lower bound for testing $k$-linearity due to Blais et al. More interestingly, it rekindles the hope of closing the gap of $\Omega(k)$ vs $O(k\log k)$ for testing $k$-linearity by analyzing the randomized parity decision tree complexity of a fairly simple function called $E_k$ that evaluates to $1$ if and only if the number of $1$s in the input is exactly $k$. The approach of Blais et al. using communication complexity fails to give anything better than $\Omega(k)$ as a lower bound.

In the case of quadratic functions, we prove an adaptive, two-sided $\Omega(n^2)$ lower bound for testing affine isomorphism to the inner product function. We remark that this bound is tight and furnishes an example of a function for which the trivial algorithm for testing affine isomorphism is the best possible. As a corollary, we obtain an $\Omega(n^2)$ lower bound for testing the class of Bent functions.

We believe that our techniques might be of independent interest and may be useful in proving other testing bounds.



Changes to previous version:

Modified proof in Appendix C.2


Paper:

TR13-142 | 11th October 2013 12:52

Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees





TR13-142
Authors: Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni
Publication: 11th October 2013 14:09
Downloads: 2042
Keywords: 


Abstract:

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 the complexity in another model of computation called parity decision trees.

The observation allows us to characterize the testable properties of linear functions in terms of the approximate $l_1$ norm of the Fourier spectrum of an associated function. It also allows us to reprove the $\Omega(k)$ lower bound for testing $k$-linearity due to Blais et al. More interestingly, it rekindles the hope of closing the gap of $\Omega(k)$ vs $O(k\log k)$ for testing $k$-linearity by analyzing the randomized parity decision tree complexity of a fairly simple function called $E_k$ that evaluates to $1$ if and only if the number of $1$s in the input is exactly $k$. The approach of Blais et al. using communication complexity fails to give anything better than $\Omega(k)$ as a lower bound.

In the case of quadratic functions, we prove an adaptive, two-sided $\Omega(n^2)$ lower bound for testing affine isomorphism to the inner product function. We remark that this bound is tight and furnishes an example of a function for which the trivial algorithm for testing affine isomorphism is the best possible. As a corollary, we obtain an $\Omega(n^2)$ lower bound for testing the class of Bent functions.

We believe that our techniques might be of independent interest and may be useful in proving other testing bounds.



ISSN 1433-8092 | Imprint