Interpolation of Shifted-Lacunary Polynomials

Given a “black box” function to evaluate an unknown rational polynomial f ? \mathbbQ[x]f \in {\mathbb{Q}}[x] at points modulo a prime p, we exhibit algorithms to compute the representation of the polynomial in the sparsest shifted power basis. That is, we determine the sparsity $t \in {\mathbb{Z}}_{>0}$t \in {\mathbb{Z}}_{>0}, the shift a ? \mathbbQ\alpha \in {\mathbb{Q}}, the exponents 0 ￡ e₁ < e₂ < ? < e_t{0 \leq e_{1} < e_{2} < \cdots < e_{t}}, and the coefficients c₁, ?, c_t ? \mathbbQ \{0}c_{1}, \ldots , c_{t} \in {\mathbb{Q}} \setminus \{0\} such that

Lower Bounds for Agnostic Learning via Approximate Rank

We prove that the concept class of disjunctions cannot be pointwise approximated by linear combinations of any small set of arbitrary real-valued functions. That is, suppose that there exist functions f₁, ?, f_r\phi_{1}, \ldots , \phi_{r} : {− 1, 1}ⁿ → \mathbbR{\mathbb{R}} with the property that every disjunction f on n variables has $\|f - \sum\nolimits_{i=1}^{r} \alpha_{i}\phi _{i}\|_{\infty}\leq 1/3$\|f - \sum\nolimits_{i=1}^{r} \alpha_{i}\phi _{i}\|_{\infty}\leq 1/3 for some reals a₁, ?, a_r\alpha_{1}, \ldots , \alpha_{r}. We prove that then $r \geq exp \{\Omega(\sqrt{n})\}$r \geq exp \{\Omega(\sqrt{n})\}, which is tight. We prove an incomparable lower bound for the concept class of decision lists. For the concept class of majority functions, we obtain a lower bound of W(2ⁿ/n)\Omega(2^{n}/n) , which almost meets the trivial upper bound of 2ⁿ for any concept class. These lower bounds substantially strengthen and generalize the polynomial approximation lower bounds of Paturi (1992) and show that the regression-based agnostic learning algorithm of Kalai et al. (2005) is optimal.     

Characterizing sets of jobs that admit optimal greedy-like algorithms

The “Priority Algorithm” is a model of computation introduced by Borodin, Nielsen and Rackoff ((Incremental) Priority algorithms, Algorithmica 37(4):295–326, 2003) which formulates a wide class of greedy algorithms. For an arbitrary set \mathbbS\mathbb{S} of jobs, we are interested in whether or not there exists a priority algorithm that gains optimal profit on every subset of \mathbbS\mathbb{S} . In the case where the jobs are all intervals, we characterize such sets \mathbbS\mathbb{S} and give an efficient algorithm (when \mathbbS\mathbb{S} is finite) for determining this. We show that in general, however, the problem is NP-hard.     

The 1-Versus-2 Queries Problem Revisited

The 1-versus-2 queries problem, which has been extensively studied in computational complexity theory, asks in its generality whether every efficient algorithm that makes at most 2 queries to a Σ _k ^p -complete language L _k has an efficient simulation that makes at most 1 query to L _k . We obtain solutions to this problem for hypotheses weaker than previously considered. We prove that:

Tripartite entanglement sudden death in Yang-Baxter systems

In this paper, we derive unitary Yang-Baxter \breveR(q, j){\breve{R}(\theta, \varphi)} matrices from the 8×8 \mathbbM{8\times8\,\mathbb{M}} matrix and the 4 × 4 M matrix by Yang-Baxteration approach, where \mathbbM/M{\mathbb{M}/M} is the image of the braid group representation. In Yang-Baxter systems, we explore the evolution of tripartite negativity for three qubits Greenberger-Horne-Zeilinger (GHZ)-type states and W-type states and investigate the evolution of the bipartite concurrence for 2 qubits Bell-type states. We show that tripartite entanglement sudden death (ESD) and bipartite ESD all can happen in Yang-Baxter systems and find that ESD all are sensitive to the initial condition. Interestingly, we find that in the Yang-Baxter system, GHZ-type states can have bipartite entanglement and bipartite ESD, and find that in some initial conditions, W-type states have tripartite ESD while they have no bipartite Entanglement. It is worth noting that the meaningful parameter j{\varphi} has great influence on bipartite ESD for two qubits Bell-type states in the Yang-Baxter system.     

Redundant modeling in permutation weighted constraint satisfaction problems

