On the parity complexity measures of Boolean functions

Details On the parity complexity measures of Boolean functions On the parity complexity measures of Boolean functions

2010-04-03

arxiv.org/abs/1004.0436v1

Computer Science

Computational Complexity

submitted to TCS on 16-MAR-2009

Scientific paper

10.1016/j.tcs.2010.03.027

The parity decision tree model extends the decision tree model by allowing the computation of a parity function in one step. We prove that the deterministic parity decision tree complexity of any Boolean function is polynomially related to the non-deterministic complexity of the function or its complement. We also show that they are polynomially related to an analogue of the block sensitivity. We further study parity decision trees in their relations with an intermediate variant of the decision trees, as well as with communication complexity.

Affiliated with

Also associated with

No associations

Rating

On the parity complexity measures of Boolean functions 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 On the parity complexity measures of Boolean functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the parity complexity measures of Boolean functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-198682