Algorithms for Boolean Function Query Properties
| dc.creator | Aaronson, Scott | |
| dc.date | 2001-07-05 | |
| dc.date.accessioned | 2026-07-07T03:17:19Z | |
| dc.date.available | 2026-07-07T03:17:19Z | |
| dc.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. | |
| dc.description | 13 pages, no figures, earlier version submitted to SIAM J. Comp | |
| dc.identifier | https://arxiv.org/abs/cs/0107010 | |
| dc.identifier | http://arxiv.org/abs/cs/0107010 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/30682 | |
| dc.subject | Computational Complexity | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | F.1.2; F.1.3; F.2.2 | |
| dc.title | Algorithms for Boolean Function Query Properties | |
| dc.type | text |