Boolean functions with small spectral norm

被引：18

作者：

Green, Ben ^{[1
]}

Sanders, Tom ^{[1
]}

机构：

[1] Univ Cambridge, Dept Pure Math & Math Stat, Cambridge CB3 0WA, England

来源：

GEOMETRIC AND FUNCTIONAL ANALYSIS | 2008年 / 18卷 / 01期

关键词：

Fourier transform; spectral norm; L-1-norm; boolean functions; structure theorem;

D O I：

10.1007/s00039-008-0654-y

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let f : F-2(n) ->{0, 1} be a boolean function, and suppose that the spectral norm parallel to f parallel to(A) := Sigma(r) vertical bar(f) over cap (r)vertical bar of f is at most M. Then [GRAPHICS] where L <= 2(2CM4) and each H-j is a subgroup of F-2(n). This result may be regarded as a quantitative analogue of the Cohen Helson - Rudin structure theorem for idempotent measures in locally compact abelian groups.

引用

页码：144 / 162

页数：19

共 50 条

[41] Submodular goal value of Boolean functions
Bach, Eric
Dusart, Jeremie
Hellerstein, Lisa
Kletenik, Devorah
DISCRETE APPLIED MATHEMATICS, 2018, 238 : 1 - 13
[42] Nonlinearity of Boolean functions and hyperelliptic curves
Cheon, JH
Chee, S
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2003, 16 (03) : 354 - 365
[43] Reversible circuit realizations of Boolean functions
Brodsky, A
EXPLORING NEW FRONTIERS OF THEORETICAL INFORMATICS, 2004, 155 : 67 - 80
[44] Analysis of affinely equivalent Boolean functions
QingShu Meng
HuanGuo Zhang
Min Yang
ZhangYi Wang
Science in China Series F: Information Sciences, 2007, 50 : 299 - 306
[45] On a conjecture for balanced symmetric Boolean functions
Cusick, Thomas W.
Li, Yuan
Stanica, Pantelimon
JOURNAL OF MATHEMATICAL CRYPTOLOGY, 2009, 3 (04) : 273 - 290
[46] On the Fourier spectrum of functions on Boolean cubes
Andreas Defant
Mieczysław Mastyło
Antonio Pérez
Mathematische Annalen, 2019, 374 : 653 - 680
[47] On higher order nonlinearities of Boolean functions
Tiwari, Sampada
Sharma, Deepmala
CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES, 2023, 15 (04): : 821 - 830
[48] On Boolean functions with several flat spectra
Gaofei Wu
Matthew Geoffrey Parker
Cryptography and Communications, 2019, 11 : 853 - 880
[49] On higher order nonlinearities of Boolean functions
Sampada Tiwari
Deepmala Sharma
Cryptography and Communications, 2023, 15 : 821 - 830
[50] MATRIX REPRESENTATIONS OF BOOLEAN FUNCTIONS AND THEIR APPLICATION
Kuzmin, O., V
Gainulin, N. A.
ADVANCES AND APPLICATIONS IN DISCRETE MATHEMATICS, 2020, 25 (01): : 99 - 111

← 1 2 3 4 5 →