Abstract
An arithmetic read-once formula (ROF) is a formula (circuit of fan-out 1) over \(+, \times \) where each variable labels at most one leaf. Every multilinear polynomial can be expressed as the sum of ROFs. In this work, we prove, for certain multilinear polynomials, a tight lower bound on the number of summands in such an expression.
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
Similar content being viewed by others
Notes
- 1.
A polynomial is multilinear if the individual degree of each variable is at most one.
References
Anderson, M., van Melkebeek, D., Volkovich, I.: Deterministic polynomial identity tests for multilinear bounded-read formulae. Comput. Complex. 24(4), 695–776 (2015)
Bshouty, D., Bshouty, N.H.: On interpolating arithmetic read-once formulas with exponentiation. J. Comput. Syst. Sci. 56(1), 112–124 (1998)
Bshouty, N.H., Cleve, R.: Interpolating arithmetic read-once formulas in parallel. SIAM J. Comput. 27(2), 401–413 (1998)
Bshouty, N.H., Hancock, T.R., Hellerstein, L.: Learning boolean read-once formulas over generalized bases. J. Comput. Syst. Sci. 50(3), 521–542 (1995)
Hancock, T.R., Hellerstein, L.: Learning read-once formulas over fields and extended bases. In: Warmuth, M.K., Valiant, L.G. (eds.) Proceedings of the Fourth Annual Workshop on Computational Learning Theory, COLT 1991, Santa Cruz, California, USA, 5–7 August 1991, pp. 326–336. Morgan Kaufmann (1991)
Kabanets, V., Impagliazzo, R.: Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complex. 13(1–2), 1–46 (2004)
Kayal, N., Koiran, P., Pecatte, T., Saha, C.: Lower bounds for sums of powers of low degree univariates. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015, Part I. LNCS, vol. 9134, pp. 810–821. Springer, Heidelberg (2015)
Raz, R.: Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM 56(2), 1–17 (2009)
Shpilka, A., Volkovich, I.: On reconstruction and testing of read-once formulas. Theor. Comput. 10, 465–514 (2014)
Shpilka, A., Volkovich, I.: Read-once polynomial identity testing. Comput. Complex. 24(3), 477–532 (2015). (combines results from papers in RANDOM 2009 and STOC 2008)
Volkovich, I.: Characterizing arithmetic read-once formulae. ACM Trans. Comput. Theor. 8(1), 2:1–2:19 (2016)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Mahajan, M., Tawari, A. (2016). Sums of Read-Once Formulas: How Many Summands Suffice?. In: Kulikov, A., Woeginger, G. (eds) Computer Science – Theory and Applications. CSR 2016. Lecture Notes in Computer Science(), vol 9691. Springer, Cham. https://doi.org/10.1007/978-3-319-34171-2_19
Download citation
DOI: https://doi.org/10.1007/978-3-319-34171-2_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-34170-5
Online ISBN: 978-3-319-34171-2
eBook Packages: Computer ScienceComputer Science (R0)