Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case
From MaRDI portal
Publication:2275907
DOI10.1016/j.dam.2010.05.016zbMath1247.06011MaRDI QIDQ2275907
Ferdinando Cicalese, Martin Milanič, Travis Gagie, Eduardo Sany Laber
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
06E30: Boolean functions
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Competitive evaluation of threshold functions in the priced information model
- Combinatorial characterization of read-once formulae
- Randomized vs. deterministic decision tree complexity for read-once Boolean functions
- Query strategies for priced information
- Lower bounds on probabilistic linear decision trees
- Selection of relevant features and examples in machine learning
- On read-once threshold formulae and their randomized decision tree complexity
- Diagnosing double regular systems
- Discrete Mathematics of Neural Networks
- Function Evaluation Via Linear Programming in the Priced Information Model
- Two applications of information complexity
- A new strategy for querying priced information
- Learning with attribute costs
- Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
- How to assign votes in a distributed system
- Disjoint Products and Efficient Computation of Reliability
- Bounds to Complexities of Networks for Sorting and for Switching
- A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives
- On the competitive ratio of evaluating priced functions
