On the shrinkage exponent for read-once formulae

DOI10.1016/0304-3975(94)00081-SzbMath0884.68092OpenAlexW2078686944WikidataQ56959096 ScholiaQ56959096MaRDI QIDQ1367534

Andrew Chi-Chih Yao, Alexander A. Razborov, Johan T. Håstad

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)

Related Items (2)

Fourier concentration from shrinkage ⋮ Negation-limited formulas

Cites Work

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

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