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:

Notes on Sum-Tests and Independence Tests

We study statistical sum-tests and independence tests, in particular for computably enumerable semimeasures on a discrete domain. Among other things, we prove that for universal semimeasures every S⁰₁\Sigma ^{0}_{1} -sum-test is bounded, but unbounded P⁰₁\Pi ^{0}_{1} -sum-tests exist, and we study to what extent the latter can be universal. For universal semimeasures, in the unary case of sum-test we leave open whether universal P⁰₁\Pi ^{0}_{1} -sum-tests exist, whereas in the binary case of independence tests we prove that they do not exist.     

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.     

When Does Eddy Viscosity Damp Subfilter Scales Sufficiently?

Large eddy simulation (LES) seeks to predict the dynamics of spatially filtered turbulent flows. The very essence is that the LES-solution contains only scales of size ≥Δ, where Δ denotes some user-chosen length scale. This property enables us to perform a LES when it is not feasible to compute the full, turbulent solution of the Navier-Stokes equations. Therefore, in case the large eddy simulation is based on an eddy viscosity model we determine the eddy viscosity such that any scales of size <Δ are dynamically insignificant. In this paper, we address the following two questions: how much eddy diffusion is needed to (a) balance the production of scales of size smaller than Δ; and (b) damp any disturbances having a scale of size smaller than Δ initially. From this we deduce that the eddy viscosity ν _e has to depend on the invariants q = \frac12tr(S²)q = \frac{1}{2}\mathrm{tr}(S^{2}) and r = -\frac13tr(S³)r= -\frac{1}{3}\mathrm{tr}(S^{3}) of the (filtered) strain rate tensor S. The simplest model is then given by n_e = \frac32(D/p)² |r|/q\nu_{e} = \frac{3}{2}(\Delta/\pi)^{2} |r|/q. This model is successfully tested for a turbulent channel flow (Re  _τ =590).     

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

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.     

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.     

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.     

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.     

Small Space Representations for Metric Min-sum k-Clustering and Their Applications

The min-sum k -clustering problem is to partition a metric space (P,d) into k clusters C ₁,…,C _k ?P such that $\sum_{i=1}^{k}\sum_{p,q\in C_{i}}d(p,q)The min-sum k -clustering problem is to partition a metric space (P,d) into k clusters C ₁,…,C _k ⊆P such that ?_i=1^k?_{p,q ? Ci}d(p,q)\sum_{i=1}^{k}\sum_{p,q\in C_{i}}d(p,q) is minimized. We show the first efficient construction of a coreset for this problem. Our coreset construction is based on a new adaptive sampling algorithm. With our construction of coresets we obtain two main algorithmic results.     

Error Analysis for hp-FEM Semi-Lagrangian Second Order BDF Method for Convection-Dominated Diffusion Problems

We present in this paper an analysis of a semi-Lagrangian second order Backward Difference Formula combined with hp-finite element method to calculate the numerical solution of convection diffusion equations in ℝ². Using mesh dependent norms, we prove that the a priori error estimate has two components: one corresponds to the approximation of the exact solution along the characteristic curves, which is O(Dt²+h^m+1(1+\frac\mathopen|logh|Dt))O(\Delta t^{2}+h^{m+1}(1+\frac{\mathopen{|}\log h|}{\Delta t})); and the second, which is O(Dt^p+|| [(u)\vec]-[(u)\vec]_h||_L^￥)O(\Delta t^{p}+\| \vec{u}-\vec{u}_{h}\|_{L^{\infty}}), represents the error committed in the calculation of the characteristic curves. Here, m is the degree of the polynomials in the finite element space, [(u)\vec]\vec{u} is the velocity vector, [(u)\vec]_h\vec{u}_{h} is the finite element approximation of [(u)\vec]\vec{u} and p denotes the order of the method employed to calculate the characteristics curves. Numerical examples support the validity of our estimates.     

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.     

Homogeneous Formulas and Symmetric Polynomials

We investigate the arithmetic formula complexity of the elementary symmetric polynomials S^k_n{S^k_n} . We show that every multilinear homogeneous formula computing S^k_n{S^k_n} has size at least k^W(logk)n{k^{\Omega(\log k)}n} , and that product-depth d multilinear homogeneous formulas for S^k_n{S^k_n} have size at least 2^W(k1/d)n{2^{\Omega(k^{1/d})}n} . Since Sⁿ_2n{S^{n}_{2n}} has a multilinear formula of size O(n ²), we obtain a superpolynomial separation between multilinear and multilinear homogeneous formulas. We also show that S^k_n{S^k_n} can be computed by homogeneous formulas of size k^O(logk)n{k^{O(\log k)}n} , answering a question of Nisan and Wigderson. Finally, we present a superpolynomial separation between monotone and non-monotone formulas in the noncommutative setting, answering a question of Nisan.     

Geometric Spanners for Weighted Point Sets

Let (S,d) be a finite metric space, where each element p∈S has a non-negative weight w (p). We study spanners for the set S with respect to the following weighted distance function:

On the Complexity of Matrix Rank and Rigidity

