A.N. Alekseychuk, S.N. Konyushok

UDC 621.391:519.2

An improved test of Boolean functions for -dimensionality / Alekseychuk A.N., Konyushok S. N. // Cybernetika i sistemny analiz.

A probabilistic test of Boolean functions for k-dimensionality is constructed. The test has a less time complexity and a smaller first kind error probability (with the same upper bound for the second kind error probability) in comparison with a well-known previously proposed test.

Refs: 9 titles.

Keywords:

testing property of Boolean functions, probabilistic algorithm, k-dimensional function, Walsh–Hadamard transform.

Author Affiliations

Institute of Special Communications and Information Protection, National Technical University of Ukraine "Kyiv Polytechnic Institute", Kyiv, Ukraine