In classical constraint satisfaction, redundant modeling has been shown effective in increasing constraint propagation and reducing search space for many problem instances. In this paper, we investigate, for the first time, how to benefit the same from redundant modeling in weighted constraint satisfaction problems (WCSPs), a common soft constraint framework for modeling optimization and over-constrained problems. Our work focuses on a popular and special class of problems, namely, permutation problems. First, we show how to automatically generate a redundant permutation WCSP model from an existing permutation WCSP using generalized model induction. We then uncover why naively combining mutually redundant permutation WCSPs by posting channeling constraints as hard constraints and relying on the standard node consistency (NC*) and arc consistency (AC*) algorithms would miss pruning opportunities, which are available even in a single model. Based on these observations, we suggest two approaches to handle the combined WCSP models. In our first approach, we propose m\text -NC_{\text c}^*m\text {-NC}_{\text c}^* and m\text -AC_{\text c}^*m\text {-AC}_{\text c}^* and their associated algorithms for effectively enforcing node and arc consistencies in a combined model with m sub-models. The two notions are strictly stronger than NC* and AC* respectively. While the first approach specifically refines NC* and AC* so as to apply to combined models, in our second approach, we propose a parameterized local consistency LB(m,Φ). The consistency can be instantiated with any local consistency Φ for single models and applied to a combined model with m sub-models. We also provide a simple algorithm to enforce LB(m,Φ). With the two suggested approaches, we demonstrate their applicabilities on several permutation problems in the experiments. Prototype implementations of our proposed algorithms confirm that applying 2\text -NC_{\text c}^*,  2\text -AC_{\text c}^*2\text {-NC}_{\text c}^*,\;2\text {-AC}_{\text c}^*, and LB(2,Φ) on combined models allow far more constraint propagation than applying the state-of-the-art AC*, FDAC*, and EDAC* algorithms on single models of hard benchmark problems.     

VPSPACE and a Transfer Theorem over the Reals

We introduce a new class VPSPACE of families of polynomials. Roughly speaking, a family of polynomials is in VPSPACE if its coefficients can be computed in polynomial space. Our main theorem is that if (uniform, constant-free) VPSPACE families can be evaluated efficiently then the class \sf PAR_{\mathbb R}\sf {PAR}_{\mathbb {R}} of decision problems that can be solved in parallel polynomial time over the real numbers collapses to \sfP_{\mathbb R}\sf{P}_{\mathbb {R}}. As a result, one must first be able to show that there are VPSPACE families which are hard to evaluate in order to separate \sfP_{\mathbb R}\sf{P}_{\mathbb {R}} from \sfNP_{\mathbb R}\sf{NP}_{\mathbb {R}}, or even from \sfPAR_{\mathbb R}\sf{PAR}_{\mathbb {R}}.     

On the solution of the fuzzy Sylvester matrix equation

In this paper, we consider the fuzzy Sylvester matrix equation AX+XB=C,AX+XB=C, where A ? \mathbbR^{n ×n}A\in {\mathbb{R}}^{n \times n} and B ? \mathbbR^{m ×m}B\in {\mathbb{R}}^{m \times m} are crisp M-matrices, C is an n×mn\times m fuzzy matrix and X is unknown. We first transform this system to an (mn)×(mn)(mn)\times (mn) fuzzy system of linear equations. Then, we investigate the existence and uniqueness of a fuzzy solution to this system. We use the accelerated over-relaxation method to compute an approximate solution to this system. Some numerical experiments are given to illustrate the theoretical results.     

Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic

In Valiant’s theory of arithmetic complexity, the classes VP and VNP are analogs of P and NP. A fundamental problem concerning these classes is the Permanent and Determinant Problem: Given a field \mathbbF{\mathbb{F}} of characteristic ≠ 2, and an integer n, what is the minimum m such that the permanent of an n × n matrix X = (x_ij) can be expressed as a determinant of an m × m matrix, where the entries of the determinant matrix are affine linear functions of x_ij ’s, and the equality is in \mathbbF[X]{\mathbb{F}}[{\bf X}]. Mignon and Ressayre (2004) proved a quadratic lower bound m = W(n²)m = \Omega(n^{2}) for fields of characteristic 0. We extend the Mignon–Ressayre quadratic lower bound to all fields of characteristic ≠ 2.     

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.     

Fuzzy sets and cut systems in a category of sets with similarity relations

Let \Upomega\Upomega be a complete residuated lattice. Let SetR(\Upomega){\mathbf{SetR}}(\Upomega) be the category of sets with similarity relations with values in \Upomega\Upomega (called \Upomega\Upomega-sets), which is an analogy of the category of classical sets with relations as morphisms. A fuzzy set in an \Upomega\Upomega-set in the category SetR(\Upomega){\mathbf{SetR}}(\Upomega) is a morphism from \Upomega\Upomega-set to a special \Upomega\Upomega-set (\Upomega,?),(\Upomega,\leftrightarrow), where ?\leftrightarrow is the biresiduation operation in \Upomega.\Upomega. In the paper, we prove that fuzzy sets in \Upomega\Upomega-sets in the category SetR(\Upomega){\mathbf{SetR}}(\Upomega) can be expressed equivalently as special cut systems (C_a)_{a ? \Upomega}.(C_{\alpha})_{\alpha\in\Upomega}.     

