Which bases admit non-trivial shrinkage of formulae?

DOI10.1007/PL00001610MaRDI QIDQ5957089zbMATH OpenOpenAlexFDO

Authors Hana Chockler, Uri Zwick

Publication date 22 July 2002

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/pl00001610

zbMATH Keywords

Boolean functionsrandom restrictionsshrinkage exponentparity functionformula complexitynonlinear lower bounds

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Which formulae shrink under random restrictions?
• Shrinkage of de Morgan formulae under restriction
• Fourier concentration from shrinkage
• How Do Read-Once Formulae Shrink?
• On the complexity of realization of the linear function by formulas over finite Boolean bases

Cited in

(4)

• Fourier concentration from shrinkage
• Which formulae shrink under random restrictions?
• Formula complexity of a linear function in a \(k\)-ary basis
• Satisfiability algorithms and lower bounds for Boolean formulas over finite bases

This page was built for publication: Which bases admit non-trivial shrinkage of formulae?

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