Certificate complexity and symmetry of nested canalizing functions

DOI10.46298/DMTCS.6191MaRDI QIDQ5024675zbMATH OpenOpenAlexFDO

Authors Yuan Li, Frank Ingram, Huaming Zhang

Publication date 27 January 2022

Published in Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2001.09094, https://dmtcs.episciences.org/8754

zbMATH Keywords

Boolean functioncertificate complexitylayer structurenested canalizing functionpartial symmetrysensitivitysymmetry

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean functions (94D10)

Abstract: Boolean nested canalizing functions (NCFs) have important applications in molecular regulatory networks, engineering and computer science. In this paper, we study their certificate complexity. For both Boolean values $bin0,1$, we obtain a formula for $b$-certificate complexity and consequently, we develop a direct proof of the certificate complexity formula of an NCF. Symmetry is another interesting property of Boolean functions and we significantly simplify the proofs of some recent theorems about partial symmetry of NCFs. We also describe the algebraic normal form of $s$-symmetric NCFs. We obtain the general formula of the cardinality of the set of $n$-variable $s$-symmetric Boolean NCFs for $s=1,dots,n$. In particular, we enumerate the strongly asymmetric Boolean NCFs.

Recommendations

• Symmetry properties of nested canalyzing functions
• Maximal sensitivity of Boolean nested canalizing functions
• scientific article; zbMATH DE number 4035741
• Nested canalyzing, unate cascade, and polynomial functions
• A characterization of nested canalyzing functions with maximum average sensitivity

Cites work

• \(k\)th order symmetric SAC Boolean functions and bisecting binomial coefficients
• Algebraic Properties of Symmetric and Partially Symmetric Boolean Functions
• Balanced Symmetric Functions Over ${\hbox{GF}}(p)$
• Boolean nested canalizing functions: a comprehensive analysis
• CREW PRAM<scp>s</scp> and Decision Trees
• Diophantine Equations With Binomial Coefficients and Perturbations of Symmetric Boolean Functions
• Enumerating Boolean functions of cryptographic significance
• scientific article; zbMATH DE number 5296403 (Why is no real title available?)
• scientific article; zbMATH DE number 5370539 (Why is no real title available?)
• Maximal sensitivity of Boolean nested canalizing functions
• Maximum nonlinearity of symmetric Boolean functions on odd number of variables
• Multistate nested canalizing functions and their networks
• Nested canalyzing depth and network stability
• Nested canalyzing, unate cascade, and polynomial functions
• On Detecting Total or Partial Symmetry of Switching Functions
• On the bent Boolean functions that are symmetric
• On the correlation of symmetric functions
• Sensitivity vs. block sensitivity of Boolean functions
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
• Sensitivity, Block Sensitivity, and Certificate Complexity of Unate Functions and Read-Once Functions
• Stratification and enumeration of Boolean functions by canalizing depth
• Symmetric Boolean Functions
• Symmetric Boolean functions depending on an odd number of variables with maximum algebraic immunity
• Symmetry properties of nested canalyzing functions
• The influence of canalization on the robustness of Boolean networks
• The neural ring: an algebraic tool for analyzing the intrinsic structure of neural codes
• The number of multistate nested canalyzing functions
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

Cited in

(6)

• A characterization of nested canalyzing functions with maximum average sensitivity
• Certificate complexity of elementary symmetric Boolean functions
• Maximal sensitivity of Boolean nested canalizing functions
• Sensitivity, Block Sensitivity, and Certificate Complexity of Unate Functions and Read-Once Functions
• Symmetry properties of nested canalyzing functions
• Diameter Versus Certificate Complexity of Boolean Functions

This page was built for publication: Certificate complexity and symmetry of nested canalizing functions

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