Randomized versus deterministic decision tree size
From MaRDI portal
Publication:6499271
Cites work
- 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?)
- 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
- 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 P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
- On fractional block sensitivity
- 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\cap 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
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)
