We obtain asymptotically tight bounds on the maximum amount of information that a single bit of memory can retain about the entire past. At each of n successive epochs, a single fair bit is generated and a one-bit memory is updated according to a family of memory update rules (possibly probabilistic and time-dependent) depending only on the value of the new input bit and on the current state of the memory. The problem is to estimate the supremum over all possible update rules of the minimum mutual information between the state of the memory at time (n + 1) and each of the previous n input bits. We show that this supremum is asymptotically equal to 1/(2n/sup 2/ ln 2) bit, as conjectured by Venkatesh and Franklin (1991). We use this result to derive asymptotically sharp estimates of related maximin correlations between the memory and the input bits, thus resolving two more questions left open by Venkatesh and Franklin and by Komlos et al. (1993). Finally, we generalize the results to the case of an m-bit memory, again obtaining asymptotically tight bounds in many cases.

A sender communicates with a receiver who wishes to reliably evaluate a function of their combined data. We show that if only the sender can transmit, the number of bits required is a conditional entropy of a naturally defined graph. We also determine the number of bits needed when the communicators exchange two messages.

Multilevel diversity coding was introduced in recent work by Roche (1992) and Yeung (1995). In a multilevel diversity coding system, an information source is encoded by a number of encoders. There is a set of decoders, partitioned into multiple levels, with each decoder having access to a certain subset of the encoders. The reconstructions of the source by decoders within the same level are identical and are subject to the same distortion criterion. Inspired by applications in computer communication and fault-tolerant data retrieval, we study a multilevel diversity coding problem with three levels for which the connectivity between the encoders and decoders is symmetrical. We obtain a single-letter characterization of the coding rate region and show that coding by superposition is optimal for this problem. Generalizing to a symmetrical problem with an arbitrary number of levels, we derive a tight lower bound on the coding rate sum.

Article Free Access Share on On the optimal capacity of binary neural networks: rigorous combinatorial approaches Authors: Jeong Han Kim Mathematical Sciences Research Center, AT&T Bell Laboratories, Murray Hill, NJ Mathematical Sciences Research Center, AT&T Bell Laboratories, Murray Hill, NJView Profile , James R. Roche Mathematical Sciences Research Center, AT&T Bell Laboratories, Murray Hill, NJ Mathematical Sciences Research Center, AT&T Bell Laboratories, Murray Hill, NJView Profile Authors Info & Claims COLT '95: Proceedings of the eighth annual conference on Computational learning theoryJuly 1995 Pages 240–249https://doi.org/10.1145/225298.225327Published:05 July 1995Publication History 0citation550DownloadsMetricsTotal Citations0Total Downloads550Last 12 Months11Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A sender communicates with a receiver who wishes to reliably evaluate a function of their combined data. We show that if only the sender can transmit, the number of bits required is a conditional entropy of a naturally defined graph. We also determine the number of bits needed when the communicators exchange two messages.