Communication and information complexity
From MaRDI portal
Publication:6200329
DOI10.4171/ICM2022/208OpenAlexW4389815267MaRDI QIDQ6200329
Publication date: 22 March 2024
Published in: International Congress of Mathematicians (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4171/icm2022/208
computational complexityinformation theoryinformation complexitycommunication complexityinteractive computation
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Information theory (general) (94A15) Communication complexity, information complexity (68Q11)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Zero-information protocols and unambiguity in Arthur-Merlin communication
- Towards a reverse Newman's theorem in interactive information complexity
- Explicit lower and upper bounds on the entangled value of multiplayer XOR games
- An information statistics approach to data stream and communication complexity
- Disjointness is hard in the multiparty number-on-the-forehead model
- Boolean function complexity. Advances and frontiers.
- Complexity measures of sign matrices
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Private vs. common random bits in communication complexity
- On the distributional complexity of disjointness
- On ACC
- Error reduction by parallel repetition - a negative result
- Which problems have strongly exponential complexity?
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- Super-logarithmic depth lower bounds via the direct sum in communication complexity
- How to Compress Interactive Communication
- Towards polynomial lower bounds for dynamic problems
- Quantum Information Complexity
- Small Value Parallel Repetition for General Games
- Simulating Noisy Channel Interaction
- Arithmetic Circuits: A survey of recent results and open questions
- A Counterexample to Strong Parallel Repetition
- Coding for interactive communication
- Constant depth circuits, Fourier transform, and learnability
- Proof verification and the hardness of approximation problems
- Parallel Repetition in Projection Games and a Concentration Bound
- Parity, circuits, and the polynomial-time hierarchy
- Interactive Information Complexity
- Interaction in Quantum Communication
- Linear FPT reductions and computational lower bounds
- A taxonomy of problems with fast parallel algorithms
- Probabilistic checking of proofs
- Average-case interactive communication
- The Probabilistic Communication Complexity of Set Intersection
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- The rate-distortion function for source coding with side information at the decoder
- Three results on interactive communication
- Privacy, additional information and communication
- A Parallel Repetition Theorem
- Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness
- Information Complexity Density and Simulation of Protocols
- Coding for Interactive Communication: A Survey
- Amortized Communication Complexity
- Communication Complexity
- An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
- Exponential Separation of Communication and External Information
- Reducibility among Combinatorial Problems
- ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
- Analysis of Boolean Functions
- Communication complexity of estimating correlations
- Communication Complexity
- Analytical approach to parallel repetition
- Some Results on Distributed Source Coding for Interactive Function Computation
- Computational Complexity
- The Infinite-Message Limit of Two-Terminal Interactive Source Coding
- Communication lower bounds for statistical estimation problems via a distributed data processing inequality
- The multiparty communication complexity of set disjointness
- Towards coding for maximum errors in interactive communication
- Elements of Information Theory
- Information Equals Amortized Communication
- From information to exact communication
- Interactive channel capacity
- A Method for the Construction of Minimum-Redundancy Codes
- Exponential Separation of Information and Communication for Boolean Functions
- On the complexity of \(k\)-SAT
- Optimal tiling of the euclidean space using permutation-symmetric bodies
This page was built for publication: Communication and information complexity
