Concepedia

On the computational power of depth-2 circuits with threshold and modulo gates

Matthias Krause, Pavel Pudlák

Theoretical Computer Science · 1997 · 75 citations · 22 references

DOI

Concepts

References

22

Algebraic methods in the theory of lower bounds for Boolean circuit complexity

Roman Smolensky · 1987 · 760 citations · Full text

, , +16

Simple Constructions of Almost k‐wise Independent Random Variables

Noga Alon, Oded Goldreich, Johan Håstad et al. · Random Structures and Algorithms · 1992 · 569 citations

, , +8

A guided tour of chernoff bounds

Torben Hagerup, Christine Rüb · Information Processing Letters · 1990 · 525 citations

, , +12

Majority gates vs. general weighted threshold gates

Mikael Goldmann, Johan H�stad, Alexander Razborov · Computational Complexity · 1992 · 210 citations

, , +13

ON ACC and threshold circuits

Andrew Chi-Chih Yao · 2002 · 201 citations

, , +12