Concepedia

Circuit Depth Complexity

Circuit Depth Complexity is the minimum depth, measured as the length of the longest path from an input node to an output node, among all Boolean circuits that compute a given function, where depth corresponds to the number of layers of logic gates in the circuit.

120

Publications

7.2K

Citations

249

Authors

124

Institutions

Publications per year

2017–2026

36

Variants

Circuit Depth

Parents

Publications

120

Almost optimal lower bounds for small depth circuits

Johan Håstad · 1986 · 630 citations

, , +10

Constant depth circuits, Fourier transform, and learnability

Nathan Linial, Yishay Mansour, Noam Nisan · Journal of the ACM · 1993 · 591 citations · Full text

, , +9

On Relating Time and Space to Size and Depth

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

, , +17

Monotone Circuits for Connectivity Require Super-Logarithmic Depth

Mauricio Karchmer, Avi Wigderson · SIAM Journal on Discrete Mathematics · 1990 · 288 citations

, , +13

Differentiable learning of quantum circuit Born machines

Jin-Guo Liu, Lei Wang · Physical review. A/Physical review, A · 2018 · 282 citations · Full text

, , +16

1–5 of 120

Authors

249

  1. AW
    Avi Wigderson

    Hebrew University of Jerusalem, Israel

    6 publications · 594 citations

    6

    h-index

  2. RR
    Ran Raz

    Weizmann Institute of Science, Israel

    4 publications · 231 citations

    4

    h-index

  3. VG
    Vince Grolmusz

    Eötvös Loránd University, Hungary

    3 publications · 46 citations

    3

    h-index

  4. MK
    Mauricio Karchmer

    Hebrew University of Jerusalem, Israel

    3 publications · 486 citations

    3

    h-index

  5. JH
    Johan Håstad

    KTH Royal Institute of Technology, Sweden

    3 publications · 653 citations

    3

    h-index

1–5 of 249

Institutions

124

  1. University of Toronto

    Toronto, Canada

    6 h-index

    12 publications

    1.4K citations

  2. Hebrew University of Jerusalem

    Jerusalem, Israel

    5 h-index

    7 publications

    1.7K citations

  3. Stanford University

    Stanford, United States

    5 h-index

    8 publications

    613 citations

  4. Weizmann Institute of Science

    Rehovot, Israel

    4 h-index

    6 publications

    335 citations

  5. Tel Aviv University

    Tel Aviv, Israel

    4 h-index

    6 publications

    833 citations

  6. University of Michigan

    Ann Arbor, United States

    4 h-index

    5 publications

    198 citations

  7. University of California San Diego

    San Diego, United States

    4 h-index

    8 publications

    179 citations

  8. TU Dortmund University

    Dortmund, Germany

    3 h-index

    5 publications

    137 citations

1–8 of 124

Venues

  1. SIAM Journal on Computing

    11 publications · 902 citations

    10

    h-index

  2. arXiv (Cornell University)

    Repository · 8 publications · 241 citations

    8

    h-index

  3. Physical Review Letters

    PRL · 5 publications · 482 citations

    5

    h-index

  4. Theoretical Computer Science

    4 publications · 137 citations

    4

    h-index

  5. Information and Computation

    3 publications · 80 citations

    3

    h-index

1–5