Vi bevisar lägre gränser för den direkta summan problem för två part avgränsade fel randomiserade multiplexround kommunikationsprotokoll. Våra bevis använder begreppet information kostnad för ett protokoll, som definieras av Chakrabarti et al. [CSWY01] och förfinas ytterligare genom. Vårt huvudsakliga tekniska resultat är en "kompression" teorem som säger att, för varje sannolikhetsfördelning μ över indata, ett k-round privat mynt avgränsade felprotokoll för en funktion f med informationskostnad c kan omvandlas till ett kround deterministiskt protokoll för f med begränsad distributionsfel och kommunikationskostnad O(kc). Vi bevisar detta resultat med hjälp av en substate sats om relativ entropi och en avvisande provtagning argument. Vårt direkta resultat följer av detta "kompressionsresultat" via teoretiska argument för elementär information. Vi betraktar också problemet med den direkta summan i kvantkommunikationen. Med ett probabilistiskt argument visar vi att budskapen inte kan komprimeras på detta sätt även om de innehåller liten information. Därför kan det bli nödvändigt med nya tekniker för att ta itu med problemet med direkta summor i kvantkommunikationen.
REF visade lägre gränser för problemet med direktsummor för tvåparts randomiserade protokoll med r rundor.
A direct sum theorem in communication complexity via message compression
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}