Peng Ningning: The Query Complexity of Read-once Boolean Functions

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 05 February 2014, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Peng Ningning, National University of Singapore

Title: The Query Complexity of Read-once Boolean Functions


Abstract: We study the query complexity of algorithms with randomness.
We consider the deterministic and the randomized decision tree
complexities for Boolean functions, denoted D(f) and R(f),
respectively. A major open problem is how small R(f) can be with
respect to D(f). The well-known Saks-Wigderson’s Conjecture is the
statement that for any Boolean function f, R(f) =
Omega(n^{0.753}), where n is the number of inputs. In this talk, we
will show some positive evidences of this conjecture. We also
introduce the latest results on this topic.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.