Randomized versus deterministic decision tree size
From MaRDI portal
Cites work
- Boolean function complexity. Advances and frontiers.
- CREW PRAM<scp>s</scp> and Decision Trees
- Decision trees with Boolean threshold queries
- Deterministic communication vs. partition number
- Fourier growth of parity decision trees
- scientific article; zbMATH DE number 4070309 (Why is no real title available?)
- scientific article; zbMATH DE number 6789270 (Why is no real title available?)
- scientific article; zbMATH DE number 7650392 (Why is no real title available?)
- Learning decision trees from random examples
- Lifting Theorems for Equality
- Log-rank and lifting for AND-functions
- Lower bounds on probabilistic linear decision trees
- Monotone circuit lower bounds from resolution
- On (simple) decision tree rank
- On fractional block sensitivity
- On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
- Quantum algorithms for learning symmetric juntas via the adversary bound
- 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?
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- Query-to-communication lifting using low-discrepancy gadgets
- Resolution over linear equations and multilinear proofs
- Resolution over linear equations modulo two
- Separation between deterministic and randomized query complexity
- Simulation theorems via pseudo-random properties
- Structure of protocols for XOR functions
Cited in
(3)
This page was built for publication: Randomized versus deterministic decision tree size
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499271)
