Editing Communication complexity (section)

== Unbounded-error communication complexity ==

In the unbounded-error setting, Alice and Bob have access to a private coin and their own inputs <math>(x, y)</math>. In this setting, Alice succeeds if she responds with the correct value of <math>f(x, y)</math> with probability strictly greater than 1/2. In other words, if Alice's responses have ''any'' non-zero correlation to the true value of <math>f(x, y)</math>, then the protocol is considered valid.

Note that the requirement that the coin is ''private'' is essential. In particular, if the number of public bits shared between Alice and Bob are not counted against the communication complexity, it is easy to argue that computing any function has <math>O(1)</math> communication complexity.<ref>{{Citation|last=Lovett|first=Shachar|title=CSE 291: Communication Complexity, Winter 2019 Unbounded-error protocols|url=https://cseweb.ucsd.edu/classes/wi19/cse291-b/4-unbounded.pdf|access-date=June 9, 2019}}</ref> On the other hand, both models are equivalent if the number of public bits used by Alice and Bob is counted against the protocol's total communication.<ref>{{Cite journal|last1=Göös|first1=Mika|last2=Pitassi|first2=Toniann|last3=Watson|first3=Thomas|date=2018-06-01|title=The Landscape of Communication Complexity Classes|journal=Computational Complexity|volume=27|issue=2|pages=245–304|doi=10.1007/s00037-018-0166-6|s2cid=4333231|issn=1420-8954|url=https://drops.dagstuhl.de/opus/volltexte/2016/6199/}}</ref>

Though subtle, lower bounds on this model are extremely strong. More specifically, it is clear that any bound on problems of this class immediately imply equivalent bounds on problems in the deterministic model and the private and public coin models, but such bounds also hold immediately for nondeterministic communication models and quantum communication models.<ref>{{Cite book|last=Sherstov|first=Alexander A.|title=2008 49th Annual IEEE Symposium on Foundations of Computer Science |chapter=The Unbounded-Error Communication Complexity of Symmetric Functions |date=October 2008|pages=384–393|doi=10.1109/focs.2008.20|isbn=978-0-7695-3436-7|s2cid=9072527}}</ref>

Forster<ref>{{Cite journal|author=Forster, Jürgen |title=A linear lower bound on the unbounded error probabilistic communication complexity |journal=Journal of Computer and System Sciences |volume=65 |issue=4 |pages= 612–625 |year=2002 |doi=10.1016/S0022-0000(02)00019-3|doi-access=free }}</ref> was the first to prove explicit lower bounds for this class, showing that computing the inner product <math>\langle x, y \rangle</math> requires at least <math>\Omega(n)</math> bits of communication, though an earlier result of Alon, Frankl, and Rödl proved that the communication complexity for almost all Boolean functions <math>f: \{0, 1\}^n \times \{0, 1\}^n \to \{0, 1\}</math> is <math>\Omega(n)</math>.<ref>{{Cite book|last1=Alon|first1=N.|last2=Frankl|first2=P.|last3=Rodl|first3=V.|title=26th Annual Symposium on Foundations of Computer Science (SFCS 1985) |chapter=Geometrical realization of set systems and probabilistic communication complexity |date=October 1985|location=Portland, OR, USA|publisher=IEEE|pages=277–280|doi=10.1109/SFCS.1985.30|isbn=9780818606441|citeseerx=10.1.1.300.9711|s2cid=8416636}}</ref>