The stochastic Boolean function evaluation problem for symmetric Boolean functions

DOI10.1016/J.DAM.2021.12.001MaRDI QIDQ2065798zbMATH OpenOpenAlexFDO

Authors Dimitrios Gkenosis, Nathaniel Grammel, Lisa Hellerstein, 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

approximation algorithmssubmodularityBoolean functionssequential testing

Mathematics Subject Classification ID

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

Recommendations

• Evaluation of monotone DNF formulas
• Approximation algorithms for stochastic Boolean function evaluation and stochastic submodular set cover
• Approximation algorithms for stochastic submodular set cover with applications to Boolean function evaluation and min-knapsack
• Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case
• Submodular goal value of Boolean functions

Cites work

• scientific article; zbMATH DE number 7378706 (Why is no real title available?)
• A Tight Bound for Stochastic Submodular Cover
• Adaptive submodularity: theory and applications in active learning and stochastic optimization
• An optimum testing algorithm for some symmetric coherent systems
• 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”
• Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case
• Diagnosing double regular systems
• Evaluation of monotone DNF formulas
• Heuristic least-cost computation of discrete classification functions with uncertain argument values
• Optimal Testing Procedures for Special Structures of Coherent Systems
• Revisiting the approximation bound for stochastic submodular cover
• Sequential testing of complex systems: a review
• Submodular goal value of Boolean functions

Cited in

(5)

• Algorithms for the unit-cost stochastic score classification problem
• Simple algorithms for stochastic score classification with small approximation ratios
• A New Algorithm for Complex Stochastic Boolean Systems
• Some problems of spectral analysis of random Boolean functions with constraints
• scientific article; zbMATH DE number 5022109 (Why is no real title available?)

This page was built for publication: The stochastic Boolean function evaluation problem for symmetric Boolean functions

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