Communication complexity bounds from information causality
Communication complexity, which quantifies the minimum communication required for distributed computation, offers a natural setting for investigating the capabilities and limitations of quantum mechanics in information processing. We introduce an information-theoretic approach to study one-way communication complexity based solely on the axioms of mutual information. Within this framework, we derive an extended statement of the information causality principle, which recovers known lower bounds on the communication complexities for a range of functions in a simplified manner and leads to new…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.10206
curl -X POST /api/v1/records/arxiv/2602.10206/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.10206/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'