Submodular goal value of Boolean functions

DOI10.1016/J.DAM.2017.10.022MaRDI QIDQ1701106zbMATH OpenOpenAlexFDO

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

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

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

Abstract: Recently, Deshpande et al. introduced a new measure of the complexity of a Boolean function. We call this measure the "goal value" of the function. The goal value of $f$ is defined in terms of a monotone, submodular utility function associated with $f$. As shown by Deshpande et al., proving that a Boolean function $f$ has small goal value can lead to a good approximation algorithm for the Stochastic Boolean Function Evaluation problem for $f$. Also, if $f$ has small goal value, it indicates a close relationship between two other measures of the complexity of $f$, its average-case decision tree complexity and its average-case certificate complexity. In this paper, we explore the goal value measure in detail. We present bounds on the goal values of arbitrary and specific Boolean functions, and present results on properties of the measure. We compare the goal value measure to other, previously studied, measures of the complexity of Boolean functions. Finally, we discuss a number of open questions provoked by our work.

Recommendations

• Horn functions and submodular Boolean functions
• Submodular functions and optimization
• The expressive power of binary submodular functions
• The Expressive Power of Binary Submodular Functions
• Disjunctive analogues of submodular and supermodular pseudo-Boolean functions
• On submodular value functions and complex dynamic programming
• Submodular functions: optimization and approximation
• Submodular function minimization
• Submodular function minimization

Cites work

• scientific article; zbMATH DE number 5852793 (Why is no real title available?)
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 176870 (Why is no real title available?)
• A general lower bound on the number of examples needed for learning
• Adaptive submodularity: theory and applications in active learning and stochastic optimization
• Approximation algorithms for stochastic submodular set cover with applications to Boolean function evaluation and min-knapsack
• 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”
• Complexity measures and decision tree complexity: a survey.
• Evaluation of monotone DNF formulas
• Learning decision trees from random examples
• On Asymptotic Estimates in Switching and Automata Theory
• On the dependence of functions on their variables
• Rank-\(r\) decision trees are a subclass of \(r\)-decision lists

Cited in

(5)

• Critical properties and complexity measures of read-once Boolean functions
• Disjunctive analogues of submodular and supermodular pseudo-Boolean functions
• Evaluation of monotone DNF formulas
• The stochastic Boolean function evaluation problem for symmetric Boolean functions
• scientific article; zbMATH DE number 7378706 (Why is no real title available?)

Describes a project that uses

Uses Software

• JBool
• OEIS

This page was built for publication: Submodular goal value of Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1701106)