Size-Depth Tradeoffs for Algebraic Formulas

DOI10.1137/S0097539792232586MaRDI QIDQ4852620zbMATH OpenFDO

Authors Nader H. Bshouty, Richard Cleve, Wayne Eberly

Publication date 1 November 1995

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539792232586

zbMATH Keywords

parallel computation

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Symbolic computation and algebraic computation (68W30)

Recommendations

• Size-depth tradeoffs for Boolean formulae
• Tensor-rank and lower bounds for arithmetic formulas
• Types of depth and formula size
• Size-depth trade-offs for monotone arithmetic circuits
• A quadratic size-hierarchy theorem for small-depth multilinear formulas

Cited in

(11)

• Size-depth tradeoffs for Boolean formulae
• Constructing small tree grammars and small circuits for formulas
• Space saving by dynamic algebraization based on tree-depth
• A generalization of Spira's theorem and circuits with small segregators or separators
• Types of depth and formula size
• A generalization of Spira's theorem and circuits with small segregators or separators
• Span-program-based quantum algorithm for evaluating unbalanced formulas
• Random arithmetic formulas can be reconstructed efficiently
• The limits of depth reduction for arithmetic formulas
• Towards optimal simulations of formulas by bounded-width programs
• Title not available (Why is no real title available?)

This page was built for publication: Size-Depth Tradeoffs for Algebraic Formulas

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