Name
Abstract | ||
|---|---|---|
•Every multilinear n-variate polynomial can be expressed as the sum of ⌈3×2n−4⌉ Read-Once Polynomials ROPs.•There exist (non-explicit) multilinear n-variate polynomials needing Ω(2nn2) summands when expressed as sums of ROPs.•The polynomials Snn−1 cannot be written as the sum of any k ROPs if k<⌈n/2⌉.•Certain explicit 4-variate multilinear polynomials cannot be expressed as the sum of two ROPs. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.tcs.2017.10.019 | Theoretical Computer Science |
Keywords | Field | DocType |
Arithmetic formulas,Read-once polynomials,Hardness of representation | Discrete mathematics,Combinatorics,Polynomial,Upper and lower bounds,Multilinear polynomial,Multilinear map,Mathematics | Journal |
Volume | ISSN | Citations |
708 | 0304-3975 | 0 |
PageRank | References | Authors |
0.34 | 16 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Meena Mahajan | 1 | 688 | 56.90 |
| Anuj Tawari | 2 | 0 | 1.01 |