New answers tagged

2

After some more searching, I managed to find a proof in these lecture notes [1]. The proof goes via Yao's principle and the lower bound is n/3. If someone knows of a published paper or a book that I may cite for this fact, I am still interested. [1] https://people.cs.rutgers.edu/~sa1497/courses/cs514-s20/lec3.pdf


Top 50 recent answers are included