Upper bounds on communication in terms of approximate rank

DOI10.1007/S00224-023-10158-4MaRDI QIDQ6635689zbMATH OpenFDO

Authors Anna Gál, Ridwan Syed

Publication date 12 November 2024

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00224-023-10158-4

zbMATH Keywords

approximate rankcommunication complexityquantum communication

Mathematics Subject Classification ID

Theory of computing (68Qxx) Algorithms in computer science (68Wxx) Foundations, quantum information and its processing, quantum axioms, and philosophy (81Pxx)

Cites work

• An additive combinatorics approach relating rank to communication complexity
• Communication Complexity
• Complexity measures of sign matrices
• Deterministic communication vs. partition number
• Efficient quantum protocols for XOR functions
• En route to the log-rank conjecture: new reductions and equivalent formulations
• Geometric arguments yield better bounds for threshold circuits and distributed computing
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2081103 (Why is no real title available?)
• scientific article; zbMATH DE number 1775389 (Why is no real title available?)
• scientific article; zbMATH DE number 2086394 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• scientific article; zbMATH DE number 7204275 (Why is no real title available?)
• Learning complexity vs communication complexity
• Lower Bounds for Quantum Communication Complexity
• Lower bounds in communication complexity
• Lower bounds in communication complexity based on factorization norms
• On rank vs. communication complexity
• On the distributional complexity of disjointness
• Perturbed Identity Matrices Have High Rank: Proof and Applications
• Private vs. common random bits in communication complexity
• Probabilistic communication complexity
• Quantum communication complexity of symmetric predicates
• Quantum search of spatial regions
• The approximate rank of a matrix and its algorithmic applications
• The cover number of a matrix and its algorithmic applications
• The Log-Approximate-Rank Conjecture Is False
• The Probabilistic Communication Complexity of Set Intersection

This page was built for publication: Upper bounds on communication in terms of approximate rank

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