Complexity measures and decision tree complexity: a survey.

DOI10.1016/S0304-3975(01)00144-XzbMath1061.68058OpenAlexW2012496360MaRDI QIDQ1853508

Ronald de Wolf, Harry Buhrman

Publication date: 21 January 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00144-x

zbMATH Keywords

Quantum computingRandomized computingComplexity measures for Boolean functionsDecision tree complexity

Mathematics Subject Classification ID

Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (only showing first 100 items - show all)

An Optimal Separation of Randomized and Quantum Query Complexity ⋮ Deterministic quantum search with adjustable parameters: implementations and applications ⋮ Quantum attribute-based encryption: a comprehensive study ⋮ Performance of Grover's search algorithm with diagonalizable collective noises ⋮ Lifting query complexity to time-space complexity for two-way finite automata ⋮ Quantum algorithm for lexicographically minimal string rotation ⋮ Near-optimal quantum algorithms for string problems ⋮ Unnamed Item ⋮ New degree bounds for polynomial threshold functions ⋮ Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems ⋮ Quadratically tight relations for randomized query complexity ⋮ A tighter relation between sensitivity complexity and certificate complexity ⋮ On the degree of univariate polynomials over the integers ⋮ The simplified weighted sum function and its average sensitivity ⋮ On the modulo degree complexity of Boolean functions ⋮ On the relationship between energy complexity and other Boolean function measures ⋮ Sensitivity, affine transforms and quantum communication complexity ⋮ Tight bounds on sensitivity and block sensitivity of some classes of transitive functions ⋮ A lower bound on the quantum query complexity of read-once functions ⋮ On the Decision Tree Complexity of Threshold Functions ⋮ A characterization of nested canalyzing functions with maximum average sensitivity ⋮ The complexity of the certification of properties of stable marriage ⋮ A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs ⋮ An adaptivity hierarchy theorem for property testing ⋮ Query Complexity in Expectation ⋮ Low-Sensitivity Functions from Unambiguous Certificates. ⋮ Alternation, sparsity and sensitivity: bounds and exponential gaps ⋮ Planar random-cluster model: scaling relations ⋮ Time-Space Complexity Advantages for Quantum Computing ⋮ A note on the size of minimal covers ⋮ QUANTUM QUERY COMPLEXITY OF CONSTANT-SIZED SUBGRAPH CONTAINMENT ⋮ Block sensitivity of weakly symmetric functions ⋮ Quantum query as a state decomposition ⋮ Totally optimal decision trees for Boolean functions ⋮ Communication Lower Bounds via Critical Block Sensitivity ⋮ Quantum query complexity of almost all functions with fixed on-set size ⋮ Deterministic Communication vs. Partition Number ⋮ A strong direct product theorem for quantum query complexity ⋮ Forrelation: A Problem That Optimally Separates Quantum from Classical Computing ⋮ A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length ⋮ Optimal separation in exact query complexities for Simon's problem ⋮ Optimal parallel quantum query algorithms ⋮ Nonadaptive quantum query complexity ⋮ All Classical Adversary Methods are Equivalent for Total Functions ⋮ From Quantum Query Complexity to State Complexity ⋮ Quantum and classical query complexities for generalized Simon's problem ⋮ Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma ⋮ Quantum and classical query complexities for generalized Deutsch-Jozsa problems ⋮ Time and space complexity of deterministic and nondeterministic decision trees ⋮ Optimal direct sum results for deterministic and randomized decision tree complexity ⋮ Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) ⋮ On the average sensitivity of the weighted sum function ⋮ Exponential lower bound for bounded depth circuits with few threshold gates ⋮ From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm ⋮ Minterm-transitive functions with asymptotically smallest block sensitivity ⋮ Sensitivity versus block sensitivity of Boolean functions ⋮ Parity decision tree in classical-quantum separations for certain classes of Boolean functions ⋮ Submodular goal value of Boolean functions ⋮ Composition limits and separating examples for some Boolean function complexity measures ⋮ Query-to-Communication Lifting for BPP ⋮ Extension Complexity of Independent Set Polytopes ⋮ Unbounded-error quantum query complexity ⋮ Generalizations of the distributed Deutsch–Jozsa promise problem ⋮ On the resolution of the sensitivity conjecture ⋮ Sharp phase transition for the random-cluster and Potts models via decision trees ⋮ Weak derandomization of weak algorithms: explicit versions of Yao's lemma ⋮ Separation Between Deterministic and Randomized Query Complexity ⋮ Revisiting Deutsch-Jozsa algorithm ⋮ Conflict complexity is lower bounded by block sensitivity ⋮ Secure and highly-available aggregation queries in large-scale sensor networks via set sampling ⋮ Quantum decision tree classifier ⋮ How low can approximate degree and quantum query complexity be for total Boolean functions? ⋮ On the power of non-adaptive learning graphs ⋮ A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function ⋮ Fourier 1-norm and quantum speed-up ⋮ Non-interactive proofs of proximity ⋮ On block sensitivity and fractional block sensitivity ⋮ Quantum algorithms on Walsh transform and Hamming distance for Boolean functions ⋮ Quantum certificate complexity ⋮ Minimization of decision trees is hard to approximate ⋮ Improved direct product theorems for randomized query complexity ⋮ An asymptotically tight bound on the number of relevant variables in a bounded degree Boolean function ⋮ Sensitivity Versus Certificate Complexity of Boolean Functions ⋮ An improved lower bound on the sensitivity complexity of graph properties ⋮ Polynomial degree vs. quantum query complexity ⋮ On the structure of Boolean functions with small spectral norm ⋮ On the parity complexity measures of Boolean functions ⋮ On the power of Ambainis lower bounds ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Superlinear Advantage for Exact Quantum Algorithms ⋮ Decision trees based on 1-consequences ⋮ Critical properties and complexity measures of read-once Boolean functions ⋮ Quantum zero-error algorithms cannot be composed ⋮ Query complexity of generalized Simon's problem ⋮ The Multiparty Communication Complexity of Set Disjointness ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The average sensitivity of bounded-depth circuits
• Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
• Sensitivity vs. block sensitivity (an average-case study)
• Randomized vs. deterministic decision tree complexity for read-once Boolean functions
• The critical complexity of graph properties
• Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
• A topological approach to evasiveness
• Lower bounds on probabilistic linear decision trees
• An \(\Omega{} (n^{4/3})\) lower bound on the randomized complexity of graph properties
• On read-once threshold formulae and their randomized decision tree complexity
• On recognizing graph properties from adjacency matrices
• Polynomials with two values
• On the degree of Boolean functions as real polynomials
• An oracle builder's toolkit
• A note on quantum black-box complexity of almost all Boolean functions
• Sensitivity vs. block sensitivity of Boolean functions
• On rank vs. communication complexity
• Complexity limitations on quantum computation
• Schwankung von Polynomen zwischen Gitterpunkten. (Oscillations of polynomials between lattice points)
• The quantum query complexity of approximating the median and related statistics
• The critical complexity of all (monotone) boolean functions and monotone graph properties
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• CREW PRAM<scp>s</scp> and Decision Trees
• Quantum lower bounds by polynomials
• A Comparison of Uniform Approximations on an Interval and a Finite Subset Thereof

This page was built for publication: Complexity measures and decision tree complexity: a survey.