Critical properties and complexity measures of read-once Boolean functions
type: Item
instance of: scholarly article
title: Critical properties and complexity measures of read-once Boolean functions
zbMATH Open document ID: 1495.06007
author: Vadim Lozin
author: Mikhail Moshkov
published in: Annals of Mathematics and Artificial Intelligence
publication date: 2021-08-02T00:00:00Z
Mathematics Subject Classification ID: 06E30
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 94D10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7377239
zbMATH Keywords: read-once Boolean function
zbMATH Keywords: certificate complexity
zbMATH Keywords: well-quasi-ordering
describes a project that uses: JBool
MaRDI profile type: Publication
full work available at URL: s10472-021-09734-6
OpenAlex ID: W3137466273
cites work: Subclasses of the separable permutations
cites work: Learning read-once formulas with queries
cites work: Finiteness theorems in stochastic integer programming
cites work: Well‐quasi‐ordering and finite distinguishing number
cites work: Submodular goal value of Boolean functions
cites work: Graph classes with linear Ramsey numbers
cites work: On various nonlinearity measures for Boolean functions
cites work: Linear Clique‐Width for Hereditary Classes of Cographs
cites work: Complexity measures and decision tree complexity: a survey.
cites work: A Ramsey-type theorem for the matching number regarding connected graphs
cites work: On a quasi-ordering on Boolean functions
cites work: Q3077976
cites work: An interval graph is not a comparability graph
cites work: Q4625695
cites work: Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees
cites work: Q3666625
cites work: Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
cites work: An interval graph is a comparability graph
cites work: Combinatorial characterization of read-once formulae
cites work: Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
cites work: On Fraissé's order type conjecture
cites work: Graph parameters and Ramsey theory
cites work: Critical properties of graphs of bounded clique-width
cites work: Linear read-once and related Boolean functions
cites work: Sensitivity, Block Sensitivity, and Certificate Complexity of Unate Functions and Read-Once Functions
cites work: Q4327609
cites work: Transactions on Rough Sets III
cites work: Q5520569
cites work: Graph minors. V. Excluding a planar graph
cites work: Graph minors. XX: Wagner's conjecture
cites work: A characterization of nested canalyzing functions with maximum average sensitivity
cites work: On almost bad Boolean bases
cites work: Pattern occurrence statistics and applications to the Ramsey theory of unavoidable patterns
cites work: Boolean minors
cites work: Characterizations of closed classes of Boolean functions in terms of forbidden subfunctions and Post classes
DOI: 10.1007/S10472-021-09734-6
Recommended article: Q5150421
Recommended article: Read-Once Functions Revisited and the Readability Number of a Boolean Function
Recommended article: On the complexity of restrictions of Boolean functions
Recommended article: On the parity complexity measures of Boolean functions
Recommended article: The complexity of Boolean functions in different characteristics
Recommended article: On complexity of a particular Boolean functions class
Recommended article: Q3762226
Recommended article: Q4036699
Recommended article: On the Multiplicative Complexity of Boolean Functions
Recommended article: On estimates on the complexity of restrictions of Boolean functions
description: scientific article; zbMATH DE number 7377239