Complexity measures and decision tree complexity: a survey.
From MaRDI portal
(Redirected from Publication:1853508)
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)- The simplified weighted sum function and its average sensitivity
- A composition theorem for randomized query complexity
- Revisiting Deutsch-Jozsa algorithm
- Deterministic and nondeterministic decision trees for recognition of properties of decision rule systems
- Decision tree complexity versus block sensitivity and degree
- On the fine-grained query complexity of symmetric functions
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- On fractional block sensitivity
- Quantum differential equation solvers: limitations and fast-forwarding
- 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?)
- Decision trees with short explainable rules
- Relations between monotone complexity measures based on decision tree complexity
- 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
- Sensitivity of symmetric Boolean functions
- 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 speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching
- 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?)
- On the fine-grained query complexity of symmetric functions
- 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
- Simulating functioning of decision trees for tasks on decision rule systems
- On complexity of deterministic and nondeterministic decision trees for decision tables with many-valued decisions from closed classes
- Quantum time-space tradeoff for finding multiple collision pairs
- 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
- Interplay between resiliency and polynomial degree -- recursive amplification, higher order sensitivity and beyond
- Weak derandomization of weak algorithms: explicit versions of Yao's lemma
- Verifiable quantum advantage without structure
- 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
- Sensitivity conjecture and signed hypercubes
- Complexity measures on the symmetric group and beyond (extended abstract)
- 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
- Separations between combinatorial measures for transitive functions
- Query-to-communication lifting for BPP
- Uniqueness for 2-intersecting families of permutations and perfect matchings
- 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
- Quantum distributed complexity of set disjointness on a line
- 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
- On the degree of Boolean functions as polynomials over \(\mathbb{Z}_m\)
- The power of many samples in query complexity
- Internal pattern matching queries in a text and applications
- Memory-restricted black-box complexity of OneMax
- New degree bounds for polynomial threshold functions
- Near-optimal quantum algorithms for string problems
- scientific article; zbMATH DE number 17536 (Why is no real title available?)
- Quantum and classical query complexities for generalized Simon's problem
- Query complexity in expectation
- Forrelation: a problem that optimally separates quantum from classical computing
- Randomized communication and implicit graph representations
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)
