Concepedia

Complexity Of Boolean Functions

Complexity of Boolean Functions is a theoretical framework in computational complexity theory that characterizes the inherent difficulty of computing Boolean functions by measuring the minimum resources, such as time, circuit size, or decision tree depth, required by any algorithm or computational model to evaluate them correctly on all inputs.

736

Publications

46K

Citations

1.1K

Authors

509

Institutions

Publications per year

2017–2026

79

Parents

Publications

736

Graph-Based Algorithms for Boolean Function Manipulation

Bryant · IEEE Transactions on Computers · 1986 · 8.9K citations · Full text

, , +16

Some complexity questions related to distributive computing(Preliminary Report)

Andrew Chi-Chih Yao · 1979 · 1.1K citations · Full text

, , +11

Algebraic methods in the theory of lower bounds for Boolean circuit complexity

Roman Smolensky · 1987 · 760 citations · Full text

, , +16

Cryptographic limitations on learning Boolean formulae and finite automata

Michael Kearns, Leslie G. Valiant · Journal of the ACM · 1994 · 744 citations · Full text

, , +17

Quantum lower bounds by polynomials

Robert Beals, Harry Buhrman, Richard Cleve et al. · Journal of the ACM · 2001 · 659 citations

, , +17

1–5 of 736

Authors

1.1K

  1. RA
    Rocco A. Servedio

    Columbia University, United States

    25 publications · 1K citations

    17

    h-index

  2. IW
    Ingo Wegener

    TU Dortmund University, Germany

    14 publications · 1.1K citations

    13

    h-index

  3. CC
    Claude Carlet

    Université Paris 8, France

    12 publications · 661 citations

    11

    h-index

  4. RO
    Ryan O’Donnell

    Carnegie Mellon University, United States

    10 publications · 482 citations

    10

    h-index

  5. AW
    Avi Wigderson

    Hebrew University of Jerusalem, Israel

    11 publications · 647 citations

    10

    h-index

1–5 of 1.1K

Institutions

509

  1. Centre National de la Recherche Scientifique

    Paris, France

    19 h-index

    34 publications

    1.4K citations

  2. Massachusetts Institute of Technology

    Cambridge, United States

    17 h-index

    32 publications

    2.2K citations

  3. Columbia University

    New York, United States

    17 h-index

    51 publications

    2K citations

  4. University of California, Berkeley

    Berkeley, United States

    17 h-index

    26 publications

    1.7K citations

  5. Rutgers, The State University of New Jersey

    New Brunswick, United States

    14 h-index

    25 publications

    1.5K citations

  6. Hebrew University of Jerusalem

    Jerusalem, Israel

    14 h-index

    19 publications

    1.5K citations

  7. TU Dortmund University

    Dortmund, Germany

    14 h-index

    29 publications

    2.3K citations

  8. Technion – Israel Institute of Technology

    Haifa, Israel

    14 h-index

    20 publications

    745 citations

1–8 of 509

Venues

  1. SIAM Journal on Computing

    55 publications · 3.8K citations

    30

    h-index

  2. Theoretical Computer Science

    28 publications · 1.4K citations

    20

    h-index

  3. IEEE Transactions on Computers

    24 publications · 10.8K citations

    19

    h-index

  4. IEEE Transactions on Information Theory

    24 publications · 1.1K citations

    17

    h-index

  5. Journal of the ACM

    JACM · 20 publications · 2.7K citations

    15

    h-index

1–5