The paper presents an improved collage theorem, valid for a class of signal mappings called affine blockwise average (ABA) mappings. The ABA structure is exploited to form a bound depending on norms of collage error signals at several resolutions. Compared to previously published collage theorems, the new theorem provides a much tighter bound on the maximum distance between the original signal (real world image) and the decoder attractor, given the distance between the original and the "collage" optimized by the encoder. This is achieved without contractivity constraints on the ABA mapping parameters. Finally, an encoding method in which one attempts to minimize the upper bound directly is suggested.>

An alternative procedure for reducing the computational complexity, which is applicable to both binary and multialphabet arithmetic coding, is described and its performance analysed with respect to the small increase in code length.>

The sensitivity of the global error (cost) function to the inclusion/exclusion of each synapse in the artificial neural network is estimated. Introduced are shadow arrays which keep track of the incremental changes to the synaptic weights during a single pass of back-propagating learning. The synapses are then ordered by decreasing sensitivity numbers so that the network can be efficiently pruned by discarding the last items of the sorted list. Unlike previous approaches, this simple procedure does not require a modification of the cost function, does not interfere with the learning process, and demands a negligible computational overhead.

We introduce a new approach to the issue of lossy data compression. The basic concept has been inspired by the theory of fractal geometry. The idea is to traverse the entire data string utilizing a fixed length "yardstick". The coding is achieved by transmitting, only, the sign bit (to distinguish between the ascent and the descent) and the horizontal distance covered by the "yardstick". All data values are estimated, at the receiver's site, based on this information. We have applied this approach in the context of image compression, and the preliminary results seem to be very promising. Indeed, the proposed approach is very simple (both conceptually and from the point of view computational complexity), and it seems to be well suited to the psycho-visual characteristics of human eye. The paper includes a brief description of the coding concept. Next a number of possible modifications and extensions are discussed. Finally a number of simulations are included in order to support the theoretical derivations. Good quality images are achieved with as low as .5 bit/pel.

A time–memory-processor tradeoff for the knapsack problem is proposed. While an exhaustive search over all possible solutions of an n-component knapsack requires T = 0(2n) running time, our parallel algorithm solves the problem in O(2n/2) operations and requires only 0(2n/6) processors and memory cells. It is an improvement over previous time–memory-processor tradeoffs, being the only one which outperforms the CmCs = 2" curve. Cm is the cost of the machine, i.e., the number of its processors and memory cells, and C, is the cost per solution, which is the product of the machine cost by the running time.

Two parties, who do not trust each other, wish to agree on the result of a coin toss while they are conversing by telephone. A new protocol which solves this problem is proposed and compared with previous protocols.

A "secret sharing system" permits a secret to be shared amongntrustees in such a way that anykof them can recover the secret, but anyk-1have complete uncertainty about it. A linear coding scheme for secret sharing is exhibited which subsumes the polynomial interpolation method proposed by Shamir and can also be viewed as a deterministic version of Blakley's probabilistic method. Bounds on the maximum value ofnfor a givenkand secret size are derived for any system, linear or nonlinear. The proposed scheme achieves the lower bound which, for practical purposes, differs insignificantly from the upper bound. The scheme may be extended to protect several secrets. Methods to protect against deliberate tampering by any of the trustees are also presented.

It is shown that the longest super-increasing sequence which can be constructed from a set ofnindependent uniformly distributed random variables is almost surely asymptotic to\log_{2}n. Some extensions of this result, as well as the implications for the security of knapsack-based cryptographic systems, are discussed.

Two results are presented on vector quantizers meeting necessary conditions for optimality. First a simple generalization of well-known centroid and moment properties of the squared-error distortion measure to a weighted quadratic distortion measure with an input dependent weighting is presented. The second result is an application of the squared-error special case of the first result to a simulation study of the design of1bit per sample two- and three-dimensional quantizers for a memoryless Gaussian source using the generalized Lloyd technique. The existence of multiple distinct local optima is demonstrated, thereby showing that sufficient conditions for unique local optima do not exist for this simple common case. It is also shown that at least three dimensions are required for a vector quantizer to outperform a scalar quantizer for this source.