Scalar versus vector quantization: worst case analysis

We study the potential merits of vector quantization and show that there can be an arbitrary discrepancy between the worst case rates required for scalar and vector quantization. Specifically, we describe a random variable and a distortion measure where quantization of a single instance to within a given distortion requires an arbitrarily large number of bits in the worst case, but quantization of multiple independent instances to within the same distortion requires an arbitrarily small number of bits per instance in the worst case. We relate this discrepancy to expander graphs, representation- and cover-numbers of set systems, and a problem studied by Slepian, Wolf, and Wyner (1973)     

Average and randomized communication complexity

The communication complexity of a two-variable function f(x,y) is the number of information bits two communicators need to exchange to compute f when, initially, each knows only one of the variables. There are several communication-complexity measures corresponding to whether (1) the worst case or average number of bits is considered, (2) computation errors are allowed and (3) randomization is allowed. Tight bounds are provided for the typical behavior of all bounded-error communication-complexity measures of Boolean functions. In the present work, the authors formally define the deterministic model. They describe randomized protocols and compare them to deterministic ones. They both survey previous work and describe original results     

Repeated communication and Ramsey graphs

We study the savings afforded by repeated use in two zero-error communication problems. We show that for some random sources, communicating one instance requires arbitrarily many bits, but communicating multiple instances requires roughly 1 bit per instance. We also exhibit sources where the number of bits required for a single instance is comparable to the source's size, but two instances require only a logarithmic number of additional bits. We relate this problem to that of communicating information over a channel. Known results imply that some channels can communicate exponentially more bits in two uses than they can in one use     

Universal Compression of Markov and Related Sources Over Arbitrary Alphabets

Recent work has considered encoding a string by separately conveying its symbols and its pattern-the order in which the symbols appear. It was shown that the patterns of independent and identically distributed (i.i.d.) strings can be losslessly compressed with diminishing per-symbol redundancy. In this correspondence, the pattern redundancy of distributions with memory is considered. Close lower and upper bounds are established on the pattern redundancy of strings generated by Hidden Markov models (HMMs) with a small number of states, showing in particular that their per-symbol pattern redundancy diminishes with increasing string length. The upper bounds are obtained by analyzing the growth rate of the number of multidimensional integer partitions, and the lower bounds, using Hayman's theorem     

Lower bounds on threshold and related circuits via communicationcomplexity

Using communication complexity concepts and techniques, we derive linear (Ω(n)) and almost-linear (Ω(n/logn)) lower bounds on the size of circuits implementing certain functions. Our approach utilizes only basic features of the gates used, hence the bounds hold for general families of gates of which the symmetric and threshold gates are special cases. Each of the bounds derived is shown to be tight for some functions and some applications to threshold circuit complexity are indicated. The results generalize and in some cases strengthen recent results     

Privacy, additional information and communication

Two parties, each holding one input of a two-variable function, communicate in order to determine the value of the function. Each party wants to expose as little of its input as possible to the other party. The authors prove tight bounds on the minimum amount of information about the individual inputs that must be revealed in the computation of most functions and of some specific ones. They also show that a computation that reveals little information about the individual inputs may require many more message exchanges than a more revealing computation     

One-way communication and error-correcting codes

We establish a further connection between one-way communication where a sender conveys information to a receiver who has related information, and error-correction coding where a sender attempts to communicate reliably over a noisy channel. Using this connection we obtain three results on the two problems. We derive an often-tight lower bound on the number of bits required for one-way communication based on the largest code for the corresponding error-correction problem. We construct an error-correcting code whose minimum distance properties are similar to those of Bose-Chaudhuri-Hocquenghem (BCH) codes based on a one-way communication protocol for set reconciliation. Finally, we prove that one-way communication is suboptimal for a large class of Hamming-distance problems.     

Source coding and graph entropies

A sender wants to accurately convey information to a receiver who has some, possibly related, data. We study the expected number of bits the sender must transmit for one and for multiple instances in two communication scenarios and relate this number to the chromatic and Korner (1973) entropies of a naturally defined graph     

Worst-case interactive communication. II. Two messages are notoptimal

For pt.I see ibid., vol.36, no.5, p.1111-26, (1990). The author defines the chromatic-decomposition number of a hypergraph and shows that, under general conditions, it determines the two message complexity. This result is then used to provide that two messages are not optimal. Protocols, complexities, and the characteristic hypergraph of (X,Y) are defined. The playoffs problem is described. Although similar in appearance to the league problem given in an example, it is shown that its two-message complexity is about twice as high as its three-message complexity. The author proves a high lower bound on the chromatic-decomposition number of the playoffs problem's characteristic hypergraph showing that the problem has a high two-message complexity, and that allowing more than two messages may decrease the number of transmitted bits by a factor of two. A technique that improves the lower bound for the chromatic-decomposition number of the playoffs problem is described. However, this improved lower bound does not suffice to increase the provable gap between two and three message complexities     

Asymptotic component densities in Programmable Gate Arrays realizing all circuits of a given size

A Programmable Gate Array (PGA) is modeled as a square grid. Some grid nodes are processing nodes containing electrical elements. The rest are switching nodes capable of connecting wires incident on them. Two possible types of switching nodes are considered. In vertex connectivity each switching node can connect only one pair of wires. In edge connectivity each switching node can simultaneously connect two pairs of wires. The PGA must be capable of implementing any graph of size at mostk and degree at most 4. We prove tight bounds on the highest achievable density of processing nodes.In edge connectivity the highest achievable density is (1/k). In vertex connectivity the highest achievable density is (1/k ²). If the grid is augmented by the diagonal edges, then the highest achievable density is (1/k) even with vertex connectivity. These extend known results for embedding graphs in grids.Small graphs of degree 1 are further examined. Fork=2 andk=3 the highest density of processing nodes equals the highest density of parked cars in a square parking lot where each car can exit. Both densities are two-thirds. Fork=4 the highest density is one-half.This work was supported in part by NSF Grants NCR-8903288 and IAI-9005849.