Abstract:
Half-duplex communication complexity with adversary was defined in [2]. Half-duplex communication protocols generalize classical protocols defined by Yao in [11]. It has been unknown so far whether or not the communication complexities defined by these models are different. In the present paper we answer this question: we exhibit a function whose half-duplex communication complexity with adversary is strictly less than its classical communication complexity.
Bibliography: 11 titles.
Keywords:communication complexity, fooling sets, half-duplex communication complexity.
Fulltext:
PDF file (929 kB)
First page:
PDF file
