Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case

DOI10.1016/J.DAM.2010.05.016MaRDI QIDQ2275907zbMATH OpenOpenAlexFDO

Authors Ferdinando Cicalese, Travis Gagie, Eduardo S. Laber, Martin Milanič

Publication date 10 August 2011

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

Full work available at URL https://doi.org/10.1016/j.dam.2010.05.016

zbMATH Keywords

decision treecompetitive analysisBoolean functionsymmetric functionfunction evaluation

Mathematics Subject Classification ID

Boolean functions (06E30)

Recommendations

• On the competitive ratio of evaluating priced functions
• Function Evaluation Via Linear Programming in the Priced Information Model
• Algorithms – ESA 2005
• Competitive evaluation of threshold functions in the priced information model
• A new strategy for querying priced information

Cites work

• scientific article; zbMATH DE number 1599890 (Why is no real title available?)
• 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 4035741 (Why is no real title available?)
• scientific article; zbMATH DE number 3278279 (Why is no real title available?)
• A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives
• A new strategy for querying priced information
• Bounds to Complexities of Networks for Sorting and for Switching
• Combinatorial characterization of read-once formulae
• Competitive evaluation of threshold functions in the priced information model
• Diagnosing double regular systems
• Discrete mathematics of neural networks. Selected topics
• Disjoint Products and Efficient Computation of Reliability
• Function Evaluation Via Linear Programming in the Priced Information Model
• How to assign votes in a distributed system
• Learning with attribute costs
• Lower bounds on probabilistic linear decision trees
• On read-once threshold formulae and their randomized decision tree complexity
• On the competitive ratio of evaluating priced functions
• Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
• Query strategies for priced information
• Randomized vs. deterministic decision tree complexity for read-once Boolean functions
• Selection of relevant features and examples in machine learning
• Two applications of information complexity

Cited in

(2)

• The stochastic Boolean function evaluation problem for symmetric Boolean functions
• Evaluation of monotone DNF formulas

Describes a project that uses

Uses Software

• JBool

This page was built for publication: Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case

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