Fundamenta Informaticae

In function theory the superposition problem is known as the problem of representing a continuous function f(x₁, … ,x_k) in k variables as the composition of “simpler” functions. This problem stems from the Hilbert's thirteenth problem. In computer science good formalization for the notion of composition of functions is formula. In the paper we consider real-valued continuous functions in k variables in the cube [0,1]^k from the class ℋ^k_ωp with ω_p a special modulus of continuity (measure the smoothness of a function) defined in the paper. ℋ^k_ωp is a superset of Hölder class of functions. We present an explicit function f ∈ ℋ^k_ωp which is hard in the sense that it cannot be represented in the following way as a formula: zero level (input) gates associated with variables {x₁, … ,x_k} (different input gates can be associated with the same variable x_i ∈ {x₁, … ,x_k}), on the first level of the formula, arbitrary number s ≥ 1 of t variable functions from ℋ^t_ωp for t < k are allowed, while the second (output) level may compute any s variable Hölder function. We apply communication complexity for constructing such hard explicit function. Notice that one can show the existence of such function using the “non constructive” proof method known in function theory as Kolmogorov's entropy method.

The paper aims at tight upper bounds on the size of pattern classification circuits that can be used for a priori parameter settings in a machine learning context. The upper bounds relate the circuit size S(C) to n_L := [log₂m_L], where m_L is the number of training samples. In particular, we show that there exist unbounded fan-in threshold circuits with less than (a) S^R_cc := 2·√2^n_L + 3 gates for unbounded depth, (b) S^L_cc := 34.8 · √2^n_L + 14 · n_L − 11 · log₂n_L + 2 gates for small bounded depth, where in both cases all m_L samples are classified correctly. We note that the upper bounds do not depend on the length n of input (sample) vectors. Since n_L << n in real-world problem settings, the upper bounds return values that are suitable for practical applications. We provide experimental evidence that the circuit size estimations work well on a number of pattern classification tasks. As a result, we formulate the conjecture that [1.25 · S^R_cc or [0.07 · S^L_cc] gates are sufficient to achieve a high generalization rate of bounded-depth classification circuits.

We consider the realization of Boolean functions by combinatorial circuits with unreliable gates computing the functions from a complete final basis B. We assume that all gates of the basis can have inverse faults on the outputs independently with probability ε (ε ∈ (0, 1/2)). We describe a set M_k (k ≥ 3) of Boolean functions, presence even by one of which in basis B guarantees the computing of almost all Boolean functions by asymptotically optimal circuits with unreliability ε at ε → 0. We prove that, for almost all functions, the complexity of asymptotically circuits with unreliable gates exceeds the complexity of the minimal circuits constructed from absolutely reliable gates by a multiplicative factor of 3(1 + b) for any b > 0.

We prove some improvements for well-known upper bound of complexity of testing irreducibility of polynomials over finite fields. Also the fast modification of well-known probabilistic algorithm finding a normal bases in special finite fields is presented.

In this paper we study the representation of Boolean functions by general binary decision diagrams (BDDs). We investigate the size L(Σ) (number of inner nodes) of BDD Σ with different constraints on the number M(Σ) of its merged nodes. Furthermore, we introduce a weighted complexity measure W(Σ) = L(Σ) + ωM(Σ), where ω > 0. For the hardest Boolean function on n input variables we define the weight W_BDD(n) and the size L_BDD(n,t), where t limits the number of merged nodes. By using a new synthesis method and appropriate restrictions for the number t of merged nodes, we are able to prove tight upper and lower asymptotic bounds: W_BDD(n) = 2ⁿ/n (1 + log n ± O(1)/n), L_BDD(n,t) = 2ⁿ/log nt (1 ± O(1/n)), which have a relative error of O(1/n). Our results show how weight and structural restrictions of general BDDs influence the complexity of the hardest function in terms of high accuracy asymptotic bounds.

We consider a new expansion of nondeterministic finite automata. The goals of this consideration are: to apply some algorithms of such expansion for various problems of minimization of classical nondeterministic automata; to use such automata for describing practical anytime algorithms for the same problems of minimization; using such automata, we often can simplify some proofs for algorithms of simplification of usual nondeterministic automata.

We consider in this paper the problem of edge-minimization for nondeterministic finite automata and some connected questions. We shall formulate a new algorithm solving this problem; this algorithm is a simplification of two ones published before. The connected problems include at first algorithms of combining states. We formulate some new sufficient conditions for the possibility of such combining.

An approximate algorithm for minimization of weighted depth of decision trees is considered. A bound on accuracy of this algorithm is obtained which is unimprovable in general case. Under some natural assumptions on the class NP, the considered algorithm is close (from the point of view of accuracy) to best polynomial approximate algorithms for minimization of weighted depth of decision trees.