English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We investigate the problem of approximating the product $a^TBc$, where$a,c\in S^{n-1}$ and $B\in O_n$, in models of communication complexity andstreaming algorithms. The worst meaningful approximation is to simply decidewhether the product is 1 or -1, given the promise that it is either. We callthat problem the aBc problem. This is a modification of computing approximateinner products, by allowing a basis change. While very efficient streamingalgorithms and one-way communication protocols are known for simple innerproducts (approximating $a^Tc$) we show that no efficient one-wayprotocols/streaming algorithms exist for the aBc problem. In communicationcomplexity we consider the 3-player number-in-hand model.  1) In communication complexity $a^TBc$ can be approximated within additiveerror $\epsilon$ with communication $O(\sqrt n/\epsilon^2)$ by a one-wayprotocol Charlie to Bob to Alice.  2) The $aBc$ problem has a streaming algorithm that uses space $O(\sqrt n\log n)$.  3) Any one-way communication protocol for $aBc$ needs communication at least$\Omega(n^{1/3})$, and we prove a tight results regarding a communicationtradeoff: if Charlie and Bob communicate over many rounds such that Charliecommunicates $o(n^{2/3})$ and Bob $o(n^{1/3})$, and then the transcript is sentto Alice, the error will be large.  4) To establish our lower bound we show concentration results for Renyidivergences under the event of restricting a density function on the sphere toa random equator and subsequently normalizing the restricted density function.This extends previous results by Klartag and Regev for set sizes to Renyidivergences of arbitrary density functions.  5) We show a strong concentration result for conditional Renyi divergences onbipartite systems for all $\alpha>1$.

The aBc Problem and Equator Sampling Renyi Divergences