Separation of the factorization norm and randomized communication complexity

DOI10.1007/S00037-025-00278-3MaRDI QIDQ6892814zbMATH OpenFDO

Authors Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, Morgan Shirley

Publication date 28 November 2025

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00037-025-00278-3

zbMATH Keywords

factorization normsrandomized communication complexity

Mathematics Subject Classification ID

Communication complexity, information complexity (68Q11) Quantum algorithms and complexity in the theory of computing (68Q12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Cites work

• Boolean functions with small spectral norm
• Classical lower bounds from quantum upper bounds
• Communication Complexity
• Dimension-free bounds and structural results in communication complexity
• Equality alone does not simulate randomness
• Factorization norms and hereditary discrepancy
• Incidences and the spectra of graphs
• Lower bound methods for sign-rank and their limitations
• Lower Bounds for Quantum Communication Complexity
• Lower bounds in communication complexity based on factorization norms
• Optimal private halfspace counting via discrepancy
• Probabilistic communication complexity
• Quantum communication complexity of symmetric predicates
• Separation of the factorization norm and randomized communication complexity
• The communication complexity of the Hamming distance problem
• The landscape of communication complexity classes
• The power of factorization mechanisms in local and central differential privacy
• The strength of equality oracles in communication

This page was built for publication: Separation of the factorization norm and randomized communication complexity

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