Algorithms for Boolean Function Query Properties

DOI10.1137/S0097539700379644MaRDI QIDQ4429679zbMATH OpenOpenAlexFDO

Authors Scott Aaronson

Publication date 28 September 2003

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539700379644

zbMATH Keywords

algorithmBoolean functionquantum computationquery complexitytruth table

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) General topics in the theory of algorithms (68W01) Quantum computation (81P68)

Recommendations

• Publication:4828947
• scientific article; zbMATH DE number 2247114
• Graph-Based Algorithms for Boolean Function Manipulation
• scientific article; zbMATH DE number 5852793
• Learning Boolean functions with queries
• scientific article; zbMATH DE number 4083547
• scientific article; zbMATH DE number 33712
• Computational complexity of Boolean functions
• Fast computing the algebraic degree of Boolean functions
• Boolean algebra approximations

Cited in

(7)

• An efficient algorithm for calculating Boolean difference
• Nondeterministic query algorithms
• Quantum query algorithms for conjunctions
• scientific article; zbMATH DE number 4083547 (Why is no real title available?)
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• The hardness of decision tree complexity
• Spectral algorithms in higher-order Fourier analysis

This page was built for publication: Algorithms for Boolean Function Query Properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4429679)