  Two parties observing correlated random variables seek to run an interactive
communication protocol. How many bits must they exchange to simulate the
protocol, namely to produce a view with a joint distribution within a fixed
statistical distance of the joint distribution of the input and the transcript
of the original protocol? We present an information spectrum approach for this
problem whereby the information complexity of the protocol is replaced by its
information complexity density. Our single-shot bounds relate the communication
complexity of simulating a protocol to tail bounds for information complexity
density. As a consequence, we obtain a strong converse and characterize the
second-order asymptotic term in communication complexity for indepedent and
identically distributed observation sequences. Furthermore, we obtain a general
formula for the rate of communication complexity which applies to any sequence
of observations and protocols. Connections with results from theoretical
computer science and implications for the function computation problem are
discussed.
