A Candidate for a Strong Separation of Information and Communication
Author(s): Braverman, Mark; Ganor, Anat; Kol, Gillat; Raz, Ran
DownloadTo refer to this page use:
http://arks.princeton.edu/ark:/88435/pr1kn7pFull metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Braverman, Mark | - |
| dc.contributor.author | Ganor, Anat | - |
| dc.contributor.author | Kol, Gillat | - |
| dc.contributor.author | Raz, Ran | - |
| dc.date.accessioned | 2021-10-08T19:45:00Z | - |
| dc.date.available | 2021-10-08T19:45:00Z | - |
| dc.date.issued | 2018 | en_US |
| dc.identifier.citation | Braverman, Mark, Anat Ganor, Gillat Kol, and Ran Raz. "A Candidate for a Strong Separation of Information and Communication." In 9th Innovations in Theoretical Computer Science Conference (ITCS), 94 (2018): 11:1-11:13. doi:10.4230/LIPIcs.ITCS.2018.11 | en_US |
| dc.identifier.issn | 1868-8969 | - |
| dc.identifier.uri | http://arks.princeton.edu/ark:/88435/pr1kn7p | - |
| dc.description.abstract | The weak interactive compression conjecture asserts that any two-party communication protocol with communication complexity C and information complexity I can be compressed to a protocol with communication complexity poly(I)polylog(C). We describe a communication problem that is a candidate for refuting that conjecture. Specifically, while we show that the problem can be solved by a protocol with communication complexity C and information complexity I=polylog(C), the problem seems to be hard for protocols with communication complexity poly(I)polylog(C)=polylog(C). | en_US |
| dc.format.extent | 11:1 - 11:13 | en_US |
| dc.language.iso | en_US | en_US |
| dc.relation.ispartof | 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) | en_US |
| dc.relation.ispartofseries | Leibniz International Proceedings in Informatics (LIPIcs); | - |
| dc.rights | Final published version. This is an open access article. | en_US |
| dc.title | A Candidate for a Strong Separation of Information and Communication | en_US |
| dc.type | Conference Article | en_US |
| dc.identifier.doi | 10.4230/LIPIcs.ITCS.2018.11 | - |
| pu.type.symplectic | http://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceeding | en_US |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| CandidateStrongSeparationInformationCommunication.pdf | 472.08 kB | Adobe PDF | View/Download |
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.