Lower bounds for sum and sum of products of read-once formulas

DOI10.1145/3313232MaRDI QIDQ5205795zbMATH OpenOpenAlexWikidataFDO

Authors C. Ramya, B. V. Raghavendra Rao

Publication date 16 December 2019

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3313232

zbMATH Keywords

algebraic complexity theoryarithmetic formulaslower bounds

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Sum of products of read-once formulas
• Sums of read-once formulas: how many summands suffice?
• Sums of read-once formulas: how many summands are necessary?
• Arithmetic circuit lower bounds via MaxRank
• Arithmetic circuit lower bounds via maximum-rank of partial derivative matrices

Cited in

(6)

• Sums of read-once formulas: how many summands are necessary?
• Limitations of sums of bounded read formulas and ABPs
• Sum of products of read-once formulas
• Sums of read-once formulas: how many summands suffice?
• Lower bounds for special cases of syntactic multilinear ABPs
• Towards identity testing for sums of products of Read-once and multilinear bounded-Read formulae

This page was built for publication: Lower bounds for sum and sum of products of read-once formulas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5205795)