Which bases admit non-trivial shrinkage of formulae?

DOI10.1007/PL00001610zbMATH Open0988.06009OpenAlexW2092062896MaRDI QIDQ5957089FDOQ5957089

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

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

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)

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)