An improved test of Boolean functions for k-dimensionality

DOI10.1007/S10559-013-9498-ZzbMATH Open1317.68265OpenAlexW2000455465MaRDI QIDQ465929FDOQ465929

Authors: A. N. Alekseychuk, S. N. Konyushok 

Publication date: 24 October 2014

Published in: Cybernetics and Systems Analysis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10559-013-9498-z

Recommendations

• scientific article; zbMATH DE number 3878850
• The complexity of dynamic tests for functions of k-valued logic
• Tight bounds for testing \(k\)-linearity
• Testing Fourier dimensionality and sparsity
• scientific article; zbMATH DE number 3943711

zbMATH Keywords

probabilistic algorithm\(k\)-dimensional functiontesting property of Boolean functionsWalsh-Hadamard transform.

Mathematics Subject Classification ID

Randomized algorithms (68W20) Boolean functions (06E30)

Cites Work

• Boolean functions in coding theory and cryptography. Translated from the Russian by Svetla Nikova
• Testing Fourier dimensionality and sparsity
• On the resynchronization attack.
• Testing Reed–Muller Codes
• On the propagation criterion for Boolean functions and on bent functions
• Optimal testing of Reed-Muller codes

Cited In (5)

• Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication
• Improved upper bound for the relative distance between a Boolean function and the set of \(k\)-dimensional functions
• Algebraically degenerate approximations of Boolean functions
• Statistical estimation of the structure of a finite population
• A New test for whetherFis "More NBU" thanG

This page was built for publication: An improved test of Boolean functions for \(k\)-dimensionality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q465929)