Bounding the randomized decision tree complexity of read-once Boolean functions

MaRDI QIDQ5365151zbMATH OpenFDO

Authors Kazuyuki Amano

Publication date 29 September 2017

Full work available at URL http://dl.acm.org/citation.cfm?id=2133169

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean functions (06E30) Boolean functions (94D10)

Recommendations

• Randomized vs. deterministic decision tree complexity for read-once Boolean functions
• On read-once threshold formulae and their randomized decision tree complexity
• scientific article; zbMATH DE number 176867
• How Do Read-Once Formulae Shrink?
• On directional vs. general randomized decision tree complexity for read-once formulas

Cited in

(9)

• Randomized vs. deterministic decision tree complexity for read-once Boolean functions
• On directional vs. general randomized decision tree complexity for read-once formulas
• Improved bounds for the randomized decision tree complexity of recursive majority
• scientific article; zbMATH DE number 176867 (Why is no real title available?)
• scientific article; zbMATH DE number 7310075 (Why is no real title available?)
• An improved lower bound for the randomized decision tree complexity of recursive majority
• Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority
• Lower bounds on the randomized communication complexity of read-once functions
• On read-once threshold formulae and their randomized decision tree complexity

This page was built for publication: Bounding the randomized decision tree complexity of read-once Boolean functions

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