Randomized versus deterministic decision tree size
From MaRDI portal
Publication:6499271
DOI10.1145/3564246.3585199MaRDI QIDQ6499271
Nikhil S. Mande, Yogesh Dahiya, Jaikumar Radhakrishnan, Arkadev Chattopadhyay, Swagato Sanyal
Publication date: 8 May 2024
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Boolean function complexity. Advances and frontiers.
- Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
- Resolution over linear equations and multilinear proofs
- Lower bounds on probabilistic linear decision trees
- On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
- Learning decision trees from random examples
- Decision trees with Boolean threshold queries
- Simulation theorems via pseudo-random properties
- Resolution over linear equations modulo two
- Quantum algorithms for learning symmetric juntas via the adversary bound
- CREW PRAM<scp>s</scp> and Decision Trees
- Deterministic Communication vs. Partition Number
- Structure of Protocols for XOR Functions
- Separations in Query Complexity Based on Pointer Functions
- Lifting Theorems for Equality
- Separation Between Deterministic and Randomized Query Complexity
- Quantum lower bounds by polynomials
- Query-to-Communication Lifting Using Low-Discrepancy Gadgets
- On (simple) decision tree rank
- Bipartite perfect matching as a real polynomial
- Log-rank and lifting for AND-functions
- Fourier growth of parity decision trees
This page was built for publication: Randomized versus deterministic decision tree size
