On directional vs. general randomized decision tree complexity for read-once formulas

DOI10.4086/CJTCS.2011.003MaRDI QIDQ5414592zbMATH OpenOpenAlexFDO

Authors Kazuyuki Amano

Publication date 6 May 2014

Published in Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/cjtcs.2011.003

zbMATH Keywords

Boolean functionscomputational complexitydecision treedirectional algorithm

Mathematics Subject Classification ID

Boolean functions (06E30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• Randomized Boolean decision trees: Several remarks
• scientific article; zbMATH DE number 176867
• Bounding the randomized decision tree complexity of read-once Boolean functions
• On read-once threshold formulae and their randomized decision tree complexity
• Randomized vs. deterministic decision tree complexity for read-once Boolean functions

Cited in

(6)

• On read-once threshold formulae and their randomized decision tree complexity
• Randomized Boolean decision trees: Several remarks
• On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
• Bounding the randomized decision tree complexity of read-once Boolean functions
• 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: On directional vs. general randomized decision tree complexity for read-once formulas

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