Recursive Majority-of-three (3-Maj) is a deceptively simple problem in the study of randomized decision tree complexity. The precise complexity of this problem is unknown, while that of the similarly defined Recursive NAND tree is completely understood.
"We know that God exists because mathematics is consistent and we know that the devil exists because we cannot prove the consistency." -- Andre Weil
GALOIS REPRESENTATIONS AND AUTOMORPHIC FORMS SEMINAR
Note: (joint work with O. Brinon and A. Mokrane)