Diameter Versus Certificate Complexity of Boolean Functions

DOI10.4230/LIPICS.MFCS.2021.31OpenAlexW3195540944MaRDI QIDQ6168445

Anna Gál, Siddhesh Chaubal

Publication date: 8 August 2023

Full work available at URL: https://doi.org/10.4230/LIPIcs.MFCS.2021.31

zbMATH Keywords

Boolean functionsblock sensitivitycertificate complexitylog-rank conjecturesensitivity conjecturealternating number

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Boolean functions with a simple certificate for CNF complexity 👍 👎
• Certificate complexity of elementary symmetric Boolean functions 👍 👎
• On the Multiplicative Complexity of Boolean Functions 👍 👎
• Certificate complexity and symmetry of nested canalizing functions 👍 👎
• Sensitivity Versus Certificate Complexity of Boolean Functions 👍 👎
• On the modulo degree complexity of Boolean functions 👍 👎
• On the modulo degree complexity of Boolean functions 👍 👎

This page was built for publication: Diameter Versus Certificate Complexity of Boolean Functions

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