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

zbMATH Open1376.68057MaRDI QIDQ5365151FDOQ5365151

Authors: Kazuyuki Amano 

Publication date: 29 September 2017

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

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

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)

Cited In (9)

• On directional vs. general randomized decision tree complexity for read-once formulas
• Randomized vs. deterministic decision tree complexity for read-once Boolean functions
• Improved bounds for the randomized decision tree complexity of recursive majority
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)