Which bases admit non-trivial shrinkage of formulae?

DOI10.1007/PL00001610zbMath0988.06009OpenAlexW2092062896MaRDI QIDQ5957089

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 functionsparity functionformula complexitynonlinear lower boundsrandom restrictionsshrinkage exponent

Mathematics Subject Classification ID

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

Related Items (2)

Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases ⋮ Formula complexity of a linear function in a \(k\)-ary basis

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