Concepedia

Uniform Complexity

Uniform Complexity is a theoretical framework within computational complexity theory that characterizes the resources required by uniform families of Boolean circuits to solve computational problems, distinguished by the requirement that a single, recursive algorithm must generate the entire circuit family.

41

Publications

3.2K

Citations

56

Authors

44

Institutions

Publications per year

2017–2026

1

Parents

Publications

41

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

Algorithms for Vertex Partitioning Problems on Partial k-Trees

Jan Arne Telle, Andrzej Proskurowski · SIAM Journal on Discrete Mathematics · 1997 · 306 citations

, , +17

Log Depth Circuits for Division and Related Problems

Paul Beame, Stephen Cook, H. James Hoover · SIAM Journal on Computing · 1986 · 238 citations

, , +17

Theory of computational complexity

Choice Reviews Online · 2001 · 229 citations

, , +17

1–5 of 41

Authors

56

  1. NI
    Neil Immerman

    University of Massachusetts Amherst, United States

    4 publications · 128 citations

    4

    h-index

  2. SC
    Stephen Cook

    University of Toronto, Canada

    4 publications · 364 citations

    4

    h-index

  3. LT
    Luca Trevisan

    University of California, Berkeley, United States

    3 publications · 206 citations

    3

    h-index

  4. HJ
    H. James Hoover

    University of Alberta, Canada

    3 publications · 347 citations

    3

    h-index

  5. SV
    Salil Vadhan

    Harvard University Press, United States

    2 publications · 160 citations

    2

    h-index

1–5 of 56

Institutions

44

  1. University of California, Berkeley

    Berkeley, United States

    4 h-index

    5 publications

    1.4K citations

  2. University of Toronto

    Toronto, Canada

    3 h-index

    8 publications

    937 citations

  3. University of Massachusetts Amherst

    Amherst Center, United States

    3 h-index

    5 publications

    199 citations

  4. University of Washington

    Seattle, United States

    3 h-index

    3 publications

    471 citations

  5. New York University

    New York, United States

    2 h-index

    3 publications

    35 citations

  6. The University of Tokyo

    Tokyo, Japan

    2 h-index

    2 publications

    33 citations

  7. Australian National University

    Canberra, Australia

    2 h-index

    6 publications

    138 citations

  8. Yale University

    New Haven, United States

    2 h-index

    2 publications

    49 citations

1–8 of 44

Venues

  1. SIAM Journal on Computing

    4 publications · 419 citations

    4

    h-index

  2. Theoretical Computer Science

    2 publications · 100 citations

    2

    h-index

  3. International Journal of Foundations of Computer Science

    IJFCS · 1 publications · 56 citations

    1

    h-index

  4. SIAM Journal on Discrete Mathematics

    1 publications · 306 citations

    1

    h-index

  5. Journal of Symbolic Logic

    1 publications · 11 citations

    1

    h-index

1–5