Concepedia

Deterministic Circuit Complexity

Deterministic Circuit Complexity is the subfield of circuit complexity that studies the minimum size or depth of Boolean circuits composed of deterministic gates—i.e., gates that compute fixed functions without randomness or nondeterministic choices—required to compute a given Boolean function, distinguishing it from probabilistic or nondeterministic models of circuit complexity.

19

Publications

661

Citations

42

Authors

29

Institutions

Publications per year

2017–2026

6

Parents

Publications

19

Las Vegas is better than determinism in VLSI and distributed computing (Extended Abstract)

Kurt Mehlhorn, Erik M. Schmidt · 1982 · 138 citations · Full text

, , +16

On non-determinancy in simple computing devices

Juris Hartmanis · Acta Informatica · 1972 · 111 citations

, , +9

Probabilistic communication complexity of Boolean relations

Ran Raz, Avi Wigderson · 1989 · 56 citations

, , +17

Communication complexities of symmetric XOR functions

Zhaoqiang Zhang, Yuanming Shi · Quantum Information and Computation · 2009 · 40 citations

, , +17

Explicit lower bound of <i>4.5n - o(n)</i> for boolena circuits

Oded Lachish, Ran Raz · 2001 · 38 citations

, , +16

1–5 of 19

Authors

42

  1. KH
    Kaave Hosseini

    University of California San Diego, United States

    2 publications · 46 citations

    2

    h-index

  2. HH
    Hamed Hatami

    University of Toronto, Canada

    2 publications · 46 citations

    2

    h-index

  3. RR
    Ran Raz

    Weizmann Institute of Science, Israel

    2 publications · 94 citations

    2

    h-index

  4. SL
    Shachar Lovett

    University of California San Diego, United States

    2 publications · 46 citations

    2

    h-index

  5. ZZ
    Zhiqiang Zhang

    Tongji University, China

    1 publications · 12 citations

    1

    h-index

1–5 of 42

Institutions

29

  1. Harvard University Press

    Cambridge, United States

    2 h-index

    4 publications

    87 citations

  2. University of California San Diego

    San Diego, United States

    2 h-index

    5 publications

    122 citations

  3. McGill University

    Montreal, Canada

    2 h-index

    4 publications

    106 citations

  4. Singapore University of Technology and Design

    Singapore, Singapore

    1 h-index

    1 publications

    21 citations

  5. University of Michigan

    Ann Arbor, United States

    1 h-index

    1 publications

    40 citations

  6. Clemson University

    Clemson, United States

    1 h-index

    1 publications

    25 citations

  7. Aarhus University

    Aarhus, Denmark

    1 h-index

    1 publications

    138 citations

  8. Albany State University

    Albany, United States

    1 h-index

    2 publications

    20 citations

1–8 of 29

Venues

  1. SIAM Journal on Computing

    2 publications · 40 citations

    2

    h-index

  2. Quantum Information and Computation

    QIC · 1 publications · 40 citations

    1

    h-index

  3. Journal of Symbolic Computation

    1 publications · 25 citations

    1

    h-index

  4. 1

    h-index

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

    Repository · 1 publications · 24 citations

    1

    h-index

1–5