We revisit a well studied linear algebraic problem, computing the rank and determinant of matrices, in order to obtain completeness results for small complexity classes. In particular, we prove that computing the rank of a class of diagonally dominant matrices is complete for L\textsf{L} . We show that computing the permanent and determinant of tridiagonal matrices over ℤ is in Gap NC¹\textsf {Gap} \textsf {NC}^{1} and is hard for NC¹\textsf {NC}^{1} . We also initiate the study of computing the rigidity of a matrix: the number of entries that needs to be changed in order to bring the rank of a matrix below a given value. We show that some restricted versions of the problem characterize small complexity classes. We also look at a variant of rigidity where there is a bound on the amount of change allowed. Using ideas from the linear interval equations literature, we show that this problem is NP\textsf {NP} -hard over ℚ and that a certain restricted version is NP\textsf {NP} -complete. Restricting the problem further, we obtain variations which can be computed in PL\textsf {PL} and are hard for C₌L\textsf {C}_{=}\textsf {L} .     

Computing Diameter in the Streaming and Sliding-Window Models

We investigate the diameter problem in the streaming and sliding-window models. We show that, for a stream of nn points or a sliding window of size nn, any exact algorithm for diameter requires W(n)\Omega(n) bits of space. We present a simple e\epsilon-approximation algorithm for computing the diameter in the streaming model. Our main result is an e\epsilon-approximation algorithm that maintains the diameter in two dimensions in the sliding-window model using O((1/e^3/2) log³n(logR+loglogn + log(1/e)))O(({1}/{\epsilon^{3/2}}) \log^{3}n(\log R+\log\log n + \log ({1}/{\epsilon}))) bits of space, where RR is the maximum, over all windows, of the ratio of the diameter to the minimum non-zero distance between any two points in the window.     

Process control using VSI cause selecting control charts

The article considers the variable process control scheme for two dependent process steps with incorrect adjustment. Incorrect adjustment of a process may result in shifts in process mean, process variance, or both, ultimately affecting the quality of products. We construct the variable sampling interval (VSI) Z_{[`(X)]</sub>-Z<sub>SX<sup>2</sup></sub>{Z_{\overline{X}}-Z_{S_X^2}} and Z<sub>[`(e)]}-Z_Se²{Z_{\bar{{e}}}-Z_{S_e^2}} control charts to effectively monitor the quality variable produced by the first process step with incorrect adjustment and the quality variable produced by the second process step with incorrect adjustment, respectively. The performance of the proposed VSI control charts is measured by the adjusted average time to signal derived using a Markov chain approach. An example of the cotton yarn producing system shows the application and performance of the proposed joint VSI Z_{[`(X)]</sub> -Z<sub>SX<sup>2</sup></sub> {Z_{\overline{X}} -Z_{S_X^2 }} and Z<sub>[`(e)]} -Z_Se² {Z_{\bar{{e}}} -Z_{S_e^2 }} control charts in detecting shifts in mean and variance for the two dependent process steps with incorrect adjustment. Furthermore, the performance of the VSI Z_{[`(X)]</sub>-Z<sub>SX<sup>2</sup></sub> {Z_{\overline{X}}-Z_{S_X^2 }} and Z<sub>[`(e)]} -Z_Se² {Z_{\bar{{e}}} -Z_{S_e^2 }} control charts and the fixed sampling interval Z_{[`(X)]</sub> -Z<sub>SX<sup>2</sup></sub> {Z_{\overline{X}} -Z_{S_X^2 }} and Z<sub>[`(e)]} -Z_Se² {Z_{\bar{{e}}} -Z_{S_e^2 }} control charts are compared by numerical analysis results. These demonstrate that the former is much faster in detecting small and median shifts in mean and variance. When quality engineers cannot specify the values of variable sampling intervals, the optimum VSI Z_{[`(X)]</sub>-Z<sub>SX<sup>2</sup></sub> {Z_{\overline{X}}-Z_{S_X^2 }} and Z<sub>[`(e)]} -Z_Se² {Z_{\bar{{e}}} -Z_{S_e^2 }} control charts are also proposed by using the Quasi-Newton optimization technique.     

On Approximate Majority and Probabilistic Time

We prove new results on the circuit complexity of approximate majority, which is the problem of computing the majority of a given bit string whose fraction of 1’s is bounded away from 1/2 (by a constant). We then apply these results to obtain new relationships between probabilistic time, BPTime (t), and alternating time, ∑_O(1)Time (t). Our main results are the following:

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).     

Approximate Pattern Matching with the <Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>, <Emphasis Type="Italic">L</Emphasis><Subscript>2</Subscript> and <Emphasis Type="Italic">L</Emphasis><Subscript>∞</Subscript> Metrics

Given an alphabet Σ={1,2,…,|Σ|} text string T∈Σ ⁿ and a pattern string P∈Σ ^m , for each i=1,2,…,n−m+1 define L _p (i) as the p-norm distance when the pattern is aligned below the text and starts at position i of the text. The problem of pattern matching with L _p distance is to compute L _p (i) for every i=1,2,…,n−m+1. We discuss the problem for d=1,2,∞. First, in the case of L ₁ matching (pattern matching with an L ₁ distance) we show a reduction of the string matching with mismatches problem to the L ₁ matching problem and we present an algorithm that approximates the L ₁ matching up to a factor of 1+ε, which has an O(\frac1e²nlogmlog|S|)O(\frac{1}{\varepsilon^{2}}n\log m\log|\Sigma|) run time. Then, the L ₂ matching problem (pattern matching with an L ₂ distance) is solved with a simple O(nlog m) time algorithm. Finally, we provide an algorithm that approximates the L _∞ matching up to a factor of 1+ε with a run time of O(\frac1enlogmlog|S|)O(\frac{1}{\varepsilon}n\log m\log|\Sigma|) . We also generalize the problem of String Matching with mismatches to have weighted mismatches and present an O(nlog ⁴ m) algorithm that approximates the results of this problem up to a factor of O(log m) in the case that the weight function is a metric.