Submodular goal value of Boolean functions
| Autor: | Devorah Kletenik, Lisa Hellerstein, Eric Bach, Jérémie Dusart |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
FOS: Computer and information sciences
Discrete mathematics Discrete Mathematics (cs.DM) Applied Mathematics Decision tree Approximation algorithm 0102 computer and information sciences 02 engineering and technology Function (mathematics) 01 natural sciences Measure (mathematics) Submodular set function Monotone polygon 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics 020201 artificial intelligence & image processing Boolean function Value (mathematics) Computer Science - Discrete Mathematics Mathematics |
| Zdroj: | Discrete Applied Mathematics. 238:1-13 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2017.10.022 |
| Popis: | 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 suggested by our work. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect