Communication complexity of equality and error-correcting codes

DOI10.4230/LIPICS.FSTTCS.2025.37MaRDI QIDQ7391915zbMATH OpenFDO

Authors Dale Jacobs, John Jeang, V. E. Podol'skii, Morgan Prior, Ilya Volkovich

Publication date 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.FSTTCS.2025.37

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites work

• A communication-randomness tradeoff for two-processor systems
• Amortized Communication Complexity
• Boolean function complexity. Advances and frontiers.
• Bounds on tradeoffs between randomness and communication complexity
• Communication complexity
• Communication Complexity
• Communication Complexity
• Communication complexity (for algorithm designers)
• Communication complexity with defective randomness
• Equality alone does not simulate randomness
• Fooling pairs in randomized communication complexity
• scientific article; zbMATH DE number 524134 (Why is no real title available?)
• Introduction to Coding Theory
• Lifting Theorems for Equality
• Lifting with simple gadgets and applications to circuit and proof complexity
• Linear programming bounds for tree codes (Corresp.)
• Private vs. common random bits in communication complexity
• Round elimination in exact communication complexity
• The strength of equality oracles in communication

This page was built for publication: Communication complexity of equality and error-correcting codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7391915)