On (simple) decision tree rank
From MaRDI portal
Publication:6050134
DOI10.1016/j.tcs.2023.114177arXiv2209.12877OpenAlexW3214958556MaRDI QIDQ6050134
Publication date: 12 October 2023
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2209.12877
Boolean functionsrankdecision treessparsityquery complexityiterated compositioncertificate complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Near optimal seperation of tree-like and general resolution
- Boolean function complexity. Advances and frontiers.
- Algorithms for sensor systems. 6th international workshop on algorithms for sensor systems, wireless ad hoc networks, and autonomous mobile entities, ALGOSENSORS 2010, Bordeaux, France, July 5, 2010. Revised selected papers
- Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
- A combinatorial characterization of treelike resolution space
- Rank-\(r\) decision trees are a subclass of \(r\)-decision lists
- On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
- Learning decision trees from random examples
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- Decision trees with Boolean threshold queries
- On the structure of Boolean functions with small spectral norm
- A characterization of tree-like resolution size
- One-way functions and the nonisomorphism of NP-complete sets
- A theory of the learnable
- Communication Complexity
- Analysis of Boolean Functions
- Lower Bounds for Linear Decision Trees with Bounded Weights
- A Brief History of Strahler Numbers
- Log-rank and lifting for AND-functions
This page was built for publication: On (simple) decision tree rank
