Lower bounds for depth-restricted branching programs. (English) Zbl 0800.68495


68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Andreev, A.E., On a method of obtaining lower bounds to the complexity of individual monotone functions, Dokl. akad. nauk SSSR, 282, No. 5, 1033-1037, (1985) · Zbl 0616.94019
[2] Andreev, A.E., A method of obtaining superquadratic lower bounds on the complexity of π-schemes, Vestnik. Moscow unǎ. ser. I mat. mech., 6, 73-75, (1986)
[3] Alon, N.; Boppana, R.B., The monotone circuit complexity of Boolean functions, J. combinatorika, 7, No. 1, 1-22, (1987) · Zbl 0631.68041
[4] Ajtai, M.; Babaj, L.; Hajnal, P.; Komlos, J.; Pudlak, P.; Rödel, V.; Szemeredi, E.; Turan, G., Two lower bounds for branching programs, (), 30-39
[5] Barrington, D.A., Bounded width-polynomial size branching programs recognize exactly those languages in NC1, (), 1-5
[6] Blum, N., A Boolean function requiring 3n network size, J. theoret. comput. sci., 28, 337-345, (1984) · Zbl 0539.94036
[7] Dunne, P.E., Lower bounds on the complexity of one-time-only branching programs, (), 90-99
[8] Jukna, S., Lower bounds on the complexity of local circuits, (), 440-448
[9] {\scKrause, M.} (to appear), Exponential lower bounds on the complexity of real-time and local branching programs, J. Inform. Process. Cybern. (EIK).
[10] {\scKrause, M.} (in preparation), “Lower Bounds on the Complexity of Branching Programs”, thesis.
[11] Kuznetsov, S.E., Combinational circuits without null chains, Izv. vyssh. uchebn. zaved. mat., 5, 56-63, (1981)
[12] Kriegel, K.; Waack, S., Lower bounds on the complexity of real-time branching programs, () · Zbl 0584.94023
[13] Mehlhorn, K.; Schmidt, E.M., Las Vegas iis better than determinism in VLSI and distributed computing, (), 30-337
[14] Meinel, C., The power of nondeterminism in polynomial size bounded width branching programs, (), 302-309
[15] Nechiporuk, E.I., A Boolean function, Dokl. akad. nauk, 199, 765-766, (1966) · Zbl 0161.00901
[16] Paul, W., A 2.5n-lower bound on the combinational complexity of Boolean functions, SIAM J. comput., 6, No. 3, 427-443, (1977) · Zbl 0358.68081
[17] Pudlak, P.; Zak, S., Space complexity of computation, (1983), University of Prague, preprint
[18] Razborov, A.A., A lower bound on the monotone complexity of the logical permanent, Mat. zametki, 37, No. 6, 887-900, (1985) · Zbl 0584.94026
[19] Wegener, I., On the complexity of branching programs and decision trees for clique functions, interner bericht der univ. Frankfurt, 1984, Assoc. comput. math., 35, 1988, 461-471, (1984)
[20] Yao, A., The entropic limitation of VLSI-computations, (), 308-311
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.