Competitive Boolean Function Evaluation: Beyond Monotonicity, and the Symmetric Case

Details Competitive Boolean Function Evaluation: Beyond Monotonicity, and the Symmetric Case Competitive Boolean Function Evaluation: Beyond Monotonicity, and the Symmetric Case

2010-06-21

arxiv.org/abs/1006.4136v1

Computer Science

Data Structures and Algorithms

15 pages, 1 figure, to appear in Discrete Applied Mathematics

Scientific paper

10.1016/j.dam.2010.05.016

We study the extremal competitive ratio of Boolean function evaluation. We provide the first non-trivial lower and upper bounds for classes of Boolean functions which are not included in the class of monotone Boolean functions. For the particular case of symmetric functions our bounds are matching and we exactly characterize the best possible competitiveness achievable by a deterministic algorithm. Our upper bound is obtained by a simple polynomial time algorithm.

Affiliated with

Also associated with

No associations

Rating

Competitive Boolean Function Evaluation: Beyond Monotonicity, and the Symmetric Case does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Competitive Boolean Function Evaluation: Beyond Monotonicity, and the Symmetric Case, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Competitive Boolean Function Evaluation: Beyond Monotonicity, and the Symmetric Case will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-602028