Complexity measures and decision tree complexity: a survey.
From MaRDI portal
Publication:1853508
DOI10.1016/S0304-3975(01)00144-XzbMATH Open1061.68058OpenAlexW2012496360MaRDI QIDQ1853508FDOQ1853508
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
Recommendations
Quantum computingRandomized computingComplexity measures for Boolean functionsDecision tree complexity
Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- The quantum query complexity of approximating the median and related statistics
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Schwankung von Polynomen zwischen Gitterpunkten. (Oscillations of polynomials between lattice points)
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- The average sensitivity of bounded-depth circuits
- On the degree of Boolean functions as real polynomials
- Sensitivity vs. block sensitivity of Boolean functions
- Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
- CREW PRAM<scp>s</scp> and Decision Trees
- Sensitivity vs. block sensitivity (an average-case study)
- On recognizing graph properties from adjacency matrices
- Polynomials with two values
- Quantum lower bounds by polynomials
- A note on quantum black-box complexity of almost all Boolean functions
- Complexity limitations on quantum computation
- A topological approach to evasiveness
- On rank vs. communication complexity
- The critical complexity of graph properties
- The critical complexity of all (monotone) boolean functions and monotone graph properties
- A Comparison of Uniform Approximations on an Interval and a Finite Subset Thereof
- On read-once threshold formulae and their randomized decision tree complexity
- Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
- Lower bounds on probabilistic linear decision trees
- Randomized vs. deterministic decision tree complexity for read-once Boolean functions
- An oracle builder's toolkit
- An \(\Omega{} (n^{4/3})\) lower bound on the randomized complexity of graph properties
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (only showing first 100 items - show all)
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- Generalizations of the distributed Deutsch–Jozsa promise problem
- The complexity of the certification of properties of stable marriage
- Title not available (Why is that?)
- Quantum algorithms for learning symmetric juntas via the adversary bound
- On the resolution of the sensitivity conjecture
- Sensitivity Versus Certificate Complexity of Boolean Functions
- Optimal direct sum results for deterministic and randomized decision tree complexity
- Quantum query as a state decomposition
- On the modulo degree complexity of Boolean functions
- Time and space complexity of deterministic and nondeterministic decision trees
- On exact quantum query complexity
- Average time complexity of decision trees.
- Title not available (Why is that?)
- Composition limits and separating examples for some Boolean function complexity measures
- Exponential lower bound for bounded depth circuits with few threshold gates
- On the parity complexity measures of Boolean functions
- Polynomial degree vs. quantum query complexity
- An improved lower bound on the sensitivity complexity of graph properties
- Quantum query complexity of constant-sized subgraph containment
- Unbounded-error quantum query complexity
- An adaptivity hierarchy theorem for property testing
- Extension Complexity of Independent Set Polytopes
- Sensitivity versus block sensitivity of Boolean functions
- Quantum zero-error algorithms cannot be composed
- An Optimal Separation of Randomized and Quantum Query Complexity
- Title not available (Why is that?)
- Weak derandomization of weak algorithms: explicit versions of Yao's lemma
- From Quantum Query Complexity to State Complexity
- Quantum certificate complexity
- Quantum decision tree classifier
- Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
- Totally optimal decision trees for Boolean functions
- Separation Between Deterministic and Randomized Query Complexity
- Evaluation of exact quantum query complexities by semidefinite programming
- New degree bounds for polynomial threshold functions
- Minimization of decision trees is hard to approximate
- A lower bound on the quantum query complexity of read-once functions
- Title not available (Why is that?)
- Memory-restricted black-box complexity of OneMax
- Title not available (Why is that?)
- A characterization of nested canalyzing functions with maximum average sensitivity
- Optimal separation in exact query complexities for Simon's problem
- Nonadaptive quantum query complexity
- A strong direct product theorem for quantum query complexity
- Superlinear advantage for exact quantum algorithms
- How low can approximate degree and quantum query complexity be for total Boolean functions?
- On the power of non-adaptive learning graphs
- Block sensitivity of weakly symmetric functions
- Quantum query complexity of almost all functions with fixed on-set size
- On the power of Ambainis lower bounds
- Query complexity of generalized Simon's problem
- Improved direct product theorems for randomized query complexity
- On the structure of Boolean functions with small spectral norm
- A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
- Deterministic quantum search with adjustable parameters: implementations and applications
- A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length
- Communication Lower Bounds via Critical Block Sensitivity
- A note on the size of minimal covers
- Sharp phase transition for the random-cluster and Potts models via decision trees
- Quantum Queries on Permutations with a Promise
- Secure and highly-available aggregation queries in large-scale sensor networks via set sampling
- Submodular goal value of Boolean functions
- On the relationship between energy complexity and other Boolean function measures
- A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function
- Fourier 1-norm and quantum speed-up
- Lifting Theorems for Equality
- On the average sensitivity of the weighted sum function
- Revisiting Deutsch-Jozsa algorithm
- Title not available (Why is that?)
- Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma
- Conflict complexity is lower bounded by block sensitivity
- On block sensitivity and fractional block sensitivity
- Quantum algorithms on Walsh transform and Hamming distance for Boolean functions
- Testing Boolean Functions Properties
- Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
- Forrelation: A Problem That Optimally Separates Quantum from Classical Computing
- Query-to-Communication Lifting for BPP
- Lifting query complexity to time-space complexity for two-way finite automata
- Low-Sensitivity Functions from Unambiguous Certificates.
- Quantum algorithm for lexicographically minimal string rotation
- An asymptotically tight bound on the number of relevant variables in a bounded degree Boolean function
- Title not available (Why is that?)
- On separation between the degree of a Boolean function and the block sensitivity
- Optimal parallel quantum query algorithms
- Parity decision tree in classical-quantum separations for certain classes of Boolean functions
- Non-interactive proofs of proximity
- On the isomorphism problem for decision trees and decision lists
- Title not available (Why is that?)
- A tighter relation between sensitivity complexity and certificate complexity
- Title not available (Why is that?)
- Any monotone property of 3-uniform hypergraphs is weakly evasive
- Representing polynomial of \textsc{St-Connectivity}
- Quantum attribute-based encryption: a comprehensive study
- Performance of Grover's search algorithm with diagonalizable collective noises
- Quantum and classical query complexities for generalized Deutsch-Jozsa problems
- Alternation, sparsity and sensitivity: bounds and exponential gaps
- Does Looking Inside a Circuit Help
- Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems
- On the degree of univariate polynomials over the integers
This page was built for publication: Complexity measures and decision tree complexity: a survey.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853508)
