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

[105] J. B. Fraleigh and R. A. Beauregard, Linear Algebra, Third Edition, Addison-Wesley, Reading,
MA, 1995.
[106] J. Friedman, “Constructing O ( n log n ) Size Monotone Formulae for the k th Elementary Sym-
metric Polynomial of n Boolean Variables,” SIAMJ.Comput.15 (1986), 641-654.
[107] M. Furst, J. Saxe, and M. Sipser, “Parity Circuits and the Polynomial Time Hierarchy,” Math.
SystemsTheory 17 (1984), 13-27.
[108] Z. Galil, “Some Open Problems in the Theory of Computation as Questions About Two-Way
Deterministic Pushdown Automaton Languages,” Math.SystemsTheory 10 (1974), 211-218.
[109] M. R. Garey and D. S. Johnson, Computers and Intractability: AGuide to the Theory of NP-
Completeness, W. H. Freeman, San Francisco, 1979.
[110] S. B. Gaskov, “The Depth of Boolean Functions,” Probl.Kibern.34 (1978 (in Russian)), 265-268.
[111] J. vonzur Gathen, “Parallel Linear Algebra,” in SynthesisofParallelAlgorithms, John H. Reif, ed.,
Morgan Kaufmann, San Mateo, CA, 1993.
[112] A. M. Gentleman, “Complexity Results for Matrix Computations on Parallel Processors,” JACM
25 (1978), 112-115.
[113] A. Gibbons and P. Spirakis, LecturesonParallelComputation, Cambridge University Press, Cam-
bridge, 1993.
[114] E. N. Gilbert, “Lattice-Theoretic Properties of Frontal Switching Functions,” J.Math. andPhys.
33 (1954), 57-97.
[115] J. R. Gilbert, T. Lengauer, and R. E. Tarjan, “The Pebbling Problem Is Complete in Polynomial
Space,” SIAMJ.Comput.9 (1980), 513-524.
[116] M. Goldmann and J. Hastad, “A Simple Lower Bound for Monotone Cliques Using a Communi-
cation Game,” Inf.Proc.Letters 41 (1992), 221-226.
[117] L. M. Goldschlager, “The Monotone and Planar Circuit Value Problems,” ACMSIGACTNews
9 (1977), 25-29.
[118] L. M. Goldschlager, “A Unified Approach to Models of Synchronous Parallel Machines,” JACM
29 (1982), 1073-1086.
[119] L. M. Goldschlager, “A Universal Interconnection Pattern for Parallel Computers,” JACM 30
(1983), 1073-1086.
[120] R. Greenlaw, H. J. Hoover, and W. L. Ruzzo, Limits toParallelComputation,OxfordUniversity
Press, Oxford, 1995.
[121] D. Y. Grigoriev, “An Application of Separability and Independence Notions for Proving Lower
Bounds of Circuit Complexity,” Notesof ScientificSeminars, SteklovMath. Inst. 60 (1976), 35-
48.
[122] L. J. Guibas, H. T. Kung, and C. D. Thompson, “Direct VLSI Implementation of Combinatorial
Algorithms,” Proc.Conf.VeryLargeScaleIntegration:Architecture,Design,Fabrication(1979).
[123] L. J. Guibas and F. M. Liang, “Systolic Stacks, Queues, and Counters,” Proc.Conf. onAdvanced
Research inVLSI (1982), 155-164.
[124] J. Hastad, “Almost Optimal Lower Bounds for Small Depth Circuits,” in Advances inComputer
Research,Vol.5:RandomnessandComputation, S. Micali, ed., JAI Press, Greenwich, CT, 1989,
143-170.
[125] A. Haken, “Counting Bottlenecks to Show Monotone P

= NP ,” Proc. 36th Ann. IEEE Symp.

FoundationsofComputerScience(1995), 36-40.
[126] L. H. Harper and J. E. Savage, “On the Complexity of the Marriage Problem,” Adv. Math 9
(1972), 299-312.