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

Boolean functions (06E30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) 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

(10)

• On read-once threshold formulae and their randomized decision tree complexity
• Randomized Boolean decision trees: Several remarks
• Improved bounds for the randomized decision tree complexity of recursive majority
• 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
• On directional vs. general randomized decision tree complexity for read-once formulas
• Lower bounds on the randomized communication complexity of read-once functions
• Randomized vs. deterministic decision tree complexity for read-once Boolean functions

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)