Algorithms for Boolean Function Query Properties
<|reference_start|>Algorithms for Boolean Function Query Properties: 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.<|reference_end|>
@article{aaronson2001algorithms,
    title={Algorithms for Boolean Function Query Properties},
    author={Scott Aaronson (UC Berkeley)},
    journal={arXiv preprint arXiv:cs/0107010},
    year={2001},
    archivePrefix={arXiv},
    eprint={cs/0107010},
    primaryClass={cs.CC cs.DS}
}