Lower bounds for Sum and Sum of Products of Read-once Formulas

DOI10.1145/3313232zbMath1485.68095OpenAlexW2926912675WikidataQ128097886 ScholiaQ128097886MaRDI QIDQ5205795

B. V. Raghavendra Rao, C. Ramya

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

lower boundsalgebraic complexity theoryarithmetic formulas

Mathematics Subject Classification ID

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

Related Items (2)

Lower bounds for special cases of syntactic multilinear ABPs ⋮ Limitations of sums of bounded read formulas and ABPs

This page was built for publication: Lower bounds for Sum and Sum of Products of Read-once Formulas