A feedforward Sigma-Pi neural network with a single hidden layer of m neurons is given by /sup m//spl Sigma//sub j=1/c/sub j/g(n/spl Pi//sub k=1/x/sub k/-/spl theta//sub k//sup j///spl lambda//sub k//sup j/) where c/sub j/, /spl theta//sub k//sup j/, /spl lambda//sub k//spl isin/R. We investigate the approximation of arbitrary functions f: R/sup n//spl rarr/R by a Sigma-Pi neural network in the L/sup p/ norm. An L/sup p/ locally integrable function g(t) can approximate any given function, if and only if g(t) can not be written in the form /spl Sigma//sub j=1//sup n//spl Sigma//sub k=0//sup m//spl alpha//sub jk/(ln|t|)/sup j-1/t/sub k/.

We study the Hamming distance d/sub H/(X,Y) between two independent identical distributed (i.i.d.) random n-tuples X and Y over some finite set, both lower and upper bounds are derived for the expectation Ed/sub H/(X,Y) and the variance Dd/sub H/(X,Y). Also, a generalization of the Grey-Rankin bound is given.

Hypothesis testing for an arbitrarily varying source (AVS) is considered. We determine the best asymptotic exponent of the probability of error of the second kind when the first kind error probability is less than 2/sup -nr/. This result generalizes the well-known theorem of Hoeffding (1965), Blahut (1974), Csiszar and Longo (1971) for hypothesis testing with an exponential-type constraint. As a corollary in information theory, the best asymptotic error exponent and the r-optimal rate (the minimum compression rate when the error probability is less than 2/sup -nr/, r/spl ges/0) of AVS coding are determined.

Two methods of constructing binary constant-weight codes from (1) codes over GF(q) and (2) constant-weight codes over GF(q) are presented. Several classes of binary optimum constant-weight codes are derived from these methods. In general, we show that binary optimum constant-weight codes, which achieve the Johnson bound, can be constructed from optimum codes over GF(q) which achieve the Plotkin bound. Finally, several classes of optimum constant-weight codes over GF(q) are constructed.

A novel concept of distortion Kolmogorov-chaitin complexity is proposed. Bearing analogy to ordinary Kolmogorov-Chaitin complexity that represents the information content of a single message, distortion Kolmogorov-Chaitin complexity can be regarded as the amount of information about a single message that must be conveyed in order to reproduce it with a bounded distortion. This explanation is justified by the properties of distortion Kolmogorov-Chaitin complexity and the equivalences between distortion Kolmogorov-Chaitin complexity and the rate-distortion function, which are analogous to those between ordinary Kolmogorov-Chaitin complexity and the Shannon entropy. Some implications for universal almost sure data compression are also discussed.>