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