One of the major open problems in complexity theory is to demonstrate an explicit function which requires super logarithmic depth, to tackle this problem Karchmer, Raz and Wigderson proposed the KRW conjecture about composition of two functions. While this conjecture seems out of our current reach, some relaxed conjectures are suggested to be the stepping stone to the original one. One important kind of relaxed forms is composition about universal relation. We already have strong lower bounds for composition of two universal relations as well as composition of a function and a universal relation. The final jigsaw to complete our understanding of composition about universal relation is the composition of a universal relation and a function. Recently, Ivan Mihajlin and Alexander Smal proved a composition theorem of a universal relation and some function via so called xor composition, that is there exists some function $f:\{0,1\}^n \rightarrow \{0,1\}$ such that ${CC}({U}_n \diamond \text{KW}_f) \geq 1.5n-o(n)$ where ${CC}$ denotes the communication complexity of the problem.

In this paper, we significantly improve their result and present an asymptotically tight and much more general composition theorem of a universal relation and most functions, that is for most functions $f:\{0,1\}^n \rightarrow \{0,1\}$ we have ${CC}({U}_m \diamond \text{KW}_f) \geq m+ n -O(\sqrt{m})$ when $m=\omega(\log^2 n),n =\omega(\sqrt{m})$. This is done by a direct proof of composition theorem of a universal relation and a multiplexor in the partially half-duplex model avoiding the xor composition. And the proof works even when the multiplexor only contains a few functions. One crucial ingredient in our proof involves a combinatorial problem of constructing a tree of many leaves and every leaf contains a non-overlapping set of functions. For each leaf, there is a set of inputs such that every function in the leaf takes the same value, that is all functions are restricted. We show how to choose a set of good inputs to effectively restrict these functions to force that the number of functions in each leaf is as small as possible while maintaining the total number of functions in all leaves. This results in a large number of leaves.

1.fix typos and improve presentation of the paper
2.change all the letter $\Theta$ for trace to $\Psi$, to avoid confusion due to that the same letter $\Theta$ is used for the notation in asymtotics.
3.add more discussion in Section 5

One of the major open problems in complexity theory is to demonstrate an explicit function which requires super logarithmic depth, to tackle this problem Karchmer, Raz and Wigderson proposed the KRW conjecture about composition of two functions. While this conjecture seems out of our current reach, some relaxed conjectures are suggested to be the stepping stone to the original one. One important kind of relaxed forms is composition about universal relation. We already have strong lower bounds for composition of two universal relations as well as composition of a function and a universal relation. The final jigsaw to complete our understand of composition about universal relation is the composition of a universal relation and a function. Recently, Ivan Mihajlin and Alexander Smal proved a composition theorem of a universal relation and some function via so called xor composition, that is there exists some function $f:\{0,1\}^n \rightarrow \{0,1\}$ such that ${CC}({U}_n \diamond \text{KW}_f) \geq 1.5n-o(n)$ where ${CC}$ denotes the communication complexity of the problem.

In this paper, we significantly improve their result and present an asymptotically tight and much more general composition theorem of a universal relation and most functions, that is for most functions $f:\{0,1\}^n \rightarrow \{0,1\}$ we have ${CC}({U}_m \diamond \text{KW}_f) \geq m+ n -O(\sqrt{m})$ when $m=\omega(\log^2 n),n =\omega(\sqrt{m})$. This is done by a direct proof of composition theorem of a universal relation and a multiplexor in the partially half-duplex model avoiding the xor composition. And the proof works even when the multiplexor only contains a few functions. One crucial ingredient in our proof involves a combinatorial problem of constructing a tree of many leaves and every leaf contains a non-overlapping set of functions. For each leaf, there is a set of inputs such that every function in the leaf takes the same value, that is all functions are restricted. We show how to choose a set of good inputs to effectively restrict these functions to force that the number of functions in each leaf is as small as possible while maintaining the total number of functions in all leaves. This results in a large number of leaves.