Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR15-204 | 23rd October 2017 14:44

Sums of read-once formulas: How many summands suffice?

RSS-Feed




Revision #2
Authors: Meena Mahajan, Anuj Tawari
Accepted on: 23rd October 2017 14:44
Downloads: 637
Keywords: 


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.



Changes to previous version:

Added an exponential lower bound over any field.


Revision #1 to TR15-204 | 11th March 2016 10:25

Sums of read-once formulas: How many summands suffice?





Revision #1
Authors: Meena Mahajan, Anuj Tawari
Accepted on: 11th March 2016 10:25
Downloads: 998
Keywords: 


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.


Paper:

TR15-204 | 14th December 2015 08:33

Sums of read-once formulas: How many summands suffice?





TR15-204
Authors: Meena Mahajan, Anuj Tawari
Publication: 14th December 2015 09:59
Downloads: 1112
Keywords: 


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.



ISSN 1433-8092 | Imprint