2001/07/05 by Scott Aaronson, Aaronson, Scott
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #F.1.2 #F.1.3 #F.2.2 #FOS: Computer and information sciences #Quantum Computing Algorithms and Architecture #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0107010
13 pages, no figures, earlier version submitted to SIAM J. Comp
arxiv created 2001/07/05 · openalex publication_date 2001/07/05 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present new algorithms to compute fundamental properties of a Boolean function given in truth-table form. Specifically, we give an O(N2.322 log N) algorithm for block sensitivity, an O(N1.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.