Bits of Kolmogorov and Shannon in a deterministic setting

The deterministic notion of (ε, δ) capacity is introduced and studied in the context of communication with squareintegrable, bandlimited signals subject to additive ε-noise. This extends the Kolmogorov 2-capacity to packing sets of overlap at most δ. For δ = 0, a previous lower bound on the 2ε-capacity is recovered, and an improved version of the upper bound is derived. For δ > 0 new bounds are obtained, and a notion of deterministic error exponent is introduced, that depends only on the transmission rate, the bandwidth, and the signal to noise ratio. The functional form of upper and lower bounds indicates that in both Kolmogorov and Shannon´s settings capacity grows linearly with the number of degrees of freedom, but only logarithmically with the signal to noise ratio. This basic information-theoretic insight transcends the details of the stochastic or deterministic description of the communication model.