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

DOI10.1016/J.DAM.2010.05.016zbMATH Open1247.06011OpenAlexW1863337174MaRDI QIDQ2275907FDOQ2275907

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

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

zbMATH Keywords

decision treecompetitive analysisBoolean functionsymmetric functionfunction evaluation

Mathematics Subject Classification ID

Boolean functions (06E30)

Cites Work

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

Cited In (2)

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

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)