Communication and information complexity
Summary: Communication complexity is an area of computational complexity theory that studies the amount of communication required to complete a computational task. Communication complexity gives us some of the most successful techniques for proving impossibility results for computational tasks. Information complexity connects communication complexity with Shannon's classical information theory. It treats information revealed or transmitted as the resource to be conserved. On the one hand, information complexity leads to extensions of classical information and coding theory to interactive scenarios. On the other hand, it provides us with tools to answer open questions about communication complexity and related areas. This note gives an overview of communication complexity and some recent developments in two-party information complexity and applications. The note is based on a talk given by the author at the International Congress of Mathematicians in 2022. It expands on some of the themes from the talk. It also provides references that were omitted during the talk. For the entire collection see [Zbl 07816355].
- A counterexample to strong parallel repetition
- A Method for the Construction of Minimum-Redundancy Codes
- A Parallel Repetition Theorem
- A taxonomy of problems with fast parallel algorithms
- Amortized Communication Complexity
- An information statistics approach to data stream and communication complexity
- Analysis of Boolean Functions
- Analytical approach to parallel repetition
- Arithmetic circuits: a survey of recent results and open questions
- Average-case interactive communication
- Boolean function complexity. Advances and frontiers.
- Coding for interactive communication
- Coding for interactive communication: a survey
- Communication Complexity
- Communication Complexity
- Communication complexity of estimating correlations
- Communication lower bounds for statistical estimation problems via a distributed data processing inequality
- Complexity measures of sign matrices
- Computational Complexity
- Constant depth circuits, Fourier transform, and learnability
- Disjointness is hard in the multiparty number-on-the-forehead model
- Elements of Information Theory
- Error reduction by parallel repetition - a negative result
- Explicit lower and upper bounds on the entangled value of multiplayer XOR games
- Exponential separation of communication and external information
- Exponential separation of information and communication for Boolean functions
- From information to exact communication
- How to compress interactive communication
- scientific article; zbMATH DE number 434716 (Why is no real title available?)
- scientific article; zbMATH DE number 3173126 (Why is no real title available?)
- scientific article; zbMATH DE number 5485476 (Why is no real title available?)
- scientific article; zbMATH DE number 1306882 (Why is no real title available?)
- scientific article; zbMATH DE number 1024014 (Why is no real title available?)
- scientific article; zbMATH DE number 1775389 (Why is no real title available?)
- Information Complexity Density and Simulation of Protocols
- Information Equals Amortized Communication
- Interaction in Quantum Communication
- Interactive channel capacity
- Interactive Information Complexity
- Linear FPT reductions and computational lower bounds
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
- On ACC
- On some fine-grained questions in algorithms and complexity
- On the complexity of k-SAT
- On the distributional complexity of disjointness
- Optimal tiling of the euclidean space using permutation-symmetric bodies
- Parallel repetition in projection games and a concentration bound
- Parity, circuits, and the polynomial-time hierarchy
- Privacy, additional information and communication
- Private vs. common random bits in communication complexity
- Probabilistic checking of proofs
- Proof verification and the hardness of approximation problems
- Quantum information complexity
- Reducibility among combinatorial problems
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Simulating noisy channel interaction (extended abstract)
- Small value parallel repetition for general games
- Some Results on Distributed Source Coding for Interactive Function Computation
- Super-logarithmic depth lower bounds via the direct sum in communication complexity
- The communication complexity of gap Hamming distance
- The Infinite-Message Limit of Two-Terminal Interactive Source Coding
- The multiparty communication complexity of set disjointness
- The Probabilistic Communication Complexity of Set Intersection
- The randomized communication complexity of set disjointness
- The rate-distortion function for source coding with side information at the decoder
- Three results on interactive communication
- Towards a reverse Newman's theorem in interactive information complexity
- Towards coding for maximum errors in interactive communication
- Towards polynomial lower bounds for dynamic problems
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Which problems have strongly exponential complexity?
- Zero-information protocols and unambiguity in Arthur-Merlin communication
This page was built for publication: Communication and information complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6200329)
