Concepedia

Uniform Circuit Complexity

Uniform Circuit Complexity is a complexity-theoretic framework that characterizes the computational power of families of Boolean circuits wherein each circuit in the sequence is efficiently generated by a deterministic algorithm, thus imposing a uniformity condition that links circuit-based computation to uniform models such as Turing machines.

23

Publications

2.2K

Citations

36

Authors

25

Institutions

Publications per year

2017–2026

1

Parents

Publications

23

Some connections between nonuniform and uniform complexity classes

Richard M. Karp, Richard J. Lipton · 1980 · 582 citations · Full text

, , +17

On uniform circuit complexity

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

, , +17

Uniform constant-depth threshold circuits for division and iterated multiplication

William Hesse, Eric Allender, David A. Mix Barrington · Journal of Computer and System Sciences · 2002 · 187 citations

, , +9

A uniform-complexity treatment of encryption and zero-knowledge

Oded Goldreich · Journal of Cryptology · 1993 · 136 citations · Full text

, , +12

Expressibility and Parallel Complexity

Neil Immerman · SIAM Journal on Computing · 1989 · 124 citations

, , +15

1–5 of 23

Authors

36

  1. DA
    David A. Mix Barrington

    University of Massachusetts Amherst, United States

    4 publications · 256 citations

    4

    h-index

  2. EA
    Eric Allender

    Rutgers, The State University of New Jersey, United States

    3 publications · 295 citations

    3

    h-index

  3. WL
    Walter L. Ruzzo

    University of Washington, United States

    2 publications · 459 citations

    2

    h-index

  4. NI
    Neil Immerman

    University of Massachusetts Amherst, United States

    2 publications · 141 citations

    2

    h-index

  5. AC
    Andrew Chiu

    University of Wisconsin–Milwaukee, United States

    1 publications · 89 citations

    1

    h-index

1–5 of 36

Institutions

25

  1. University of Massachusetts Amherst

    Amherst Center, United States

    3 h-index

    4 publications

    426 citations

  2. Rutgers, The State University of New Jersey

    New Brunswick, United States

    2 h-index

    2 publications

    240 citations

  3. University of Washington

    Seattle, United States

    2 h-index

    2 publications

    459 citations

  4. Yale University

    New Haven, United States

    2 h-index

    2 publications

    141 citations

  5. University of California San Diego

    San Diego, United States

    2 h-index

    2 publications

    37 citations

  6. Princeton University

    Princeton, United States

    2 h-index

    3 publications

    121 citations

  7. University of Wisconsin–Milwaukee

    Milwaukee, United States

    1 h-index

    2 publications

    178 citations

  8. Technion – Israel Institute of Technology

    Haifa, Israel

    1 h-index

    1 publications

    136 citations

1–8 of 25

Venues

  1. SIAM Journal on Computing

    4 publications · 278 citations

    4

    h-index

  2. Theoretical Computer Science

    2 publications · 74 citations

    2

    h-index

  3. Journal of Computer and System Sciences

    2 publications · 621 citations

    2

    h-index

  4. Journal of the ACM

    JACM · 1 publications · 53 citations

    1

    h-index

  5. RAIRO - Theoretical Informatics and Applications

    ITA · 1 publications · 89 citations

    1

    h-index

1–5