Concepedia

Circuit Size Complexity

Circuit Size Complexity is the minimum number of gates required in a Boolean circuit to compute a given Boolean function, serving as a measure of computational resource bounds within circuit complexity theory.

279

Publications

13.7K

Citations

503

Authors

243

Institutions

Publications per year

2017–2026

32

Parents

Publications

279

The program-size complexity of self-assembled squares (extended abstract)

Paul W. K. Rothemund, Erik Winfree · 2000 · 424 citations

, , +14

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

Alexander Razborov · Mathematical Notes · 1987 · 394 citations

, , +12

On Relating Time and Space to Size and Depth

Allan Borodin · SIAM Journal on Computing · 1977 · 341 citations

, , +17

On the maximal number of independent circuits in a graph

Keresztély Corrádi, A. Hajnal · Acta Mathematica Academiae Scientiarum Hungaricae · 1963 · 326 citations

, , +8

Ligero

Scott Ames, Carmit Hazay, Yuval Ishai et al. · 2017 · 289 citations · Full text

, , +17

1–5 of 279

Authors

503

  1. DB
    David Blaauw

    University of Michigan, United States

    7 publications · 414 citations

    7

    h-index

  2. SV
    Sarma Vrudhula

    Arizona State University, United States

    6 publications · 246 citations

    6

    h-index

  3. AR
    Alexander Razborov

    Steklov Mathematical Institute, Russia

    6 publications · 889 citations

    6

    h-index

  4. VZ
    Vladimir Zolotov

    Motorola (United States), United States

    6 publications · 283 citations

    6

    h-index

  5. PP
    Pavel Pudlák

    Czech Academy of Sciences, Institute of Mathematics, Czechia

    5 publications · 232 citations

    5

    h-index

1–5 of 503

Institutions

243

  1. Massachusetts Institute of Technology

    Cambridge, United States

    9 h-index

    12 publications

    338 citations

  2. TU Dortmund University

    Dortmund, Germany

    9 h-index

    15 publications

    532 citations

  3. University of Michigan

    Ann Arbor, United States

    9 h-index

    20 publications

    1.1K citations

  4. Motorola (United States)

    Schaumburg, United States

    8 h-index

    8 publications

    446 citations

  5. Princeton University

    Princeton, United States

    7 h-index

    9 publications

    1.1K citations

  6. University of Arizona

    Tucson, United States

    7 h-index

    7 publications

    278 citations

  7. Rutgers, The State University of New Jersey

    New Brunswick, United States

    7 h-index

    11 publications

    282 citations

  8. KTH Royal Institute of Technology

    Stockholm, Sweden

    7 h-index

    14 publications

    717 citations

1–8 of 243

Venues

  1. IEEE Transactions on Computers

    17 publications · 1.4K citations

    16

    h-index

  2. SIAM Journal on Computing

    16 publications · 1.2K citations

    14

    h-index

  3. 13

    h-index

  4. Theoretical Computer Science

    11 publications · 424 citations

    11

    h-index

  5. Information Processing Letters

    7 publications · 179 citations

    7

    h-index

1–5