Randomized versus deterministic decision tree size
From MaRDI portal
Publication:6499271
DOI10.1145/3564246.3585199MaRDI QIDQ6499271FDOQ6499271
Nikhil S. Mande, Yogesh Dahiya, Jaikumar Radhakrishnan, Arkadev Chattopadhyay, Swagato Sanyal
Publication date: 8 May 2024
Cites Work
- Boolean function complexity. Advances and frontiers.
- CREW PRAM<scp>s</scp> and Decision Trees
- Title not available (Why is that?)
- 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
- Separations in Query Complexity Based on Pointer Functions
- 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
- Title not available (Why is that?)
- Bipartite perfect matching as a real polynomial
- Separation Between Deterministic and Randomized Query Complexity
- Lifting Theorems for Equality
- Title not available (Why is that?)
- Simulation theorems via pseudo-random properties
- Title not available (Why is that?)
- 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)
