How Do Read-Once Formulae Shrink?

DOI10.1017/S0963548300001358zbMath0815.06013WikidataQ60299186 ScholiaQ60299186MaRDI QIDQ4325332

Uri Zwick, Moshe Dubiner

Publication date: 2 July 1995

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

zbMATH Keywords

lower boundsrandom restrictionsread-once functioncomplexity of Boolean functionsexpected formula sizeexpected number of variables

Mathematics Subject Classification ID

Combinatorial probability (60C05) Boolean functions (06E30)

Related Items (3)

On the shrinkage exponent for read-once formulae ⋮ Fourier concentration from shrinkage ⋮ Negation-limited formulas

Cites Work

• Unnamed Item
• Unnamed Item
• Short monotone formulae for the majority function
• Parity, circuits, and the polynomial-time hierarchy
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• The effect of random restrictions on formula size
• Shrinkage of de Morgan formulae under restriction
• Reliable circuits using less reliable relays

This page was built for publication: How Do Read-Once Formulae Shrink?