Conferences in Research and Practice in Information Technology
  

Online Version - Last Updated - 20 Jan 2012

 

 
Home
 

 
Procedures and Resources for Authors

 
Information and Resources for Volume Editors
 

 
Orders and Subscriptions
 

 
Published Articles

 
Upcoming Volumes
 

 
Contact Us
 

 
Useful External Links
 

 
CRPIT Site Search
 
    

On Directional vs. Undirectional Randomized Decision Tree Complexity for Read-Once Formulas

Amano, K.

    We investigate the relationship between the direc- tional and the undirectional complexity of read-once Boolean formulas on the randomized decision tree model. It was known that there is a read-once Boolean formula such that an optimal randomized al- gorithm to evaluate it is not directional. This was first pointed out by Saks and Wigderson (1986) and an explicit construction of such a formula was given by Vereshchagin (1998). We conduct a systematic search for a certain class of functions and provide an explicit construction of a read-once Boolean formula f on n variables such that the cost of the optimal directional randomized decision tree for f is Ω(n^α) and the cost of the optimal randomized undirectional decision tree for f is O(n^β) with α−β > 0.0101. This is the largest known gap so far.
Cite as: Amano, K. (2010). On Directional vs. Undirectional Randomized Decision Tree Complexity for Read-Once Formulas. In Proc. 16-th Computing: The Australasian Theory Symposium (CATS 2010) Brisbane, Australia. CRPIT, 109. Viglas, T. and Potanin, A. Eds., ACS. 25-30
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS