Concepedia

Circuit Complexity Of Boolean Functions

Circuit Complexity of Boolean Functions is a theoretical framework in computational complexity theory that measures the minimum number of basic logic gates required to compute a Boolean function in a Boolean circuit, distinguishing it by its focus on the inherent resource constraints of circuit size and depth for function evaluation.

348

Publications

17.2K

Citations

513

Authors

266

Institutions

Publications per year

2017–2026

24

Parents

Publications

348

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

Roman Smolensky · 1987 · 760 citations · Full text

, , +16

Almost optimal lower bounds for small depth circuits

Johan Håstad · 1986 · 630 citations

, , +10

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

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 348

Authors

513

  1. AW
    Avi Wigderson

    Hebrew University of Jerusalem, Israel

    9 publications · 342 citations

    9

    h-index

  2. NK
    Neeraj Kayal

    Microsoft Research (India), India

    7 publications · 339 citations

    7

    h-index

  3. IW
    Ingo Wegener

    TU Dortmund University, Germany

    7 publications · 161 citations

    7

    h-index

  4. JH
    Johan Håstad

    KTH Royal Institute of Technology, Sweden

    6 publications · 744 citations

    6

    h-index

  5. RI
    Russell Impagliazzo

    University of California San Diego, United States

    6 publications · 268 citations

    6

    h-index

1–5 of 513

Institutions

266

  1. Massachusetts Institute of Technology

    Cambridge, United States

    11 h-index

    12 publications

    660 citations

  2. University of Toronto

    Toronto, Canada

    10 h-index

    16 publications

    1.2K citations

  3. University of Illinois Urbana-Champaign

    Urbana, United States

    10 h-index

    15 publications

    419 citations

  4. University of California San Diego

    San Diego, United States

    9 h-index

    13 publications

    679 citations

  5. Microsoft (United States)

    Redmond, United States

    9 h-index

    18 publications

    883 citations

  6. Stanford University

    Stanford, United States

    9 h-index

    12 publications

    1.1K citations

  7. Rutgers, The State University of New Jersey

    New Brunswick, United States

    9 h-index

    9 publications

    225 citations

  8. TU Dortmund University

    Dortmund, Germany

    8 h-index

    12 publications

    417 citations

1–8 of 266

Venues

  1. SIAM Journal on Computing

    31 publications · 1.5K citations

    23

    h-index

  2. Theoretical Computer Science

    22 publications · 1.3K citations

    16

    h-index

  3. IEEE Transactions on Computers

    17 publications · 1.5K citations

    15

    h-index

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

    Repository · 10 publications · 199 citations

    10

    h-index

  5. Information Processing Letters

    9 publications · 587 citations

    9

    h-index

1–5