How Do Read-Once Formulae Shrink?
From MaRDI portal
Publication:4325332
DOI10.1017/S0963548300001358zbMath0815.06013WikidataQ60299186 ScholiaQ60299186MaRDI QIDQ4325332
Publication date: 2 July 1995
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
lower bounds; random restrictions; read-once function; complexity of Boolean functions; expected formula size; expected number of variables
Related Items
Negation-limited formulas, On the shrinkage exponent for read-once formulae, Fourier concentration from shrinkage
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