Editing Communication complexity (section)

=== Collapse of Randomized Communication Complexity ===

Let's say we additionally allow Alice and Bob to share some resource, for example a pair of entangled particles. Using that ressource, Alice and Bob can correlate their information and thus try to 'collapse' (or 'trivialize') communication complexity in the following sense.

'''Definition.''' ''A resource <math>R</math> is said to be ''"collapsing"'' if, using that resource <math>R</math>, only one bit of classical communication is enough for Alice to know the evaluation <math>f(x,y)</math> in the worst case scenario for any [[Boolean function]] <math>f</math>. ''

The surprising fact of a collapse of communication complexity is that the function <math>f</math> can have arbitrarily large entry size, but still the number of communication bit is constant to a single one.

Some resources are shown to be non-collapsing, such as quantum correlations <ref>{{cite book | chapter-url=https://doi.org/10.1007/3-540-49208-9_4 | doi=10.1007/3-540-49208-9_4 | chapter=Quantum Entanglement and the Communication Complexity of the Inner Product Function | title=Quantum Computing and Quantum Communications | series=Lecture Notes in Computer Science | date=1999 | last1=Cleve | first1=Richard | last2=Van Dam | first2=Wim | last3=Nielsen | first3=Michael | last4=Tapp | first4=Alain | volume=1509 | pages=61–74 | isbn=978-3-540-65514-5 | url=https://digital.library.unt.edu/ark:/67531/metadc706249/ }}</ref> or more generally almost-quantum correlations,<ref>{{cite journal | url=https://doi.org/10.1038/ncomms7288 | doi=10.1038/ncomms7288 | title=Almost quantum correlations | date=2015 | last1=Navascués | first1=Miguel | last2=Guryanova | first2=Yelena | last3=Hoban | first3=Matty J. | last4=Acín | first4=Antonio | journal=Nature Communications | volume=6 | page=6288 | pmid=25697645 | arxiv=1403.4621 | bibcode=2015NatCo...6.6288N }}</ref> whereas on the contrary some other resources are shown to collapse randomized communication complexity, such as the PR-box,<ref>W. van Dam, Nonlocality & Communication Complexity,
Ph.d. thesis, University of Oxford (1999).</ref> or some noisy PR-boxes satisfying some conditions.<ref>{{cite journal |last1=Brassard |first1=Gilles |last2=Buhrman |first2=Harry |last3=Linden |first3=Noah |last4=Méthot |first4=André Allan |last5=Tapp |first5=Alain |last6=Unger |first6=Falk |title=Limit on Nonlocality in Any World in Which Communication Complexity Is Not Trivial |journal=Physical Review Letters |date=27 June 2006 |volume=96 |issue=25 |doi=10.1103/PhysRevLett.96.250401|arxiv=quant-ph/0508042 }}</ref><ref>{{cite journal |last1=Brunner |first1=Nicolas |last2=Skrzypczyk |first2=Paul |title=Nonlocality Distillation and Postquantum Theories with Trivial Communication Complexity |journal=Physical Review Letters |date=24 April 2009 |volume=102 |issue=16 |doi=10.1103/PhysRevLett.102.160403|arxiv=0901.4070 }}</ref><ref>{{cite journal |last1=Botteron |first1=Pierre |last2=Broadbent |first2=Anne |last3=Proulx |first3=Marc-Olivier |title=Extending the Known Region of Nonlocal Boxes that Collapse Communication Complexity |journal=Physical Review Letters |date=14 February 2024 |volume=132 |issue=7 |doi=10.1103/PhysRevLett.132.070201|arxiv=2302.00488 }}</ref>