Concepedia

Boolean Circuit Complexity

Boolean Circuit Complexity is a quantitative measure in computational complexity theory that characterizes the minimum size or depth of a Boolean circuit, composed of logical gates and operating over binary inputs, required to compute a given Boolean function, thereby distinguishing it from other models of computation by its non-uniform and combinatorial circuit-based structure.

341

Publications

16.3K

Citations

520

Authors

308

Institutions

Publications per year

2017–2026

45

Parents

Publications

341

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

Roman Smolensky · 1987 · 760 citations · Full text

, , +16

Separating the polynomial-time hierarchy by oracles

Andrew Chi-Chih Yao · 1985 · 554 citations

, , +17

On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication

Randal E. Bryant · IEEE Transactions on Computers · 1991 · 524 citations

, , +16

Delegating computation

Shafi Goldwasser, Yael Tauman Kalai, Guy N. Rothblum · 2008 · 477 citations

, , +13

Lower bounds on the size of bounded depth circuits over a complete basis with logical addition

Alexander Razborov · Mathematical Notes · 1987 · 394 citations

, , +12

1–5 of 341

Authors

520

  1. RR
    Ran Raz

    Weizmann Institute of Science, Israel

    7 publications · 283 citations

    7

    h-index

  2. IW
    Ingo Wegener

    TU Dortmund University, Germany

    7 publications · 238 citations

    7

    h-index

  3. AW
    Avi Wigderson

    Hebrew University of Jerusalem, Israel

    7 publications · 207 citations

    7

    h-index

  4. RP
    Ramamohan Paturi

    University of California San Diego, United States

    7 publications · 251 citations

    7

    h-index

  5. SC
    Stephen Cook

    University of Toronto, Canada

    6 publications · 402 citations

    6

    h-index

1–5 of 520

Institutions

308

  1. Stanford University

    Stanford, United States

    14 h-index

    22 publications

    1.8K citations

  2. Centre National de la Recherche Scientifique

    Paris, France

    14 h-index

    29 publications

    916 citations

  3. University of California San Diego

    San Diego, United States

    11 h-index

    25 publications

    845 citations

  4. Princeton University

    Princeton, United States

    10 h-index

    13 publications

    1.1K citations

  5. Massachusetts Institute of Technology

    Cambridge, United States

    10 h-index

    9 publications

    883 citations

  6. University of Toronto

    Toronto, Canada

    9 h-index

    18 publications

    1.1K citations

  7. Steklov Mathematical Institute

    Moscow, Russia

    8 h-index

    8 publications

    729 citations

  8. Rutgers, The State University of New Jersey

    New Brunswick, United States

    8 h-index

    10 publications

    290 citations

1–8 of 308

Venues

  1. SIAM Journal on Computing

    24 publications · 1.3K citations

    20

    h-index

  2. IEEE Transactions on Computers

    20 publications · 1.8K citations

    18

    h-index

  3. Theoretical Computer Science

    14 publications · 580 citations

    12

    h-index

  4. Journal of the ACM

    JACM · 12 publications · 512 citations

    11

    h-index

  5. DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

    Repository · 9 publications · 155 citations

    9

    h-index

1–5