Sampling on the sphere by mutually orthogonal subspaces

DOI10.1137/1.9781611974782.61MaRDI QIDQ4575800zbMATH OpenOpenAlexFDO

Authors Uri Grupel

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.03714

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: The purpose of this paper is twofold. First, we provide an optimal $Omega(sqrtn)$ bits lower bound for any two-way protocol for the Vector in Subspace Communication Problem which is of bounded total rank. This result complements Raz's $O(sqrtn)$ protocol, which has a simple variant of bounded total rank. Second, we present a plausible mathematical conjecture on a measure concentration phenomenon that implies an $Omega(sqrtn)$ lower bound for a general protocol. We prove the conjecture for the subclass of sets that depend only on $O(sqrtn)$ directions.

Recommendations

• scientific article; zbMATH DE number 1975228
• Lower bounds on information complexity via zero-communication protocols and applications
• Communication lower bounds using directional derivatives

Cited in

(3)

• Sampling by intersections with random geodesics
• scientific article; zbMATH DE number 1975228 (Why is no real title available?)
• Subsampling needlet coefficients on the sphere

This page was built for publication: Sampling on the sphere by mutually orthogonal subspaces

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