Randomized versus deterministic decision tree size
From MaRDI portal
Publication:6499271
DOI10.1145/3564246.3585199MaRDI QIDQ6499271FDOQ6499271
Authors: Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil S. Mande, Jaikumar Radhakrishnan, Swagato Sanyal 
Publication date: 8 May 2024
Cites Work
- Boolean function complexity. Advances and frontiers.
- CREW PRAM<scp>s</scp> and Decision Trees
- Monotone circuit lower bounds from resolution
- Quantum lower bounds by polynomials
- Learning decision trees from random examples
- Decision trees with Boolean threshold queries
- Quantum algorithms for learning symmetric juntas via the adversary bound
- Title not available (Why is that?)
- Resolution over linear equations and multilinear proofs
- On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
- 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
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- Separation between deterministic and randomized query complexity
- Lifting Theorems for Equality
- Title not available (Why is that?)
- Simulation theorems via pseudo-random properties
- On fractional block sensitivity
- Resolution over linear equations modulo two
- Deterministic communication vs. partition number
- Structure of protocols for XOR functions
- Query-to-communication lifting using low-discrepancy gadgets
- Log-rank and lifting for AND-functions
- Title not available (Why is that?)
- Fourier growth of parity decision trees
- On (simple) decision tree rank
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)
