Name
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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-319-34171-2_19 | Electronic Colloquium on Computational Complexity (ECCC) |
DocType | Volume | ISSN |
Conference | abs/1603.02605 | 0302-9743 |
Citations | PageRank | References |
1 | 0.36 | 11 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Meena Mahajan | 1 | 688 | 56.90 |
| Anuj Tawari | 2 | 1 | 0.36 |