Critical properties and complexity measures of read-once Boolean functions
From MaRDI portal
Publication:2043436
DOI10.1007/s10472-021-09734-6zbMath1495.06007OpenAlexW3137466273MaRDI QIDQ2043436
Vadim V. Lozin, Mikhail Ju. Moshkov
Publication date: 2 August 2021
Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10472-021-09734-6
Analysis of algorithms and problem complexity (68Q25) Combinatorics of partially ordered sets (06A07) Boolean functions (06E30) Boolean functions (94D10)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On various nonlinearity measures for Boolean functions
- Combinatorial characterization of read-once formulae
- Graph minors. XX: Wagner's conjecture
- On a quasi-ordering on Boolean functions
- Graph minors. V. Excluding a planar graph
- On almost bad Boolean bases
- A characterization of nested canalyzing functions with maximum average sensitivity
- Graph parameters and Ramsey theory
- Submodular goal value of Boolean functions
- Linear read-once and related Boolean functions
- Complexity measures and decision tree complexity: a survey.
- Boolean minors
- Critical properties of graphs of bounded clique-width
- A Ramsey-type theorem for the matching number regarding connected graphs
- Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
- Characterizations of closed classes of Boolean functions in terms of forbidden subfunctions and Post classes
- Finiteness theorems in stochastic integer programming
- Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial \(k\)-trees
- On Fraissé's order type conjecture
- Graph classes with linear Ramsey numbers
- Linear Clique‐Width for Hereditary Classes of Cographs
- Subclasses of the separable permutations
- Sensitivity, Block Sensitivity, and Certificate Complexity of Unate Functions and Read-Once Functions
- Learning read-once formulas with queries
- Pattern occurrence statistics and applications to the Ramsey theory of unavoidable patterns
- Well‐quasi‐ordering and finite distinguishing number
- Transactions on Rough Sets III
- Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
- An interval graph is not a comparability graph
- An interval graph is a comparability graph
