On the shrinkage exponent for read-once formulae

DOI10.1016/0304-3975(94)00081-SzbMATH Open0884.68092DBLPjournals/tcs/HastadRY95OpenAlexW2078686944WikidataQ56959096 ScholiaQ56959096MaRDI QIDQ1367534FDOQ1367534

Andrew Chi-Chih Yao, Alexander Razborov, Johan Hastad

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

Recommendations

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

zbMATH Keywords

read-once de Morgan formula

Mathematics Subject Classification ID

Theory of computing (68Q99)

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Parity, circuits, and the polynomial-time hierarchy
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• Short monotone formulae for the majority function
• Title not available (Why is that?)
• The effect of random restrictions on formula size
• Shrinkage of de Morgan formulae under restriction
• 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
• Amplification and percolation (probabilistic Boolean functions)
• How Do Read-Once Formulae Shrink?

Cited In (7)

• 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
• 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)