On the depth complexity of formulas

DOI10.1007/BF01744302zbMath0445.68031OpenAlexW2033773511MaRDI QIDQ3890111

Marc Snir, Eli Shamir

Publication date: 1980

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01744302

zbMATH Keywords

lower boundsalgebraic systemarithmetic computationscomputations over finite languagesdepth complexity of formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Lower bounds for monotone counting circuits ⋮ Formulas versus Circuits for Small Distance Connectivity ⋮ Lower bounds on arithmetic circuits via partial derivatives ⋮ On a relation between the depth and complexity of monotone Boolean formulas ⋮ Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors ⋮ Shadows of Newton polytopes ⋮ On \(\epsilon\)-sensitive monotone computations ⋮ Homogeneous formulas and symmetric polynomials ⋮ Lower bounds for tropical circuits and dynamic programs ⋮ Monotone separations for constant degree polynomials ⋮ Regular expression length via arithmetic formula complexity ⋮ A lower bound for monotone arithmetic circuits computing \(0-1\) permanent ⋮ Tropical Complexity, Sidon Sets, and Dynamic Programming ⋮ Lower bounds on the depth of monotone arithmetic computations ⋮ A direct version of Shamir and Snir's lower bounds on monotone circuit depth ⋮ Lower bounds on monotone arithmetic circuits with restricted depths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Size-depth tradeoff in non-monotone Boolean formulae
• The circuit depth of symmetric Boolean functions
• Size-depth tradeoff in monotone Boolean formulae
• The covering problem of complete uniform hypergraphs
• Computational Complexity and Numerical Stability
• Bounds to Complexities of Networks for Sorting and for Switching
• Restructuring of Arithmetic Expressions For Parallel Evaluation
• Computer Search for Numerical Instability
• Fast Parallel Matrix Inversion Algorithms
• The Depth of All Boolean Functions
• On the Parallel Evaluation of Multivariate Polynomials

This page was built for publication: On the depth complexity of formulas