Vi visar att nästan alla kända lägre bundna metoder för kommunikation komplexitet också är lägre gränser för informationen komplexitet. I synnerhet definierar vi en avslappnad version av partitionen som är bunden till Jain och Klauck [JK10] och bevisar att den sänker informations komplexiteten hos alla funktioner. Vår avslappnade partitionsbundna delsummor alla normbaserade metoder (t.ex. γ 2-metoden) och rektangelbaserade metoder (t.ex. Den rektangel/korruption som är bunden, den släta rektangeln som är bunden och avvikelsen som är bunden), utom partitionen som är bunden. Vårt resultat använder en ny anslutning mellan rektanglar och nollkommunikationsprotokoll där spelarna antingen kan mata ut ett värde eller avbryta. Vi bevisar följande kompression lemma: givet ett protokoll för en funktion f med information komplexitet I, kan man konstruera en noll-kommunikation protokoll som har icke-abort sannolikhet minst 2 −O(I) och som beräknar f korrekt med hög sannolikhet villkorad på att inte avbryta. Sedan visar vi hur ett sådant nollkommunikationsprotokoll relaterar till den avslappnade partitionen bunden. Vi använder vårt huvudteorem för att lösa tre av de öppna frågor som ställdes av Braverman [Bra12]. För det första visar vi att informationskomplexet hos Vektorn i Subrymdsproblemet [KR11] är  en (n 1/3 ), vilket i sin tur innebär att det finns en exponentiell separation mellan kvantkommunikationens komplexitet och den klassiska informationskomplexiteten. Dessutom ger vi en (n) lägre gräns på information komplexiteten i Gap Hamming Avståndsproblem.
Den avslappnade partitionen bunden fram i REF, på liknande sätt subsumes flera kombinatoriska gränser, med undantag för partitionen bunden sig själv.
Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}