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

Complexity of Hard-Core Set Proofs

We study a fundamental result of Impagliazzo (FOCS’95) known as the hard-core set lemma. Consider any function f:{0,1}ⁿ?{0,1}{f:\{0,1\}^n\to\{0,1\}} which is “mildly hard”, in the sense that any circuit of size s must disagree with f on at least a δ fraction of inputs. Then, the hard-core set lemma says that f must have a hard-core set H of density δ on which it is “extremely hard”, in the sense that any circuit of size s￠=O(s/(\frac1e²log(\frac1ed))){s'=O(s/(\frac{1}{\epsilon^2}\log(\frac{1}{\epsilon\delta})))} must disagree with f on at least (1-e)/2{(1-\epsilon)/2} fraction of inputs from H.     

The sudden death of entanglement in constructed Yang–Baxter systems

Some Hamiltonians are constructed from the unitary \checkR_i,i+1(q, j){\check{R}_{i,i+1}(\theta, \varphi)}-matrices, where θ and j{\varphi} are time-independent parameters. We show that the entanglement sudden death (ESD) can happen in these closed Yang–Baxter systems. It is found that the ESD is not only sensitive to the initial condition, but also has a great connection with different Yang–Baxter systems. Especially, we find that the meaningful parameter j{\varphi} has a great influence on ESD.     

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.     

Communication Complexity Under Product and Nonproduct Distributions

We solve an open problem in communication complexity posed by Kushilevitz and Nisan (1997). Let R_∈(f) and $D^\mu_\in (f)$D^\mu_\in (f) denote the randomized and μ-distributional communication complexities of f, respectively (∈ a small constant). Yao’s well-known minimax principle states that $R_{\in}(f) = max_\mu \{D^\mu_\in(f)\}$R_{\in}(f) = max_\mu \{D^\mu_\in(f)\}. Kushilevitz and Nisan (1997) ask whether this equality is approximately preserved if the maximum is taken over product distributions only, rather than all distributions μ. We give a strong negative answer to this question. Specifically, we prove the existence of a function f : {0, 1}ⁿ ×{0, 1}ⁿ ? {0, 1}f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\} for which max_{μ product} {D^m _? (f)} = Q(1)  but R _? (f) = Q(n)\{D^\mu_\in (f)\} = \Theta(1) \,{\textrm but}\, R_{\in} (f) = \Theta(n). We also obtain an exponential separation between the statistical query dimension and signrank, solving a problem previously posed by the author (2007).     

Entanglement and Berry phase in a 9 × 9 Yang–Baxter system

A M-matrix which satisfies the Hecke algebraic relations is presented. Via the Yang–Baxterization approach, we obtain a unitary solution \breveR(q,j₁,j₂){\breve{R}(\theta,\varphi_{1},\varphi_{2})} of Yang–Baxter equation. It is shown that any pure two-qutrit entangled states can be generated via the universal \breveR{\breve{R}}-matrix assisted by local unitary transformations. A Hamiltonian is constructed from the \breveR{\breve{R}}-matrix, and Berry phase of the Yang–Baxter system is investigated. Specifically, for j₁ = j₂{\varphi_{1}\,{=}\,\varphi_{2}}, the Hamiltonian can be represented based on three sets of SU(2) operators, and three oscillator Hamiltonians can be obtained. Under this framework, the Berry phase can be interpreted.     

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

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.     

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.     

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:

The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions

We prove asymptotically optimal bounds on the Gaussian noise sensitivity and Gaussian surface area of degree-d polynomial threshold functions. In particular, we show that for f a degree-d polynomial threshold function that the Gaussian noise sensitivity of f with parameter e{\epsilon} is at most \fracdarcsin(?{2e-e²})p{\frac{d\arcsin\left(\sqrt{2\epsilon-\epsilon^2}\right)}{\pi}} . This bound translates into an optimal bound on the Gaussian surface area of such functions, namely that the Gaussian surface area is at most \fracd?{2p}{\frac{d}{\sqrt{2\pi}}} . Finally, we note that the later result implies bounds on the runtime of agnostic learning algorithms for polynomial threshold functions.     

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.     

Spreading of Messages in Random Graphs

Consider the following model on the spreading of messages. A message initially convinces a set of vertices, called the seeds, of the Erdős-Rényi random graph G(n,p). Whenever more than a ρ∈(0,1) fraction of a vertex v’s neighbors are convinced of the message, v will be convinced. The spreading proceeds asynchronously until no more vertices can be convinced. This paper derives lower bounds on the minimum number of initial seeds, min-seed(n,p,d,r)\mathrm{min\hbox{-}seed}(n,p,\delta,\rho), needed to convince a δ∈{1/n,…,n/n} fraction of vertices at the end. In particular, we show that (1) there is a constant β>0 such that min-seed(n,p,d,r)=W(min{d,r}n)\mathrm{min\hbox{-}seed}(n,p,\delta,\rho)=\Omega(\min\{\delta,\rho\}n) with probability 1−n ^−Ω(1) for p≥β (ln (e/min {δ,ρ}))/(ρ n) and (2) min-seed(n,p,d,1/2)=W(dn/ln(e/d))\mathrm{min\hbox{-}seed}(n,p,\delta,1/2)=\Omega(\delta n/\ln(e/\delta)) with probability 1−exp (−Ω(δ n))−n ^−Ω(1) for all p∈[ 0,1 ]. The hidden constants in the Ω notations are independent of p.     

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.     

Distributed discovery of large near-cliques

Given an undirected graph and 0 ￡ e ￡ 1{0\le\epsilon\le1}, a set of nodes is called an e{\epsilon}-near clique if all but an e{\epsilon} fraction of the pairs of nodes in the set have a link between them. In this paper we present a fast synchronous network algorithm that uses small messages and finds a near-clique. Specifically, we present a constant-time algorithm that finds, with constant probability of success, a linear size e{\epsilon}-near clique if there exists an e³{\epsilon^3}-near clique of linear size in the graph. The algorithm uses messages of O(log n) bits. The failure probability can be reduced to n ^−Ω(1) by increasing the time complexity by a logarithmic factor, and the algorithm also works if the graph contains a clique of size Ω(n/(log log n) ^α ) for some a ? (0,1){\alpha \in (0,1)}. Our approach is based on a new idea of adapting property testing algorithms to the distributed setting.     

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.     

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.     

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.     

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.     

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.