Comparing Nontriviality for E and EXP

A set A is nontrivial for the linear-exponential-time class E=DTIME(2 ^lin ) if for any k≥1 there is a set B _k ∈E such that B _k is (p-m-)reducible to A and B_k ? DTIME(2^k·n)B_{k} \not\in \mathrm{DTIME}(2^{k\cdot n}). I.e., intuitively, A is nontrivial for E if there are arbitrarily complex sets in E which can be reduced to A. Similarly, a set A is nontrivial for the polynomial-exponential-time class EXP=DTIME(2 ^poly ) if for any k≥1 there is a set [^(B)]_k ? EXP\hat{B}_{k} \in \mathrm {EXP} such that [^(B)]_k\hat{B}_{k} is reducible to A and [^(B)]_k ? DTIME(2^nk)\hat{B}_{k} \not\in \mathrm{DTIME}(2^{n^{k}}). We show that these notions are independent, namely, there are sets A ₁ and A ₂ in E such that A ₁ is nontrivial for E but trivial for EXP and A ₂ is nontrivial for EXP but trivial for E. In fact, the latter can be strengthened to show that there is a set A∈E which is weakly EXP-hard in the sense of Lutz (SIAM J. Comput. 24:1170–1189, 11) but E-trivial.     

Prediction of phosphorus content of electroless nickel–phosphorous coatings using artificial neural network modeling

A multilayer feedforward neural network with two hidden layers was designed and developed for prediction of the phosphorus content of electroless Ni–P coatings. The input parameters of the network were the pH, metal turnover, and loading of an electroless bath. The output parameter was the phosphorus content of the electroless Ni–P coatings. The temperature and molar rate of the bath were constant ( 91^° \textC, 0.4 \textNi^{\text + +} /\textH₂ \textPO₂ ^{- -} 91^\circ {\text{C}},\:0.4\,{\text{Ni}}^{{{\text{ + + }}}} /{\text{H}}_{2} {\text{PO}}_{2}^{{ - - }} ). The network was trained and tested using the data gathered from our own experiments. The goal of the study was to estimate the accuracy of this type of neural network in prediction of the phosphorus content. The study result shows that this type of network has high accuracy even when the number of hidden neurons is very low. Some comparison between the network’s predictions and own experimental data are given.     

On the efficiency of quantum algorithms for Hamiltonian simulation

We study algorithms simulating a system evolving with Hamiltonian H = ?_j=1^m H_j{H = \sum_{j=1}^m H_j} , where each of the H _j , j = 1, . . . ,m, can be simulated efficiently. We are interested in the cost for approximating e^-iHt, t ? \mathbbR{e^{-iHt}, t \in \mathbb{R}} , with error e{\varepsilon} . We consider algorithms based on high order splitting formulas that play an important role in quantum Hamiltonian simulation. These formulas approximate e ^−iHt by a product of exponentials involving the H _j , j = 1, . . . ,m. We obtain an upper bound for the number of required exponentials. Moreover, we derive the order of the optimal splitting method that minimizes our upper bound. We show significant speedups relative to previously known results.     

The individual ergodic theorem on the IF-events with product

The ergodic theory and particularly the individual ergodic theorem were studied in many structures. Recently the individual ergodic theorem has been proved for MV-algebras of fuzzy sets (Riečan in Czech Math J 50(125):673–680, 2000; Riečan and Neubrunn in Integral, measure, and ordering. Kluwer, Dordrecht, 1997) and even in general MV-algebras (Jurečková in Int J Theor Phys 39:757–764, 2000). The notion of almost everywhere equality of observables was introduced by Riečan and Jurečková (Int J Theor Phys 44:1587–1597, 2005). They proved that the limit of Cesaro means is an invariant observable for P-observables. In Lendelová (Int J Theor Phys 45(5):915–923, 2006c) showed that the assumption of P-observable can be omitted. In this paper we prove the individual ergodic theorem on family of IF-events and show that each P {\mathcal{P}} -preserving transformation in this family can be expressed by two corresponding P^\flat,P^\sharp {\mathcal{P}}^\flat,{\mathcal{P}}^\sharp -preserving transformations in tribe T. {\mathcal{T}}.     

An improved algorithm on the content of realizable fuzzy matrices

