Bibliography - Models of Computation: Exploring the Power of Computing - page 612

[150] D. Johnson, J. E. Savage, and L. R. Welch, “Combinational Complexity Measures as a Function
of Fan-Out,” Jet Propulsion Laboratory, Technical Report No. 32-1526, 1972.
[151] D. S. Johnson, “A Catalog of Complexity Classes,” in HandbookofTheoreticalComputerScience,
Vol. A, J. van Leeuwen, ed., Elsevier, Amsterdam,NY,Oxford,Tokyo;MITPress,Cambridge,
MA, 1990, 68-161.
[152] R. B. Johnson, “The Complexity of a VLSI Adder,” Info.ProcessingLetters 11 (1980), 92-93.
[153] N. D. Jones and W. T. Laaser, “Complete Problems for Deterministic Polynomial Time,” Theoret.
Comp.Sci. 3 (1976), 105-117.
[154] B. H. H. Juurlink and H. A. G. Wijshoff, “A Quantitative Comparison of Parallel Computational
Models,” Proc.8thAnn.ACMSymp.ParallelAlgorithmsandArchitectures(1996), 13-24.
[155] A. Karatsuba and Y. Ofman, “Multiplication of Multidigit Numbers on Automata,” Dokl. Akad.
Nauk SSSR (Soviet Math. Dokl.) 145 (1962), 293-294, (in Russian);

English translation in Sov. Phys.-Dokl. 19 (1963), 595-596.
[156] M. Karchmer, CommunicationComplexity:ANewApproachtoCircuitDepth, MIT Press, Cam-
bridge, MA and London, England, 1989.
[157] M. Karchmer and A. Wigderson, “Monotone Circuits for Connectivity Require Superlogarithmic
Depth,” Proc.20thAnn.ACMSymp.TheoryofComputing(1988), 539-550.
[158] A. R. Karlin and E. Upfal, “Parallel Hashing - An Efficient Implementation of Shared Memory,”
Proc.18thAnn.ACMSymp.TheoryofComputing(1986), 160-168.
[159] R. Karp, “Reducibility Among Combinatorial Problems,” in ComplexityofComputerComputa-
tions, R. E. Miller and J. Thatcher, eds., Plenum, New York, 1972,

85-104.
[160] R. M. Karp and R. J. Lipton, “Some Connections Between Nonuniform and Uniform Complexity
Classes,” Proc.12thAnn.ACMSymp.TheoryofComputing(April 28-30, 1980), 302-309.
[161] R. M. Karp and V. Ramachandran, “A Survey of Parallel Algorithms for Shared-Memory Ma-
chines,” in Handbook of Theoretical Computer Science, Vol. A, J. van Leeuwen, ed., Elsevier,
Amsterdam, NY, Oxford, Tokyo; MIT Press, Cambridge, MA, 1990, 870-941.
[162] T. Kasami, “An Efficient Recognition and Syntax Algorithm for Context-Free Languages,” Air
Force Cambridge Research Laboratory, Report AFCRL-65-758, Cambridge, MA, 1965.
[163] Z. M. Kedem and A. Zorat, “Replication of Inputs May Save Computational Resources in VLSI,”
in VLSISystemsandComputations, H. T. Kung, B. Sproull, and G. Steele, eds., Computer Science
Press, Rockville, MD, 1981, 52-60.
[164] Z. M. Kedem and A. Zorat, “On Relations Between Input and Communication/Computation,”
Proc.22ndAnn. IEEESymp.FoundationsofComputerScience(1981), 37-44.
[165] L. G. Khachian, “A Polynomial Time Algorithm for Linear Programming,” Dokl. Akad. Nauk
SSSR(SovietMath.Dokl.) 244 (1979), 1093-1096.
[166] L. S. Khasin, “Complexity Bounds for the Realization of Monotone Symmetrical Functions by
Means of Formulas in the Basis + , ,” Dokl. Akad. Nauk SSSR (Soviet Math. Dokl.) 189

(1970), 752-755, (in Russian); English translation in Soviet Phys. Dokl. 14(12) (1970), 1149-
1151.
[167] M. M. Klawe, “A Tight Bound for Black and White Pebbles on the Pyramid,” Proc. 24th Ann.
IEEESymp.FoundationsofComputerScience(1983), 410-419.
[168] S. C. Kleene, “General Recursive Functions of Natural Numbers,” Math. Annalen 112 (1936),
727-742.

· , −