How Do Read-Once Formulae Shrink?

DOI10.1017/S0963548300001358MaRDI QIDQ4325332zbMATH OpenDBLPWikidataFDO

Authors Moshe Dubiner, Uri Zwick

Publication date 2 July 1995

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

Full work available at URL https://doi.org/10.1017/S0963548300001358

zbMATH Keywords

complexity of Boolean functionsexpected formula sizeexpected number of variableslower boundsrandom restrictionsread-once function

Mathematics Subject Classification ID

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

Recommendations

• Sums of read-once formulas: how many summands suffice?
• Sums of read-once formulas: how many summands are necessary?
• On the shrinkage exponent for read-once formulae
• Which formulae shrink under random restrictions?
• Amplification by Read-Once Formulas
• Sum of products of read-once formulas
• Learning read-once formulas with queries
• The effect of random restrictions on formula size
• Characterizing arithmetic read-once formulae

Cites work

• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 42045 (Why is no real title available?)
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Parity, circuits, and the polynomial-time hierarchy
• Reliable circuits using less reliable relays
• Short monotone formulae for the majority function
• Shrinkage of de Morgan formulae under restriction
• The effect of random restrictions on formula size

Cited in

(17)

• On the shrinkage exponent for read-once formulae
• Fourier concentration from shrinkage
• Mining circuit lower bound proofs for meta-algorithms
• Depth-independent lower bounds on the communication complexity of read-once Boolean formulas
• Amplification and percolation (probabilistic Boolean functions)
• Amplification by Read-Once Formulas
• The effect of random restrictions on formula size
• The number of Boolean functions computed by formulas of a given size
• On the complexity of computing a random Boolean function over the reals
• Local restrictions from the Furst-Saxe-Sipser paper
• On the Readability of Monotone Boolean Formulae
• Bounding the randomized decision tree complexity of read-once Boolean functions
• On transformations of probability distributions by read-once quasigroup formulae
• Which bases admit non-trivial shrinkage of formulae?
• Lower bounds on the randomized communication complexity of read-once functions
• Combinatorial characterization of read-once formulae
• Negation-limited formulas

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

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