Certificate complexity and symmetry of nested canalizing functions

DOI10.46298/dmtcs.6191zbMath1492.94250arXiv2001.09094OpenAlexW3214845160MaRDI QIDQ5024675

Frank Ingram, Yuan Li, Huaming Zhang

Publication date: 27 January 2022

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

Full work available at URL: https://arxiv.org/abs/2001.09094

zbMATH Keywords

sensitivitysymmetryBoolean functionnested canalizing functionpartial symmetrycertificate complexitylayer structure

Mathematics Subject Classification ID

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

Cites Work

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