Algorithms for Boolean function query properties

We investigate efficient algorithms for computing Boolean function properties relevant to query complexity. Such properties include, for example, deterministic, randomized, and quantum query complexities; block sensitivity; certificate complexity; and degree as a real polynomial. The algorithms compute the properties, given an n-variable function's truth table (of size N = 2(n)) as input. Our main results are the following: - O(N log(2) (3) log N) algorithms for many common properties, - an O(Nlog(2) (5) log N) algorithm for block sensitivity, - an O( N) algorithm for testing ``quasi symmetry,{''} - a notion of a `` tree decomposition{''} of a Boolean function, proof that the decomposition is unique, and an O(N log(2) (3) log N) algorithm for finding it, - a subexponential-time approximation algorithm for space-bounded quantum query complexity. To develop this algorithm, we give a new way to search systematically through unitary matrices using finite-precision arithmetic. The algorithms discussed have been implemented in a linkable library.