Circuit Complexity and Multiplicative Complexity of Boolean Functions

被引：0
|
作者：
Kojevnikov, Arist [1 ]
Kulikov, Alexander S. [1 ]
机构：
[1] VA Steklov Math Inst, St Petersburg Dept, Moscow 117333, Russia
来源：
PROGRAMS, PROOFS, PROCESSES | 2010年 / 6158卷
关键词：
COMBINATIONAL COMPLEXITY; BOUNDS;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In this note, we use lower bounds on Boolean multiplicative complexity to prove lower bounds on Boolean circuit complexity. We give a very simple proof of a 7n/3 - c lower bound on the circuit complexity of a large class of functions representable by high degree polynomials over GF(2). The key idea of the proof is a circuit complexity measure assigning different weights to XOR and AND gates.
引用
收藏
页码：239 / 245
页数：7
相关论文
共 50 条
  • [1] THE MULTIPLICATIVE COMPLEXITY OF BOOLEAN FUNCTIONS
    SCHNORR, CP
    LECTURE NOTES IN COMPUTER SCIENCE, 1989, 357 : 45 - 58
  • [2] On the Multiplicative Complexity of Boolean Functions
    Selezneva, Svetlana N.
    FUNDAMENTA INFORMATICAE, 2016, 145 (03) : 399 - 404
  • [3] On the multiplicative complexity of some Boolean functions
    Selezneva, S. N.
    COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS, 2015, 55 (04) : 724 - 730
  • [4] On the multiplicative complexity of some Boolean functions
    S. N. Selezneva
    Computational Mathematics and Mathematical Physics, 2015, 55 : 724 - 730
  • [5] Multiplicative complexity of some Boolean functions
    Selezneva, Svetlana N.
    DISCRETE MATHEMATICS AND APPLICATIONS, 2015, 25 (02): : 101 - 108
  • [6] Boolean functions with multiplicative complexity 3 and 4
    Calik, Cagdas
    Turan, Meltem Sonmez
    Peralta, Rene
    CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES, 2020, 12 (05): : 935 - 946
  • [7] Boolean functions with multiplicative complexity 3 and 4
    Çağdaş Çalık
    Meltem Sönmez Turan
    René Peralta
    Cryptography and Communications, 2020, 12 : 935 - 946
  • [8] Multiplicative complexity of vector valued Boolean functions
    Boyar, Joan
    Find, Magnus Gausdal
    THEORETICAL COMPUTER SCIENCE, 2018, 720 : 36 - 46
  • [9] THE MONOTONE CIRCUIT COMPLEXITY OF BOOLEAN FUNCTIONS
    ALON, N
    BOPPANA, RB
    COMBINATORICA, 1987, 7 (01) : 1 - 22
  • [10] Upper bounds on the multiplicative complexity of symmetric Boolean functions
    Brandao, Luis T. A. N.
    Calik, Cagdas
    Sonmez Turan, Meltem
    Peralta, Rene
    CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES, 2019, 11 (06): : 1339 - 1362
12345