An estimate on the convergence of MKZ–Bézier operators

The pointwise approximation properties of the MKZ–Bézier operators M_n,α(f,x) for α≥1 have been studied in [X.M. Zeng, Rates of approximation of bounded variation functions by two generalized Meyer–König–Zeller type operators, Comput. Math. Appl. 39 (2000) 1–13]. The aim of this paper is to study the pointwise approximation of the operators M_n,α(f,x) for the other case 0<α<1. By means of some new estimate techniques and a result of Guo and Qi [S. Guo, Q. Qi, The moments for the Meyer–König and Zeller operators, Appl. Math. Lett. 20 (2007) 719–722], we establish an estimate formula on the rate of convergence of the operators M_n,α(f,x) for the case 0<α<1.     

One-way functions and circuit complexity

A finite function f is a mapping of {0, 1}ⁿ into {0, 1}^m{#}, where “#” is a symbol to be thought of as “undefined.” A family of finite functions is said to be one-way (in a circuit complexity sense) if it can be computed with polynomial-size circuits, but every family of inverses of these functions cannot. In this paper we show that, provided functions that are not one-to-one are allowed, one-way functions exist if and only if the satisfiability problem SAT does not have polynomial-size circuits. A family of functions f_i(x) can be checked if some family of polynomial-size circuits with inputs x and y can determine if f_i(x) = y. A family of functions f_i(x) can be evaluated if some family of polynomial-size circuits with input x can compute f_i(x). Can all families of total functions that can be checked also be evaluated? We show that this is true if and only if the nonuniform versions of the complexity classes P and UP co-UP are equal. A family of functions f_i is one-way for constant depth circuits if f_i can be computed with unbounded famin circuits of polynomial size and constant depth, but every family of inverses f_i⁻¹ cannot. We give two provably one-way functions (in fact permutaions) for constant-depth circuits. The second example has the stronger property that no bit of its inverse can be computed in polynomial size and constant depth.     

Perturbing Bézier coefficients for best constrained degree reduction in the L2-norm

This paper first shows how the Bézier coefficients of a given degree n polynomial are perturbed so that it can be reduced to a degree m (<n) polynomial with the constraint that continuity of a prescribed order is preserved at the two endpoints. The perturbation vector, which consists of the perturbation coefficients, is determined by minimizing a weighted Euclidean norm. The optimal degree n−1 approximation polynomial is explicitly given in Bézier form. Next the paper proves that the problem of finding a best L₂-approximation over the interval [0,1] for constrained degree reduction is equivalent to that of finding a minimum perturbation vector in a certain weighted Euclidean norm. The relevant weights are derived. This result is applied to computing the optimal constrained degree reduction of parametric Bézier curves in the L₂-norm.     

A lower bound on the mod 6 degree of the OR function

We examine the computational power of modular counting, where the modulus m is not a prime power, in the setting of polynomials in Boolean variables over Z _m . In particular, we say that a polynomial P weakly represents a Boolean function f (both have n variables) if for any inputs x and y in {0,1}ⁿ, we have whenever . Barrington et al. (1994) investigated the minimal degree of a polynomial representing the OR function in this way, proving an upper bound of O(n ^{1/ r} ) (where r is the number of distinct primes dividing m) and a lower bound of . Here, we show a lower bound of when m is a product of two primes and in general. While many lower bounds are known for a much stronger form of representation of a function by a polynomial (Barrington et al. 1994, Tsai 1996), very little is known using this liberal (and, we argue, more natural) definition. While the degree is known to be for the generalized inner product because of its high communication complexity (Grolmusz 1995), our bound is the best known for any function of low communication complexity and any modulus not a prime power. received 29 September 1994     

On multiplicativity of the Bernstein operator

For continuous functions f and g, we prove that the Bernstein operator B_n is multiplicative for all n≥1 and all x∈2[0,1] if and only if at least one of the functions f and g is a constant function. Some other variants of multiplicativity are also considered.     

Communication Complexity Method for Measuring Nondeterminism in Finite Automata

While deterministic finite automata seem to be well understood, surprisingly many important problems concerning nondeterministic finite automata (nfa's) remain open. One such problem area is the study of different measures of nondeterminism in finite automata and the estimation of the sizes of minimal nondeterministic finite automata. In this paper the concept of communication complexity is applied in order to achieve progress in this problem area. The main results are as follows:1. Deterministic communication complexity provides lower bounds on the size of nfa's with bounded unambiguity. Applying this fact, the proofs of several results about nfa's with limited ambiguity can be simplified and presented in a uniform way.2. There is a family of languages KON_k² with an exponential size gap between nfa's with polynomial leaf number/ambiguity and nfa's with ambiguity k. This partially provides an answer to the open problem posed by B. Ravikumar and O. Ibarra (1989, SIAM J. Comput.18, 1263–1282) and H. Leung (1998, SIAM J. Comput.27, 1073–1082).     

On the Autoreducibility of Functions

This paper studies the notions of self-reducibility and autoreducibility. Our main result regarding length-decreasing self-reducibility is that any complexity class C\mathcal{C} that has a (logspace) complete language and is closed under polynomial-time (logspace) padding has the property that if all C\mathcal{C} -complete languages are length-decreasing (logspace) self-reducible then C í P\mathcal{C}\subseteq \mathrm {P} (C í L\mathcal {C}\subseteq \mathrm {L} ). In particular, this result applies to NL, NP and PSPACE. We also prove an equivalent of this theorem for function classes (for example, for #P). We also show that for several hard function classes, in particular for #P, it is the case that all their complete functions are deterministically autoreducible. In particular, we show the following result. Let f be a #P parsimonious function with two preimages of 0. We show that there are two FP functions h and t such that for all inputs x we have f(x)=t(x)+f(h(x)), h(x)≠x, and t(x)∈{0,1}. Our results regarding single-query autoreducibility of #P functions can be contrasted with random self-reducibility for which it is known that if a #P complete function were random self-reducible with one query then the polynomial hierarchy would collapse.     

Bernstein-type operators which preserve polynomials

In this paper we present the sequence of linear Bernstein-type operators defined for f∈C[0,1] by B_n(f°τ⁻¹)°τ, B_n being the classical Bernstein operators and τ being any function that is continuously differentiable ∞ times on [0,1], such that τ(0)=0, τ(1)=1 and τ^′(x)>0 for x∈[0,1]. We investigate its shape preserving and convergence properties, as well as its asymptotic behavior and saturation. Moreover, these operators and others of King type are compared with each other and with B_n. We present as an interesting byproduct sequences of positive linear operators of polynomial type with nice geometric shape preserving properties, which converge to the identity, which in a certain sense improve B_n in approximating a number of increasing functions, and which, apart from the constant functions, fix suitable polynomials of a prescribed degree. The notion of convexity with respect to τ plays an important role.     

Approximation of functions by means of a new generalized Bernstein operator

In this paper we first use a probabilistic method to construct a linear positive polynomial operatorL _{m, r} ^α,β Bernstein type, depending on a non-negative integer parameterr and on two real parameters α and β, such that 0≤α≤β. Then we investigate the approximation properties of this operator mapping into itself the Banach spaceC[0,1] of real-valued continuous functions on [0,1]. A special attention is accorded to the case of the operatorL _m,r=L _m,r ^0,0 . We prove that the remainder of the approximation formula of a functionfεC[0,1] byL _m,r f can be represented either by means of divided differences, or in an integral form, obtained by using a classical theorem of Peano. We give also an asymptotic estimate for this remainder. The operatorL _m,r enjoys the variation diminishing property—in the sense of I. J. Schoenberg [15]. By extending the known inequalities of T. Popoviciu [12] and G. G. Lorentz [7], we evaluate the orders of approximation in terms of the modulus of continuity of the functionf or of its derivative. In the last section of this paper we determine the point spectrum of the operatorL _m,r and , finally, we present a quadrature formula which can be constructed by means of this operator. Dedicated to Professor Aldo Ghizzetti on his 75th birthday     

Most Sequences Are Stochastic

The central problem in machine learning (and statistics) is the problem of predicting future events x_n+1 based on past observations x₁x₂…x_n, where n=1, 2…. The main goal is to find a method of prediction that minimizes the total loss suffered on a sequence x₁x₂…x_n+1 for n=1, 2…. We say that a data sequence is stochastic if there exists a simply described prediction algorithm whose performance is close to the best possible one. This optimal performance is defined in terms of Vovk's predictive complexity, which is a generalization of the notion of Kolmogorov complexity. Predictive complexity gives a limit on the predictive performance of simply described prediction algorithms. In this paper we argue that data sequences normally occurring in the real world are stochastic; more formally, we prove that Levin's a priori semimeasure of nonstochastic sequences is small.     

The μ-basis of a planar rational curve—properties and computation

A moving line L(x,y;t)=0 is a family of lines with one parameter t in a plane. A moving line L(x,y;t)=0 is said to follow a rational curve P(t) if the point P(t₀) is on the line L(x,y;t₀)=0 for any parameter value t₀. A μ-basis of a rational curve P(t) is a pair of lowest degree moving lines that constitute a basis of the module formed by all the moving lines following P(t), which is the syzygy module of P(t). The study of moving lines, especially the μ-basis, has recently led to an efficient method, called the moving line method, for computing the implicit equation of a rational curve [3 and 6]. In this paper, we present properties and equivalent definitions of a μ-basis of a planar rational curve. Several of these properties and definitions are new, and they help to clarify an earlier definition of the μ-basis [3]. Furthermore, based on some of these newly established properties, an efficient algorithm is presented to compute a μ-basis of a planar rational curve. This algorithm applies vector elimination to the moving line module of P(t), and has O(n²) time complexity, where n is the degree of P(t). We show that the new algorithm is more efficient than the fastest previous algorithm [7].     

Limiting negations in non-deterministic circuits

The minimum number of NOT gates in a Boolean circuit computing a Boolean function f is called the inversion complexity of f. In 1958, Markov determined the inversion complexity of every Boolean function and, in particular, proved that log₂(n+1) NOT gates are sufficient to compute any Boolean function on n variables. In this paper, we consider circuits computing non-deterministically and determine the inversion complexity of every Boolean function. In particular, we prove that one NOT gate is sufficient to compute any Boolean function in non-deterministic circuits if we can use an arbitrary number of guess inputs.     

Communication Complexity of Sum-Type Functions Invariant under Translation

The communication complexity of a function f denotes the number of bits that two processors have to exchange in order to compute f(x, y), when each processor knows one of the variables x and y, respectively. In this paper the deterministic communication complexity of sum-type functions, such as the Hamming distance and the Lee distance, is examined. Here f: X × X → G, where X is a finite set and G is an Abelian group, and the sum-type function f_n:Xⁿ × Xⁿ → G is defined by f_n((x₁, ..., x_n), (y₁, ..., y_n)) = Σⁿ_i=1f(x_i, y_i) Since the functions examined are also translation-invariant, their function matrices are simultaneously diagonalizable and the corresponding eigenvalues can be calculated. This allows to apply a rank lower bound for the communication complexity. The best results are obtained for G = /2 . For prime numbers |X| in this case the communication complexity of all non-trivial sum-type functions is determined exactly. Exact results are also obtained for the parity of the Hamming distance and the parity of the Lee distance. For the Hamming distance and the Lee distance exact results are only obtained for special parameters n and |X|.     

Min-rank conjecture for log-depth circuits

A completion of an m-by-n matrix A with entries in {0,1,?} is obtained by setting all ?-entries to constants 0 and 1. A system of semi-linear equations over GF₂ has the form Mx=f(x), where M is a completion of A and f:n{0,1}→m{0,1} is an operator, the ith coordinate of which can only depend on variables corresponding to ?-entries in the ith row of A. We conjecture that no such system can have more than ²n−?⋅mr(A) solutions, where ?>0 is an absolute constant and mr(A) is the smallest rank over GF₂ of a completion of A. The conjecture is related to an old problem of proving super-linear lower bounds on the size of log-depth boolean circuits computing linear operators x?Mx. The conjecture is also a generalization of a classical question about how much larger can non-linear codes be than linear ones. We prove some special cases of the conjecture and establish some structural properties of solution sets.     

The Complexity of Finding SUBSEQ(<Emphasis Type="Italic">A</Emphasis>)

Higman showed that if A is any language then SUBSEQ(A) is regular. His proof was nonconstructive. We show that the result cannot be made constructive. In particular we show that if f takes as input an index e of a total Turing Machine M _e , and outputs a DFA for SUBSEQ(L(M _e )), then ∅″≤_T f (f is Σ ₂-hard). We also study the complexity of going from A to SUBSEQ(A) for several representations of A and SUBSEQ(A).     

Inapproximability of the Tutte polynomial

The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that encodes many interesting properties of the graph. We study the complexity of the following problem, for rationals x and y: take as input a graph G, and output a value which is a good approximation to T(G;x,y). Jaeger et al. have completely mapped the complexity of exactly computing the Tutte polynomial. They have shown that this is #P-hard, except along the hyperbola (x-1)(y-1)=1 and at four special points. We are interested in determining for which points (x,y) there is a fully polynomial randomised approximation scheme (FPRAS) for T(G;x,y). Under the assumption RP≠NP, we prove that there is no FPRAS at (x,y) if (x,y) is in one of the half-planes x<-1 or y<-1 (excluding the easy-to-compute cases mentioned above). Two exceptions to this result are the half-line x<-1,y=1 (which is still open) and the portion of the hyperbola (x-1)(y-1)=2 corresponding to y<-1 which we show to be equivalent in difficulty to approximately counting perfect matchings. We give further intractability results for (x,y) in the vicinity of the origin. A corollary of our results is that, under the assumption RP≠NP, there is no FPRAS at the point (x,y)=(0,1-λ) when λ>2 is a positive integer. Thus, there is no FPRAS for counting nowhere-zero λ flows for λ>2. This is an interesting consequence of our work since the corresponding decision problem is in P for example for λ=6. Although our main concern is to distinguish regions of the Tutte plane that admit an FPRAS from those that do not, we also note that the latter regions exhibit different levels of intractability. At certain points (x,y), for example the integer points on the x-axis, or any point in the positive quadrant, there is a randomised approximation scheme for T(G;x,y) that runs in polynomial time using an oracle for an NP predicate. On the other hand, we identify a region of points (x,y) at which even approximating T(G;x,y) is as hard as #P.     

Guaranteeing the Diversity of Number Generators

A major problem in using iterative number generators of the form x_i=f(x_i−1) is that they can enter unexpectedly short cycles. This is hard to analyze when the generator is designed, hard to detect in real time when the generator is used, and can have devastating cryptanalytic implications. In this paper we define a measure of security, called sequence diversity, which generalizes the notion of cycle-length for noniterative generators. We then introduce the class of counter-assisted generators and show how to turn any iterative generator (even a bad one designed or seeded by an adversary) into a counter-assisted generator with a provably high diversity, without reducing the quality of generators which are already cryptographically strong.     

New Results on Noncommutative and Commutative Polynomial Identity Testing

Using ideas from automata theory, we design the first polynomial deterministic identity testing algorithm for the sparse noncommutative polynomial identity testing problem. Given a noncommuting black-box polynomial f ? \mathbb F{x₁,?,x_n}f \in {\mathbb F}\{x_{1},\ldots,x_n\} of degree d with at most t monomials, where the variables x_i are noncommuting, we give a deterministic polynomial identity test that checks if C o 0C \equiv 0 and runs in time polynomial in d, n, |C|, and t. Our algorithm evaluates the black-box polynomial for x_i assigned to matrices over \mathbbF{\mathbb{F}} and, in fact, reconstructs the entire polynomial f in time polynomial in n, d and t.     

Proper Learning Algorithm for Functions of k Terms under Smooth Distributions

In this paper, we introduce a probabilistic distribution, called a smooth distribution, which is a generalization of variants of the uniform distribution such as q-bounded distribution and product distribution. Then, we give an algorithm that, under the smooth distribution, properly learns the class of functions of k terms given as _k ^k_n={g(f₁(v), …, f_k(v)) | g _k, f₁, …, f_{k n}} in polynomial time for constant k, where _k is the class of all Boolean functions of k variables and _n is the class of terms over n variables. Although class _k ^k_n was shown by Blum and Singh to be learned using DNF as the hypothesis class, it has remained open whether it is properly learnable under a distribution-free setting.     

Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials

The determinantal complexity of a polynomial f(x ₁,x ₂,…,x _n ) is the minimum m such that f=det  _m (L(x ₁,x ₂,…,x _n )), where L(x ₁,x ₂,…,x _n ) is a matrix whose entries are affine forms in the x _i s over some field $\mbox {$\mbox {.