Sums of Read-Once Formulas: How Many Summands Suffice?
| Autor: | Anuj Tawari, Meena Mahajan |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
Multilinear map 020206 networking & telecommunications Multilinear polynomial 0102 computer and information sciences 02 engineering and technology Expression (computer science) 01 natural sciences Upper and lower bounds Combinatorics 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Variable (mathematics) Mathematics |
| Zdroj: | Computer Science – Theory and Applications ISBN: 9783319341705 CSR |
| DOI: | 10.1007/978-3-319-34171-2_19 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|