Concepedia

Exact lower time bounds for computing Boolean functions on CREW PRAMs

Martin Dietzfelbinger, Mirosław Kutyłowski

Journal of Computer and System Sciences · 1994 · 48 citations · 22 references

Concepts

ComputingComputer EngineeringComputer ScienceAlgorithmsTheory Of ComputationBoolean AlgebraBoolean OperationsCircuit ComplexityComputational ComplexityDigital Logic DesignTiming AnalysisBoolean Function ComplexityBoolean FunctionsCircuit Lower BoundsComplexity Of Boolean FunctionsComputational Lower BoundsLower BoundsWorst-case Bounds

References

22

A class of multiple-error-correcting codes and the decoding scheme

I.S. Reed · Transactions of the IRE Professional Group on Information Theory · 1954 · 852 citations

Engineering, Computer Science, Electrical Engineering +17

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

Roman Smolensky · 1987 · 760 citations · Full text

Computing, Computer Science, Mathematics +16

The influence of variables on Boolean functions

J. Kahn, Gil Kalai, Nathan Linial · 1988 · 628 citations

Natural Sciences, Computer Science, Mathematics +7

Constant depth circuits, Fourier transform, and learnability

Nathan Linial, Yishay Mansour, Noam Nisan · Journal of the ACM · 1993 · 591 citations · Full text

Engineering, Computer Science, Instrumentation +9

Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

Stephen Cook, Cynthia Dwork, Rüdiger Reischuk · SIAM Journal on Computing · 1986 · 339 citations

Computing, Computer Engineering, Computer Science +15