Mahajan, Meena ; Tawari, Anuj (2018) Sums of read-once formulas: How many summands are necessary? Theoretical Computer Science, 708 . pp. 34-45. ISSN 0304-3975
Full text not available from this repository.
Official URL: http://doi.org/10.1016/j.tcs.2017.10.019
Related URL: http://dx.doi.org/10.1016/j.tcs.2017.10.019
Abstract
An arithmetic read-once formula (ROF) is a formula (circuit of fan-out 1) over +,* where each variable labels at most one leaf. Every multilinear polynomial can be expressed as the sum of (possibly exponentially many) ROFs. In this work, we prove, for certain multilinear polynomials, a tight lower bound on the number of summands in such an expression.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier B.V. |
| Keywords: | Arithmetic formulas; Read-once polynomials; Hardness of representation |
| ID Code: | 128009 |
| Deposited On: | 14 Oct 2022 11:28 |
| Last Modified: | 14 Oct 2022 11:28 |
Repository Staff Only: item control page
