  We propose a linear algebraic method, rooted in the spectral properties of
graphs, that can be used to prove lower bounds in communication complexity. Our
proof technique effectively marries spectral bounds with information-theoretic
inequalities. The key insight is the observation that, in specific settings,
even when data sets $X$ and $Y$ are closely correlated and have high mutual
information, the owner of $X$ cannot convey a reasonably short message that
maintains substantial mutual information with $Y$. In essence, from the
perspective of the owner of $Y$, any sufficiently brief message $m=m(X)$ would
appear nearly indistinguishable from a random bit sequence.
  We employ this argument in several problems of communication complexity. Our
main result concerns cryptographic protocols. We establish a lower bound for
communication complexity of multi-party secret key agreement with
unconditional, i.e., information-theoretic security. Specifically, for
one-round protocols (simultaneous messages model) of secret key agreement with
three participants we obtain an asymptotically tight lower bound. This bound
implies optimality of the previously known omniscience communication protocol
(this result applies to a non-interactive secret key agreement with three
parties 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 ergodicity
assumptions on the input data. In this setting, we found it natural to present
our results using the framework of Kolmogorov complexity.
