Abstract
We study the computational power of decision lists over AND-functions versus threshold-⊕ circuits. AND-decision lists are a natural generalization of formulas in disjunctive or conjunctive normal form. We showthat, in contrast to CNF- and DNF-formulas, there are functions with small AND-decision lists which need exponential size unbounded weight threshold-⊕ circuits. This implies that Jackson’s polynomial learning algorithm for DNFs [7] which is based on the efficient simulation of DNFs by polynomial weight threshold-⊕ circuits [8], cannot be applied to AND-decision lists. A further result is that for all k ≥ 1 the complexity class defined by polynomial length AC 0 k -decision lists lies strictly between AC 0 k+1 and AC 0 k+2
Supported by DFG grant Kr 1521/3-2.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
N. Alon, J. Bruck. Explicite constructions of depth two majority circuits for comparison and addition. Techn. Report RJ 8300 (75661) IBM San Jose, 1991.
J. Aspnes, R. Beigel, M. Furst, S. Rudich. The expressive power of Voting Polynomials. Proc. STOC’91, 402–409.
J. Bruck. Harmonic Analysis of polynomial threshold functions. SIAM Journal of Discrete Mathematics. 3:22, 1990, pp. 168–177.
J. Bruck, R. Smolensky. Polynomial Threshold functions, AC0-functions, and spectral norms. Proc. of FOCS’90, 632–641.
M. Goldmann, J. Håstad, A. A. Razborov. Majority gates versus general weighted Threshold gates. J. Computational Complexity 2, 1992, 277–300.
J. Håstad. Almost optimal lower bounds for small depth circuits. STOC’86, pp. 6–20.
J. Jackson. An efficient membership-query algorithm for learning DNF with respect to the uniform distribution, FOCS’94, pp. 42–53.
M. Krause, P. Pudlak. On the computational power of depth-2 circuits with threshold and modulo gates. J. Theoretical Computer Science 174, 1997, pp. 137–156.Prel. version in STOC’94, pp. 49–59.
M. Krause, P. Pudlak. Computing Boolean functions by polynomials and threshold circuits. J. Comput. complex. 7 (1998), pp. 346–370. Prel. version in FOCS’95, pp. 682–691.
N. Linial, Y. Mansour, N. Nisan. Constant depth circuits, Fourier transform, and learnability. J. of the ACM, vol. 40(3), 1993, pp. 607–620. Prel. version in FOCS’89, pp. 574–579.
M. Minsky, S. Papert. Perceptrons. MIT Press, Cambridge 1988 (expanded edition, first edition 1968).
I. Wegener. Branching Programs and Binary Decision Diagrams. SIAM Monographs on Discrete Mathematics and Applications. Philadelphia 2000.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Krause, M. (2002). On the Computational Power of Boolean Decision Lists. In: Alt, H., Ferreira, A. (eds) STACS 2002. STACS 2002. Lecture Notes in Computer Science, vol 2285. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45841-7_30
Download citation
DOI: https://doi.org/10.1007/3-540-45841-7_30
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43283-8
Online ISBN: 978-3-540-45841-8
eBook Packages: Springer Book Archive