Separating decision tree complexity from subcube partition complexity

DOI10.4230/LIPICS.APPROX-RANDOM.2015.915MaRDI QIDQ5351943zbMATH OpenFDO

Authors Robin Kothari, David Racicot-Desloges, Miklos Santha

Publication date 31 August 2017

Full work available at URL https://arxiv.org/abs/1504.01339

zbMATH Keywords

decision tree complexityquery complexityrandomized algorithmssubcube partition complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Recommendations

• scientific article; zbMATH DE number 2019628
• Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority
• Nearly optimal separations between communication (or query) complexity and partitions
• scientific article; zbMATH DE number 17536

Cited in

(7)

• On the Complexity of Extracting Subtree with Keeping Distinguishability
• scientific article; zbMATH DE number 17536 (Why is no real title available?)
• Deterministic communication vs. partition number
• Low-sensitivity functions from unambiguous certificates
• Losing Treewidth by Separating Subsets
• The complexity of subcube partition relates to the additive structure of the support
• Fooling near-maximal decision trees

This page was built for publication: Separating decision tree complexity from subcube partition complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5351943)