Circuit Complexity

Circuit Complexity is a branch of computational complexity theory that classifies computational problems according to the size and depth of Boolean circuits required to solve them, distinguishing it from other complexity measures by focusing on non-uniform models of computation.

3.3K

Publications

180.2K

Citations

5.1K

Authors

1.4K

Institutions

Publications per year

2017–2026

523

Parents

Theory Of Computation

Children

Arithmetic Circuit ComplexityArithmetic Formula Lower BoundsBoolean Circuit ComplexityBounded-depth CircuitsCircuit Complexity HierarchiesCircuit Complexity Of Boolean FunctionsCircuit Complexity Of Natural PropertiesCircuit Depth ComplexityCircuit Evaluation ProblemCircuit Lower Bounds

Publications

3.3K

Elementary gates for quantum computation

Adriano Barenco, Charles H. Bennett, Richard Cleve et al. · Physical Review A · 1995 · 4.4K citations · Full text

Computing, Computer Science, Quantum Computing +16

Combinational profiles of sequential benchmark circuits

F. Brglez, D. Bryan, Krzysztof Koźmiński · 2003 · 2.1K citations

Engineering, Computer Engineering, Computer Science +17

Boosting a Weak Learning Algorithm by Majority

Yoav Freund · Information and Computation · 1995 · 1.7K citations

Computing, Computer Science, Mathematics +11

Improved simulation of stabilizer circuits

Scott Aaronson, Daniel Gottesman · Physical Review A · 2004 · 1.6K citations · Full text

Computing, Computer Science, Mathematics +17

Which Problems Have Strongly Exponential Complexity?

Russell Impagliazzo, Ramamohan Paturi, Francis Zane · Journal of Computer and System Sciences · 2001 · 1.4K citations

Computing, Computer Science, Mathematics +16

1–5 of 3.3K

Authors

5.1K

AW
Avi Wigderson
Hebrew University of Jerusalem, Israel
46 publications · 3.5K citations
28
h-index
RI
Russell Impagliazzo
University of California San Diego, United States
32 publications · 4K citations
25
h-index
RW
Ryan Williams
Stanford University, United States
28 publications · 1.5K citations
21
h-index
RD
Rolf Drechsler
University of Bremen, Germany
31 publications · 1.3K citations
20
h-index
IL
Igor L. Markov
University of Michigan, United States
20 publications · 1.7K citations
18
h-index

1–5 of 5.1K

Institutions

1.4K

1–8 of 1.4K

Venues

SIAM Journal on Computing
143 publications · 12K citations
55
h-index
IEEE Transactions on Computers
122 publications · 9.2K citations
46
h-index
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
124 publications · 7.1K citations
43
h-index
Theoretical Computer Science
59 publications · 2.3K citations
26
h-index
Journal of Computer and System Sciences
37 publications · 4.6K citations
25
h-index

1–5