Abstract
We survey lower bounds established for the complexity of computing explicitly given Boolean functions by switching-and-rectifier networks, branching programs and switching networks. We first consider the unrestricted case and then proceed to various restricted models. Among these are monotone networks, bounded-width devices, oblivious devices and read-k times only devices.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Ajtai, L. Babai, P. Hajnal, J. Komlos, P. Pudlák, V. Rödl, E. Szemeredi, and Gy. Turán. Two lower bounds for branching programs. In Proceedings of the 18st ACM STOC, pages 30–38, 1986.
M. Ajtai, J. Komlós, and E. Szemeredi. An O(n log n) sorting network. In Proceedings of the 15st ACM STOC, pages 1–9, 1983.
R. Aleluinas, R. M. Karp, R. J. Lipton, R. J. Lovász, and C. Rackoff. Random walks, universal sequences and the complexity of maze problems. In Proceedings of the 20th IEEE Symposium on Foundations of Computer Science, pages 218–223, 1979.
N. Alon and W. Maass. Meanders and their applications in lower bounds arguments. Journal of Computer and System Sciences, 37:118–129, 1988.
L. Babai, N. Nisan, and M. Szegedy. Multiparty protocols and logspace-hard pseudorandom sequences. In Proceedings of the 21st ACM STOC, pages 1–11, 1989.
L. Babai, P. Pudlák, V. Rödl, and E. Szemeredi. Lower bounds in complexity of symmetric Boolean functions. 1988. To appear in Theoretical Computer Science.
D. A. Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC 1. In Proceedings of the 18st ACM STOC, pages 1–5, 1986.
D. A. Barrington and H. Straubing. Superlinear lower bounds for bounded-width branching programs. 1990. Preprint.
R. B. Boppana and M. Sipser. The complexity of finite functions. In Jan Van Leeuwen, editor, Handbook of Theoretical Computer Science, vol. A (Algorithms and Complexity), chapter 14, pages 757–804, Elsevier Science Publishers B.V. and The MIT Press, 1990.
A. Borodin and S. Cook. A time-space tradeoff for sorting on a general sequential model of computation. SIAM Journal on Computing, 11(2):287–297, 1982.
A. Borodin, D. Dolev, F. Fich, and W. Paul. Bounds for width 2 branching programs. In Proceedings of the 15st ACM STOC, pages 87–93, 1983.
A. Borodin, A. Razborov, and R. Smolensky. On lower bounds for read-k times branching programs. May 1991. Submitted to Computational Complexity.
Jin-yi Cai and R. J. Lipton. Subquadratic simulations of circuits by branching programs. In Proceedings of the 30st IEEE FOCS, pages 568–573, 1989.
A. Chandra, M. Furst, and R. Lipton. Multiparty protocols. In Proceedings of the 15th ACM STOC, pages 94–99, 1983.
R. Cleve. Towards optimal simulations of formulas by bounded-width programs. In Proceedings of the 22th ACM STOC, pages 271–277, 1990.
P. E. Dunne. Lower bounds on the complexity of one-time-only branching programs. In Proceedings of the FCT, Lecture Notes in Computer Science, 199, pages 90–99, Springer-Verlag, New York/Berlin, 1985.
M. A. Gavrilov. The theory of relay and switching circuits. Nauka, 1950. In Russian.
M. I. Grinchuk. On the switching network size of symmetric Boolean functions (in Russian). Master's thesis, Moscow State University, Moscow, 1989.
J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, Massachussetts, 1979.
N. Immerman. Nondeterministic space is closed under complementation. In Proceedings of the 3rd Structures in Complexity Theory Annual Conference, pages 112–115, 1988.
S. Jukna. Lower bounds on the complexity of local circuits. In Proceedings of the MFCT'86, Lecture Notes in Computer Science, 233, pages 440–448, Springer-Verlag, New York/Berlin, 1986.
R. Kannan. A circuit size lower bound. In Proceedings of the 22th IEEE Symposium on Foundations of Computer Science, pages 304–309, 1981.
M. Krause. Exponential lower bounds on the complexity of local and real-time branching programs. 1986. To appear in J. Inform. Process. Cybern. (EIK).
M. Krause. Lower bounds for depth-restricted branching programs. Information and Computation, 91(1):1–14, 1991.
K. Kriegel and S. Waack. Lower bounds on the complexity of real-time branching programs. In Proceedings of the FCT, Lecture Notes in Computer Science, 278, pages 90–99, Springer-Verlag, New York/Berlin, 1987.
O. B. Lupanov. On computing symmetric functions of the propositional calculus by switching networks (in Russian). In Problems of Cybernetics, vol. 15, pages 85–100, Nauka, 1965.
A. A. Markov. On minimal switching-and-rectifier networks for monotone symmetric functions (in Russian). In Problems of Cybernetics, vol. 8, pages 117–121, Nauka, 1962.
W. Masek. A fast algorithm for the string edidting problem and decision graph complexity. Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1976.
E. I. Nečiporuk. On a Boolean function. Doklady of the Academy of Sciences of the USSR, 169(4):765–766 (in Russian), 1966. English translation in Soviet Mathematics Doklady 7:4, pages 999–1000.
C. H. Papadimitriou and M. Sipser. Communication complexity. In Proceedings of the 14th ACM STOC, pages 196–200, 1982.
M. S. Paterson and L. G. Valiant. Circuit size is nonlinear in depth. Theoretical Computer Science, 2:397–400, 1976.
P. Pudlák. The hierarchy of Boolean circuits. Computers and Artificial Intelligence, 6(5):449–468, 1987.
P. Pudlák. A lower bound on complexity of branching programs. In Proceedings of the 11th MFCT, Lecture Notes in Computer Science, 176, pages 480–489, Springer-Verlag, New York/Berlin, 1984.
A. A. Razborov. Lower bounds on the size of switching-and-rectifier networks for symmetric Boolean functions. Mathematical Notes of the Academy of Sciences of the USSR, 48(6):79–91, 1990.
A. A. Razborov. On the method of approximation. In Proceedings of the 21st ACM Symposium on Theory of Computing, pages 167–176, 1989.
C. Shannon. A symbolic analysis of relay and switching networks. Transactions of American Institute of Electrical Engeneers, 57:713–723, 1938.
C. Shannon. The synthesis of two-terminal switching circuits. Bell Systems Technical Journal, 28(1):59–98, 1949.
J. Simon and M. Szegedy. Lower bound techniques for read only once branching programs. November 1990. Preprint.
P. M. Spira. On time-hardware complexity tradeoffs for Boolean functions. In Proceedings of the 4th Hawaii Symposium on System Sciences, pages 525–527, Western Periodicals Company, North Hollywood, 1971.
R. Szelepcsényi. The method of forcing for nondeterministic automata. Bulletin of the EATCS, 33:96–99, 1987.
L. G. Valiant. Short monotone formulae for the majority function. Journal of Algorithms, 5:363–366, 1984.
I. Wegener. The complexity of Boolean functions. Wiley-Teubner, 1987.
I. Wegener. On the complexity of branching programs and decision trees for clique functions. Assoc. Comput. Math., 35:461–471, 1988.
A. Yao. Lower bounds by probabilistic arguments. In Proceedings of the 24th IEEE FOCS, pages 420–428, 1983.
S. Žák. An exponential lower bound for one-time-only branching programs. In Proceedings of the 11th MFCT, Lecture Notes in Computer Science, 176, pages 562–566, Springer-Verlag, New York/Berlin, 1984.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Razborov, A.A. (1991). Lower bounds for deterministic and nondeterministic branching programs. In: Budach, L. (eds) Fundamentals of Computation Theory. FCT 1991. Lecture Notes in Computer Science, vol 529. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-54458-5_49
Download citation
DOI: https://doi.org/10.1007/3-540-54458-5_49
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-54458-6
Online ISBN: 978-3-540-38391-8
eBook Packages: Springer Book Archive