Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
We show that computing the majority of n copies of a boolean function g has randomised query complexity R(Maj∘gⁿ) = Θ(n⋅R ̅_{1/n}(g)). In fact, we show that to obtain a similar result for any composed function f∘gⁿ, it suffices to prove a sufficiently strong form of the result only in the special case g = GapOr. LIPIcs, Vol. 200, 36th Computational Complexity Conference (CCC 2021), pages 18:1-18:15
Giovanni De Micheli, Alessandro Tempia Calvino, Gianluca Radi
Giovanni De Micheli, Heinz Riener, Siang-Yun Lee
Giovanni De Micheli, Mathias Soeken, Dewmini Sudara Marakkalage, Eleonora Testa, Heinz Riener