Certificate complexity of elementary symmetric Boolean functions

DOI10.1016/j.tcs.2022.09.034OpenAlexW4300981118MaRDI QIDQ2089681

Yanyan Li

Publication date: 24 October 2022

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.09.034

zbMATH Keywords

certificate complexityelementary symmetric Boolean function

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Boolean nested canalizing functions: a comprehensive analysis
• Asymptotic behavior of perturbations of symmetric functions
• Block sensitivity of minterm-transitive functions
• The critical complexity of graph properties
• A divisibility approach to the open boundary cases of Cusick-Li-Stǎnicǎ's conjecture
• Enumerating Boolean functions of cryptographic significance
• On the bent Boolean functions that are symmetric
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
• Sensitivity vs. block sensitivity of Boolean functions
• Sensitivities and block sensitivities of elementary symmetric Boolean functions
• Maximal sensitivity of Boolean nested canalizing functions
• Block sensitivity of weakly symmetric functions
• Recent Results on Balanced Symmetric Boolean Functions
• A Note on a Conjecture for Balanced Elementary Symmetric Boolean Functions
• Symmetric Boolean Functions
• Symmetric Boolean functions depending on an odd number of variables with maximum algebraic immunity
• On a conjecture for balanced symmetric Boolean functions
• Balanced Symmetric Functions Over ${\hbox{GF}}(p)$
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• 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
• The Degree of Balanced Elementary Symmetric Boolean Functions of <formula formulatype="inline"> <tex Notation="TeX">${{\bf 4k}+{\bf 3}}$</tex> </formula> Variables
• On Detecting Total or Partial Symmetry of Switching Functions
• Algebraic Properties of Symmetric and Partially Symmetric Boolean Functions

This page was built for publication: Certificate complexity of elementary symmetric Boolean functions