On the complexity of balanced Boolean functions

被引：5
|
作者：
Bernasconi, A [1 ]
机构：
[1] Tech Univ Munich, Inst Informat, D-80290 Munich, Germany
来源：
INFORMATION PROCESSING LETTERS | 1999年 / 70卷 / 04期
关键词：
balanced Boolean functions; strongly balanced Boolean functions; spectral characterization; harmonic analysis; computational complexity;
D O I：
10.1016/S0020-0190(99)00061-7
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
This paper introduces the notions of balanced and strongly balanced Boolean functions and examines the complexity of these functions using harmonic analysis on the hypercube. The results are applied to derive a lower bound related to AC(0) functions. (C) 1999 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：157 / 163
页数：7
相关论文
共 50 条
  • [21] The Complexity of Boolean Functions in Different Characteristics
    Parikshit Gopalan
    Amir Shpilka
    Shachar Lovett
    computational complexity, 2010, 19 : 235 - 263
  • [22] THE CONJUNCTIVE COMPLEXITY OF QUADRATIC BOOLEAN FUNCTIONS
    LENZ, K
    WEGENER, I
    THEORETICAL COMPUTER SCIENCE, 1991, 81 (02) : 257 - 268
  • [23] On the distribution of the spectral complexity of boolean functions
    Ryazanov, B.V.
    1600, Publ by VSP Int Sci Publ, Zeist, Netherlands (04):
  • [24] On the complexity bounds of restrictions of Boolean functions
    Chashkin, AV
    DOKLADY AKADEMII NAUK, 1996, 348 (05) : 595 - 597
  • [25] NONLINEARITY AND PROPAGATION CHARACTERISTICS OF BALANCED BOOLEAN FUNCTIONS
    SEBERRY, J
    ZHANG, XM
    ZHENG, YL
    INFORMATION AND COMPUTATION, 1995, 119 (01) : 1 - 13
  • [26] On the Complexity of Boolean Functions in Different Characteristics
    Gopalan, Parikshit
    Lovett, Shachar
    Shpilka, Amir
    PROCEEDINGS OF THE 24TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, 2009, : 173 - +
  • [27] RESEARCHING THE COMPLEXITY OF BOOLEAN FUNCTIONS WITH COMPUTERS
    Toran, Jacobo
    Amano, Kazuyuki
    BULLETIN OF THE EUROPEAN ASSOCIATION FOR THEORETICAL COMPUTER SCIENCE, 2010, (101): : 64 - 91
  • [28] Complexity of decision trees for boolean functions
    Freivalds, R
    Miyakawa, M
    Rosenberg, IG
    33RD INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC, PROCEEDINGS, 2003, : 253 - 255
  • [29] Query complexity of Boolean functions on slices
    Byramji, Farzan
    DISCRETE MATHEMATICS, 2024, 347 (06)
  • [30] THE MONOTONE CIRCUIT COMPLEXITY OF BOOLEAN FUNCTIONS
    ALON, N
    BOPPANA, RB
    COMBINATORICA, 1987, 7 (01) : 1 - 22
12345