The stochastic Boolean function evaluation problem for symmetric Boolean functions

DOI10.1016/j.dam.2021.12.001OpenAlexW3211688262MaRDI QIDQ2065798

Lisa Hellerstein, Dimitrios Gkenosis, Nathaniel Grammel, Devorah Kletenik

Publication date: 13 January 2022

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

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

zbMATH Keywords

submodularityBoolean functionsapproximation algorithmssequential testing

Mathematics Subject Classification ID

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

Related Items

Algorithms for the unit-cost stochastic score classification problem

Cites Work

• Unnamed Item
• Unnamed Item
• Evaluation of monotone DNF formulas
• Heuristic least-cost computation of discrete classification functions with uncertain argument values
• An optimum testing algorithm for some symmetric coherent systems
• Submodular goal value of Boolean functions
• Sequential testing of complex systems: a review
• Diagnosing double regular systems
• Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case
• Minimum Latency Submodular Cover
• Optimal Testing Procedures for Special Structures of Coherent Systems
• 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
• Revisiting the Approximation Bound for Stochastic Submodular Cover
• A Tight Bound for Stochastic Submodular Cover