Algorithms for Boolean Function Query Properties

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
13 pages, no figures, earlier version submitted to SIAM J. Comp

Keywords

Computational Complexity, Data Structures and Algorithms, F.1.2; F.1.3; F.2.2

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/30682

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0107010
 http://arxiv.org/abs/cs/0107010

Collections

arXiv