An n×nn{\times}n fuzzy matrix A is called realizable if there exists an n×tn{\times}t fuzzy matrix B such that A=B\odot B^T,A=B\odot B^{T}, where \odot\odot is the max–min composition. Let r(A)=min{p:A=B\odot B^T, B ? L^n×p}.r(A)={min}\{p:A=B\odot B^{T}, B\in L^{n\times p}\}. Then r(A)r(A) is called the content of A. Since 1982, how to calculate r(A) for a given n×nn{\times}n realizable fuzzy matrix A was a focus problem, many researchers have made a lot of research work. X. P. Wang in 1999 gave an algorithm to find the fuzzy matrix B and calculate r(A) within [r(A)]ⁿ²[r(A)]^{n^{2}} steps. Therefore, to find a simpler algorithm is a problem what we have to consider. This paper makes use of the symmetry of the realizable fuzzy matrix A to simplify the algorithm of content r(A)r(A) based on the work of Wang (Chin Ann Math A 6: 701–706, 1999).     

Strong-Stability-Preserving 7-Stage Hermite–Birkhoff Time-Discretization Methods

Optimal, 7-stage, explicit, strong-stability-preserving (SSP) Hermite–Birkhoff (HB) methods of orders 4 to 8 with nonnegative coefficients are constructed by combining linear k-step methods with a 7-stage Runge–Kutta (RK) method of order 4. Compared to Huang’s hybrid methods of the same order, the new methods generally have larger effective SSP coefficients and larger maximum effective CFL numbers, \textnum_\texteff\text{num}_{\text{eff}}, on Burgers’ equation, independently of the number k of steps, especially when k is small for both methods. Based on \textnum_\texteff\text{num}_{\text{eff}}, some new methods of order 4 compare favorably with other methods of the same order, including RK104 of Ketcheson. The new SSP HB methods are listed in their Shu–Osher representation in Appendix.     

Online variance minimization

We consider the following type of online variance minimization problem: In every trial t our algorithms get a covariance matrix C ^t and try to select a parameter vector w ^t−1 such that the total variance over a sequence of trials ?_t=1^T (w^t-1)^T C^tw^t-1\sum_{t=1}^{T} (\boldsymbol {w}^{t-1})^{\top} \boldsymbol {C}^{t}\boldsymbol {w}^{t-1} is not much larger than the total variance of the best parameter vector u chosen in hindsight. Two parameter spaces in ℝ ⁿ are considered—the probability simplex and the unit sphere. The first space is associated with the problem of minimizing risk in stock portfolios and the second space leads to an online calculation of the eigenvector with minimum eigenvalue of the total covariance matrix ?_t=1^T C^t\sum_{t=1}^{T} \boldsymbol {C}^{t}. For the first parameter space we apply the Exponentiated Gradient algorithm which is motivated with a relative entropy regularization. In the second case, the algorithm has to maintain uncertainty information over all unit directions u. For this purpose, directions are represented as dyads uu ^⊤ and the uncertainty over all directions as a mixture of dyads which is a density matrix. The motivating divergence for density matrices is the quantum version of the relative entropy and the resulting algorithm is a special case of the Matrix Exponentiated Gradient algorithm. In each of the two cases we prove bounds on the additional total variance incurred by the online algorithm over the best offline parameter.     

Generalized fuzzy interior ideals of semigroups

The concept of $(\overline{\in},\overline{\in} \vee \overline{q})The concept of ([`( ? )],[`( ? )] ú[`(q)])(\overline{\in},\overline{\in} \vee \overline{q})-fuzzy interior ideals of semigroups is introduced and some related properties are investigated. In particular, we describe the relationships among ordinary fuzzy interior ideals, (∈, ∈ ∨ q)-fuzzy interior ideals and ([`( ? )],[`( ? )] ú[`(q)])(\overline{\in},\overline{\in} \vee \overline{q})-fuzzy interior ideals of semigroups. Finally, we give some characterization of [F] _t by means of (∈, ∈ ∨ q)-fuzzy interior ideals.     

Lower estimation of approximation rate for neural networks

Let SFd and Πψ,n,d = { nj=1bjψ(ωj·x+θj) :bj,θj∈R,ωj∈Rd} be the set of periodic and Lebesgue’s square-integrable functions and the set of feedforward neural network (FNN) functions, respectively. Denote by dist (SF d, Πψ,n,d) the deviation of the set SF d from the set Πψ,n,d. A main purpose of this paper is to estimate the deviation. In particular, based on the Fourier transforms and the theory of approximation, a lower estimation for dist (SFd, Πψ,n,d) is proved. That is, dist(SF d, Πψ,n,d) (nlogC2n)1/2 . T...