On the shrinkage exponent for read-once formulae

DOI10.1016/0304-3975(94)00081-SMaRDI QIDQ1367534zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Johan Hastad, Alexander Razborov, Andrew Chi-Chih Yao

Publication date 29 September 1997

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(94)00081-s

zbMATH Keywords

read-once de Morgan formula

Mathematics Subject Classification ID

Theory of computing (68Q99)

Recommendations

• Shrinkage of de Morgan formulae under restriction
• How Do Read-Once Formulae Shrink?
• The Shrinkage Exponent of de Morgan Formulas is 2

Cites work

• scientific article; zbMATH DE number 3162894 (Why is no real title available?)
• A method for obtaining more than quadratic effective lower estimates of complexity of schemes
• Amplification and percolation (probabilistic Boolean functions)
• Complexity of the realization of a linear function in the class of -circuits
• How Do Read-Once Formulae Shrink?
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• Parity, circuits, and the polynomial-time hierarchy
• Short monotone formulae for the majority function
• Shrinkage of de Morgan formulae under restriction
• The effect of random restrictions on formula size
• \(\Sigma_ 1^ 1\)-formulae on finite structures

Cited in

(8)

• Fourier concentration from shrinkage
• How Do Read-Once Formulae Shrink?
• Characterizing arithmetic read-once formulae
• Which formulae shrink under random restrictions?
• Negation-limited formulas
• On the Expressive Power of Read-Once Determinants
• An improved deterministic \#SAT algorithm for small De Morgan formulas
• Optimal explicit small-depth formulas for the coin problem

This page was built for publication: On the shrinkage exponent for read-once formulae

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