On the depth complexity of formulas

DOI10.1007/BF01744302MaRDI QIDQ3890111zbMATH OpenOpenAlexFDO

Authors Eli Shamir, Marc Snir

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

algebraic systemarithmetic computationscomputations over finite languagesdepth complexity of formulaslower bounds

Mathematics Subject Classification ID

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

Cites work

• Bounds to Complexities of Networks for Sorting and for Switching
• Computational Complexity and Numerical Stability
• Computer Search for Numerical Instability
• Fast Parallel Matrix Inversion Algorithms
• scientific article; zbMATH DE number 3182201 (Why is no real title available?)
• scientific article; zbMATH DE number 3637282 (Why is no real title available?)
• scientific article; zbMATH DE number 3328173 (Why is no real title available?)
• On the Parallel Evaluation of Multivariate Polynomials
• Restructuring of Arithmetic Expressions For Parallel Evaluation
• Size-depth tradeoff in monotone Boolean formulae
• Size-depth tradeoff in non-monotone Boolean formulae
• The circuit depth of symmetric Boolean functions
• The complexity of computing the permanent
• The covering problem of complete uniform hypergraphs
• The Depth of All Boolean Functions

Cited in

(19)

• Lower bounds on monotone arithmetic circuits with restricted depths
• A lower bound for monotone arithmetic circuits computing \(0-1\) permanent
• 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 arithmetic circuits via partial derivatives
• On \(\epsilon\)-sensitive monotone computations
• Tropical complexity, Sidon sets, and dynamic programming
• Lower bounds for monotone counting circuits
• Formulas versus Circuits for Small Distance Connectivity
• Lower bounds for tropical circuits and dynamic programs
• On a relation between the depth and complexity of monotone Boolean formulas
• Regular expression length via arithmetic formula complexity
• Shadows of Newton polytopes
• Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
• Homogeneous formulas and symmetric polynomials
• Monotone classes beyond VNP
• Notes on Boolean read-k and multilinear circuits
• Monotone classes beyond VNP
• Monotone separations for constant degree polynomials

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

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