Complexity measures and decision tree complexity: a survey.
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 4130025 (Why is no real title available?)
- scientific article; zbMATH DE number 4012495 (Why is no real title available?)
- scientific article; zbMATH DE number 194009 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 1500513 (Why is no real title available?)
- A Comparison of Uniform Approximations on an Interval and a Finite Subset Thereof
- A note on quantum black-box complexity of almost all Boolean functions
- A topological approach to evasiveness
- An \(\Omega{} (n^{4/3})\) lower bound on the randomized complexity of graph properties
- An oracle builder's toolkit
- CREW PRAM<scp>s</scp> and Decision Trees
- Complexity limitations on quantum computation
- Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
- Lower bounds on probabilistic linear decision trees
- On rank vs. communication complexity
- On read-once threshold formulae and their randomized decision tree complexity
- On recognizing graph properties from adjacency matrices
- On the degree of Boolean functions as real polynomials
- Polynomials with two values
- Quantum lower bounds by polynomials
- Query complexity, or why is it difficult to separate NP^ A coNP^ A from P^ A by random oracles A?
- Randomized vs. deterministic decision tree complexity for read-once Boolean functions
- Schwankung von Polynomen zwischen Gitterpunkten. (Oscillations of polynomials between lattice points)
- Sensitivity vs. block sensitivity (an average-case study)
- Sensitivity vs. block sensitivity of Boolean functions
- The average sensitivity of bounded-depth circuits
- The critical complexity of all (monotone) boolean functions and monotone graph properties
- The critical complexity of graph properties
- The quantum query complexity of approximating the median and related statistics
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
Cited in
(only showing first 100 items - show all)- Extension complexity of independent set polytopes
- Symmetries, graph properties, and quantum speedups
- Optimal deterministic quantum algorithm for the promised element distinctness problem
- Does looking inside a circuit help?
- From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm
- Time-Space Complexity Advantages for Quantum Computing
- A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length
- Deterministic quantum search with adjustable parameters: implementations and applications
- A note on the size of minimal covers
- Tight bounds on sensitivity and block sensitivity of some classes of transitive functions
- Sharp phase transition for the random-cluster and Potts models via decision trees
- Secure and highly-available aggregation queries in large-scale sensor networks via set sampling
- Separation between deterministic and randomized query complexity
- SOFSEM 2006: Theory and Practice of Computer Science
- Submodular goal value of Boolean functions
- Quantum Queries on Permutations with a Promise
- A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function
- Fourier 1-norm and quantum speed-up
- Certificate complexity of elementary symmetric Boolean functions
- Exact distributed quantum algorithm for generalized Simon's problem
- The multiparty communication complexity of set disjointness
- Improved output-sensitive quantum algorithms for Boolean matrix multiplication
- On the relationship between energy complexity and other Boolean function measures
- On the average sensitivity of the weighted sum function
- Lifting Theorems for Equality
- On the decision tree complexity of threshold functions
- Characterization of exact two-query quantum algorithms
- On query complexity measures and their relations for symmetric functions
- Communication lower bounds via critical block sensitivity
- Quantum queries on permutations
- The simplified weighted sum function and its average sensitivity
- A composition theorem for randomized query complexity
- Revisiting Deutsch-Jozsa algorithm
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- On fractional block sensitivity
- Conflict complexity is lower bounded by block sensitivity
- The complexity of the certification of properties of stable marriage
- On block sensitivity and fractional block sensitivity
- Quantum algorithms on Walsh transform and Hamming distance for Boolean functions
- Optimal direct sum results for deterministic and randomized decision tree complexity
- Quantum algorithms for learning symmetric juntas via the adversary bound
- scientific article; zbMATH DE number 426344 (Why is no real title available?)
- Quantum query as a state decomposition
- Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
- On the resolution of the sensitivity conjecture
- Lifting query complexity to time-space complexity for two-way finite automata
- Average time complexity of decision trees.
- Size of sets with small sensitivity: a generalization of Simon's lemma
- On exact quantum query complexity
- Time and space complexity of deterministic and nondeterministic decision trees
- On the modulo degree complexity of Boolean functions
- Composition limits and separating examples for some Boolean function complexity measures
- From quantum query complexity to state complexity
- Exponential lower bound for bounded depth circuits with few threshold gates
- Generalizations of the distributed Deutsch-Jozsa promise problem
- An asymptotically tight bound on the number of relevant variables in a bounded degree Boolean function
- On separation between the degree of a Boolean function and the block sensitivity
- On the parity complexity measures of Boolean functions
- scientific article; zbMATH DE number 7559433 (Why is no real title available?)
- Quantum algorithm for lexicographically minimal string rotation
- Polynomial degree vs. quantum query complexity
- An improved lower bound on the sensitivity complexity of graph properties
- Parity decision tree in classical-quantum separations for certain classes of Boolean functions
- Unbounded-error quantum query complexity
- Quantum lower bounds for approximate counting via Laurent polynomials
- Non-interactive proofs of proximity
- Quantum query complexity of constant-sized subgraph containment
- An adaptivity hierarchy theorem for property testing
- On the isomorphism problem for decision trees and decision lists
- scientific article; zbMATH DE number 1285753 (Why is no real title available?)
- A tighter relation between sensitivity complexity and certificate complexity
- scientific article; zbMATH DE number 7758330 (Why is no real title available?)
- Sensitivity versus block sensitivity of Boolean functions
- Quantum zero-error algorithms cannot be composed
- Any monotone property of 3-uniform hypergraphs is weakly evasive
- An Optimal Separation of Randomized and Quantum Query Complexity
- Representing polynomial of \textsc{St-Connectivity}
- Quantum attribute-based encryption: a comprehensive study
- Quantum and classical query complexities for generalized Deutsch-Jozsa problems
- Alternation, sparsity and sensitivity: bounds and exponential gaps
- Performance of Grover's search algorithm with diagonalizable collective noises
- Sensitivity versus certificate complexity of Boolean functions
- Weak derandomization of weak algorithms: explicit versions of Yao's lemma
- Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems
- A \(\mathrm{ZPP}^{\mathrm{NP}[1]}\) lifting theorem
- Quantum certificate complexity
- Quantum decision tree classifier
- On the degree of univariate polynomials over the integers
- Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
- Totally optimal decision trees for Boolean functions
- Deterministic communication vs. partition number
- Query-to-communication lifting for BPP
- Evaluation of exact quantum query complexities by semidefinite programming
- Testing Boolean functions properties
- Decision trees based on 1-consequences
- Critical properties and complexity measures of read-once Boolean functions
- A composition theorem for decision tree complexity
- A lower bound on the quantum query complexity of read-once functions
- All classical adversary methods are equivalent for total functions
- Minimization of decision trees is hard to approximate
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)
