Upper bounds on communication in terms of approximate rank

DOI10.1007/978-3-030-79416-3_7OpenAlexW3175070762MaRDI QIDQ2117081

Anna Gál, Ridwan Syed

Publication date: 21 March 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-79416-3_7

zbMATH Keywords

quantum communicationcommunication complexityapproximate rank

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Dimension-free bounds and structural results in communication complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A discrepancy lower bound for information complexity
• Probabilistic communication complexity
• Complexity measures of sign matrices
• Private vs. common random bits in communication complexity
• On the distributional complexity of disjointness
• Geometric arguments yield better bounds for threshold circuits and distributed computing
• On rank vs. communication complexity
• Quantum Computation and Quantum Information
• Communication is Bounded by Root of Rank
• Lower Bounds in Communication Complexity
• Perturbed Identity Matrices Have High Rank: Proof and Applications
• Learning Complexity vs Communication Complexity
• The Probabilistic Communication Complexity of Set Intersection
• Deterministic Communication vs. Partition Number
• Quantum communication complexity of symmetric predicates
• Communication Complexity
• The Log-Approximate-Rank Conjecture Is False
• En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations
• Efficient quantum protocols for XOR functions
• Lower Bounds for Quantum Communication Complexity
• The approximate rank of a matrix and its algorithmic applications
• Lower bounds in communication complexity based on factorization norms

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