Algorithms for Boolean Function Query Properties

Details Algorithms for Boolean Function Query Properties Algorithms for Boolean Function Query Properties

2001-07-05

arxiv.org/abs/cs/0107010v1

Computer Science

Computational Complexity

13 pages, no figures, earlier version submitted to SIAM J. Comp

Scientific paper

We present new algorithms to compute fundamental properties of a Boolean function given in truth-table form. Specifically, we give an O(N^2.322 log N) algorithm for block sensitivity, an O(N^1.585 log N) algorithm for `tree decomposition,' and an O(N) algorithm for `quasisymmetry.' These algorithms are based on new insights into the structure of Boolean functions that may be of independent interest. We also give a subexponential-time algorithm for the space-bounded quantum query complexity of a Boolean function. To prove this algorithm correct, we develop a theory of limited-precision representation of unitary operators, building on work of Bernstein and Vazirani.

Affiliated with

Also associated with

No associations

Rating

Algorithms for Boolean Function Query Properties 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 Algorithms for Boolean Function Query Properties, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithms for Boolean Function Query Properties will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-652396