Submodular goal value of Boolean functions

DOI10.1016/j.dam.2017.10.022zbMath1403.68340arXiv1702.04067OpenAlexW2963843195MaRDI QIDQ1701106

Devorah Kletenik, Jérémie Dusart, Eric Bach, Lisa Hellerstein

Publication date: 22 February 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

submodularityBoolean functionsread-once formulas

Mathematics Subject Classification ID

Boolean functions (06E30) Approximation algorithms (68W25) Boolean functions (94D10)

Related Items

Unnamed Item, Critical properties and complexity measures of read-once Boolean functions, The stochastic Boolean function evaluation problem for symmetric Boolean functions

Uses Software

• JBool
• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Evaluation of monotone DNF formulas
• On the dependence of functions on their variables
• Rank-\(r\) decision trees are a subclass of \(r\)-decision lists
• Learning decision trees from random examples
• A general lower bound on the number of examples needed for learning
• Complexity measures and decision tree complexity: a survey.
• Comments on the Proof of Adaptive Stochastic Set Cover Based on Adaptive Submodularity and Its Implications for the Group Identification Problem in “Group-Based Active Query Selection for Rapid Diagnosis in Time-Critical Situations”
• Approximation Algorithms for Stochastic Submodular Set Cover with Applications to Boolean Function Evaluation and Min-Knapsack
• On Asymptotic Estimates in Switching and Automata Theory