To refer to this page use:
http://arks.princeton.edu/ark:/88435/pr1838x
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Braverman, Mark | - |
dc.contributor.author | Schneider, J | - |
dc.date.accessioned | 2018-07-20T15:09:21Z | - |
dc.date.available | 2018-07-20T15:09:21Z | - |
dc.date.issued | 2016 | en_US |
dc.identifier.citation | Braverman, M, Schneider, J. (2016). Information complexity is computable. 55 (10.4230/LIPIcs.ICALP.2016.87 | en_US |
dc.identifier.uri | http://arks.princeton.edu/ark:/88435/pr1838x | - |
dc.description.abstract | The information complexity of a function f is the minimum amount of information Alice and Bob need to exchange to compute the function f. In this paper we provide an algorithm for approximating the information complexity of an arbitrary function f to within any additive error epsilon > 0, thus resolving an open question as to whether information complexity is computable. In the process, we give the first explicit upper bound on the rate of convergence of the information complexity of f when restricted to b-bit protocols to the (unrestricted) information complexity of f. | en_US |
dc.language.iso | en_US | en_US |
dc.relation.ispartof | 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) | en_US |
dc.rights | Author's manuscript | en_US |
dc.title | Information complexity is computable | en_US |
dc.type | Conference Article | en_US |
dc.identifier.doi | doi:10.4230/LIPIcs.ICALP.2016.87 | - |
dc.date.eissued | 2016 | en_US |
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 | |
---|---|---|---|---|
Information complexity is computable.pdf | 252.69 kB | Adobe PDF | View/Download |
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.