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 propose a linear algebraic method, rooted in the spectral properties ofgraphs, that can be used to prove lower bounds in communication complexity. Ourproof technique effectively marries spectral bounds with information-theoreticinequalities. The key insight is the observation that, in specific settings,even when data sets $X$ and $Y$ are closely correlated and have high mutualinformation, the owner of $X$ cannot convey a reasonably short message thatmaintains substantial mutual information with $Y$. In essence, from theperspective of the owner of $Y$, any sufficiently brief message $m=m(X)$ wouldappear nearly indistinguishable from a random bit sequence.  We employ this argument in several problems of communication complexity. Ourmain result concerns cryptographic protocols. We establish a lower bound forcommunication complexity of multi-party secret key agreement withunconditional, i.e., information-theoretic security. Specifically, forone-round protocols (simultaneous messages model) of secret key agreement withthree participants we obtain an asymptotically tight lower bound. This boundimplies optimality of the previously known omniscience communication protocol(this result applies to a non-interactive secret key agreement with threeparties and input data sets with an arbitrary symmetric information profile).  We consider communication problems in one-shot scenarios when the parties'inputs are not produced by any i.i.d. sources, and there are no ergodicityassumptions on the input data. In this setting, we found it natural to presentour results using the framework of Kolmogorov complexity.

Spectral approach to the communication complexity of multi-party key agreement