Concepedia

Bounded-depth Circuits

Bounded-Depth Circuits is a Boolean circuit model belonging to the class of computational circuits characterized by a constant depth independent of input size, distinguished by its restriction on the number of sequential layers of logic gates, thereby limiting computational parallelism and typically used to study the complexity of problems within subclasses of P.

136

Publications

7.9K

Citations

227

Authors

121

Institutions

Publications per year

2017–2026

16

Variants

Bounded-depth Circuit

Parents

Publications

136

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

On uniform circuit complexity

Walter L. Ruzzo · Journal of Computer and System Sciences · 1981 · 434 citations

, , +17

Quantum advantage with shallow circuits

Sergey Bravyi, David Gosset, Robert König · Science · 2018 · 424 citations · Full text

, , +17

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 136

Authors

227

  1. PP
    Pavel Pudlák

    Czech Academy of Sciences, Institute of Mathematics, Czechia

    7 publications · 511 citations

    7

    h-index

  2. AW
    Avi Wigderson

    Hebrew University of Jerusalem, Israel

    6 publications · 615 citations

    6

    h-index

  3. RS
    Ramprasad Saptharishi

    Microsoft Research (India), India

    6 publications · 169 citations

    6

    h-index

  4. RI
    Russell Impagliazzo

    University of California San Diego, United States

    5 publications · 183 citations

    5

    h-index

  5. NS
    Nitin Saxena

    Indian Institute of Technology Kanpur, India

    4 publications · 110 citations

    4

    h-index

1–5 of 227

Institutions

121

  1. University of California San Diego

    San Diego, United States

    10 h-index

    15 publications

    513 citations

  2. Massachusetts Institute of Technology

    Cambridge, United States

    7 h-index

    10 publications

    310 citations

  3. Czech Academy of Sciences, Institute of Mathematics

    Prague, Czechia

    6 h-index

    8 publications

    238 citations

  4. IBM (United States)

    Armonk, United States

    5 h-index

    10 publications

    629 citations

  5. Rutgers, The State University of New Jersey

    New Brunswick, United States

    5 h-index

    6 publications

    257 citations

  6. Princeton University

    Princeton, United States

    5 h-index

    5 publications

    184 citations

  7. Microsoft (United States)

    Redmond, United States

    4 h-index

    10 publications

    358 citations

  8. Aarhus University

    Aarhus, Denmark

    4 h-index

    5 publications

    100 citations

1–8 of 121

Venues

  1. SIAM Journal on Computing

    11 publications · 499 citations

    11

    h-index

  2. arXiv (Cornell University)

    Repository · 10 publications · 242 citations

    10

    h-index

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

    Repository · 6 publications · 107 citations

    6

    h-index

  4. Journal of Computer and System Sciences

    5 publications · 782 citations

    5

    h-index

  5. Information Processing Letters

    5 publications · 279 citations

    5

    h-index

1–5