共查询到20条相似文献,搜索用时 31 毫秒
1.
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 f1, ?, fr\phi_{1}, \ldots , \phi_{r} : {− 1, 1}n →
\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 a1, ?, ar\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(2n/n)\Omega(2^{n}/n) , which almost meets the trivial upper bound of 2n 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. 相似文献
2.
Davod Khojasteh Salkuyeh 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2011,15(5):953-961
In this paper, we consider the fuzzy Sylvester matrix equation AX+XB=C,AX+XB=C, where
A ? \mathbbRn ×nA\in {\mathbb{R}}^{n \times n} and
B ? \mathbbRm ×mB\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. 相似文献
3.
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{x1,?,xn}f \in {\mathbb F}\{x_{1},\ldots,x_n\} of degree d with at most t monomials, where the variables xi 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 xi assigned to matrices over
\mathbbF{\mathbb{F}} and, in fact, reconstructs the entire polynomial f in time polynomial in n, d and t. 相似文献
4.
We study algorithms simulating a system evolving with Hamiltonian H = ?j=1m Hj{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. 相似文献
5.
Quantitative Separation Logic and Programs with Lists 总被引:1,自引:0,他引:1
This paper presents an extension of a decidable fragment of Separation Logic for singly-linked lists, defined by Berdine et
al. (2004). Our main extension consists in introducing atomic formulae of the form ls
k
(x, y) describing a list segment of length k, stretching from x to y, where k is a logical variable interpreted over positive natural numbers, that may occur further inside Presburger constraints. We
study the decidability of the full first-order logic combining unrestricted quantification of arithmetic and location variables.
Although the full logic is found to be undecidable, validity of entailments between formulae with the quantifier prefix in
the language
$* {$\mathbbN, "\mathbbN}*\exists^* \{\exists_{\bf \mathbb{N}}, \forall_{\bf \mathbb{N}}\}^* is decidable. We provide here a model theoretic method, based on a parametric notion of shape graphs. We have implemented
our decision technique, providing a fully automated framework for the verification of quantitative properties expressed as
pre- and post-conditions on programs working on lists and integer counters. 相似文献
6.
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. 相似文献
7.
Antoine Chaillet Yacine Chitour Antonio Loría Mario Sigalotti 《Mathematics of Control, Signals, and Systems (MCSS)》2008,20(2):135-156
Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, ${\int_t^{t+T}\alpha(s){\rm d}s \geq \mu}Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, . In particular, when α(t) becomes zero the system dynamics switches to an uncontrollable system. In this paper, we address the following question:
is it possible to find a linear time-invariant state-feedback u = Kx, with K only depending on (A, B) and possibly on μ, T, which globally asymptotically stabilizes the system? We give a positive answer to this question for two cases: when A is neutrally stable and when the system is the double integrator.
Notation A continuous function is of class
, if it is strictly increasing and is of class if it is continuous, non-increasing and tends to zero as its argument tends to infinity. A function is said to be a class
-function if, for any t ≥ 0, and for any s ≥ 0. We use |·| for the Euclidean norm of vectors and the induced L
2-norm of matrices. 相似文献
8.
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 ℝ2. 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(Dt2+hm+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(Dtp+|| [(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. 相似文献
9.
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. 相似文献
10.
Alexander A. Sherstov 《Computational Complexity》2010,19(1):135-150
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}n ×{0, 1}n ? {0, 1}f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\} for which maxμ product {Dm ? (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). 相似文献
11.
Yi-Fan Han Gui-Jun Zhang Xin-Lei Yong Ling-Shan Xu Yuan-Hong Tao 《Quantum Information Processing》2018,17(3):58
A way of constructing special entangled basis with fixed Schmidt number 2 (SEB2) in \({\mathbb {C}}^3 \otimes {\mathbb {C}}^{4k}(k\in z^+,3\not \mid k)\) is proposed, and the conditions mutually unbiased SEB2s (MUSEB2s) satisfy are discussed. In addition, a very easy way of constructing MUSEB2s in \({\mathbb {C}}^3 \otimes {\mathbb {C}}^{4k}(k=2^l)\) is presented. We first establish the concrete construction of SEB2 and MUSEB2s in \({\mathbb {C}}^3 \otimes {\mathbb {C}}^{4}\) and \({\mathbb {C}}^3 \otimes {\mathbb {C}}^{8}\), respectively, and then generalize them into \({\mathbb {C}}^3 \otimes {\mathbb {C}}^{4k}(k\in z^+,3\not \mid k)\) and display the condition that MUSEB2s satisfy; we also give general form of two MUSEB2s as examples in \({\mathbb {C}}^3 \otimes {\mathbb {C}}^{4k}(k=2^l)\). 相似文献
12.
Process control using VSI cause selecting control charts 总被引:1,自引:1,他引:0
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)]-ZSX2{Z_{\overline{X}}-Z_{S_X^2}} and Z[`(e)]-ZSe2{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)] -ZSX2 {Z_{\overline{X}} -Z_{S_X^2 }} and Z[`(e)] -ZSe2 {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)]-ZSX2 {Z_{\overline{X}}-Z_{S_X^2 }} and Z[`(e)] -ZSe2 {Z_{\bar{{e}}} -Z_{S_e^2 }} control charts and the fixed sampling interval Z[`(X)] -ZSX2 {Z_{\overline{X}} -Z_{S_X^2 }} and Z[`(e)] -ZSe2 {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)]-ZSX2 {Z_{\overline{X}}-Z_{S_X^2 }} and Z[`(e)] -ZSe2 {Z_{\bar{{e}}} -Z_{S_e^2 }} control charts are also proposed by using the Quasi-Newton optimization technique. 相似文献
13.
VPSPACE and a Transfer Theorem over the Reals 总被引:1,自引:1,他引:0
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}}. 相似文献
14.
E. A. Timofeev 《Automatic Control and Computer Sciences》2017,51(7):634-638
Recall that Lebesgue’s singular function L(t) is defined as the unique solution to the equation L(t) = qL(2t) + pL(2t ? 1), where p, q > 0, q = 1 ? p, p ≠ q. The variables M n = ∫01t n dL(t), n = 0,1,… are called the moments of the function The principal result of this work is \({M_n} = {n^{{{\log }_2}p}}{e^{ - \tau (n)}}(1 + O({n^{ - 0.99}}))\), where the function τ(x) is periodic in log2x with the period 1 and is given as \(\tau (x) = \frac{1}{2}1np + \Gamma '(1)lo{g_2}p + \frac{1}{{1n2}}\frac{\partial }{{\partial z}}L{i_z}( - \frac{q}{p}){|_{z = 1}} + \frac{1}{{1n2}}\sum\nolimits_{k \ne 0} {\Gamma ({z_k})L{i_{{z_k} + 1}}( - \frac{q}{p})} {x^{ - {z_k}}}\), \({z_k} = \frac{{2\pi ik}}{{1n2}}\), k ≠ 0. The proof is based on poissonization and the Mellin transform. 相似文献
15.
D. Gangopadhyay 《Gravitation and Cosmology》2010,16(3):231-238
A lagrangian for a k-essence field is constructed for a constant scalar potential, and its form is determined when the scale factor is very small
as compared to the present epoch but very large as compared to the inflationary epoch. This means that one is already in an
expanding and flat universe. The form is similar to that of an oscillator with time-dependent frequency. Expansion is naturally
built into the theory with the existence of growing classical solutions of the scale factor. The formalism allows one to estimate
the temperature fluctuations of the background radiation at these early stages (as compared to the present epoch) of the Universe.
If the temperature is T
a
at time t
a
and T
b
at time t
b
(t
b
> t
a
), then, for small times, the probability evolution for the logarithm of the inverse temperature can be estimated as
$
P\left( {b,a} \right) = \left| {\left\langle {\ln \left( {{1 \mathord{\left/
{\vphantom {1 {T_b }}} \right.
\kern-\nulldelimiterspace} {T_b }}} \right),t_b } \right.} \right|\left. {\left. {\ln \left( {{1 \mathord{\left/
{\vphantom {1 {T_a }}} \right.
\kern-\nulldelimiterspace} {T_a }}} \right),t_a } \right\rangle } \right|^2 \approx \left( {\frac{{3m_{Pl}^2 }}
{{\pi ^2 \left( {t_b - t_a } \right)^3 }}} \right)\left( {\ln T_a } \right)^2 \left( {\ln Tb} \right)^2 \left( {1 - 3\gamma \left( {t_a + t_b } \right)} \right)
$
P\left( {b,a} \right) = \left| {\left\langle {\ln \left( {{1 \mathord{\left/
{\vphantom {1 {T_b }}} \right.
\kern-\nulldelimiterspace} {T_b }}} \right),t_b } \right.} \right|\left. {\left. {\ln \left( {{1 \mathord{\left/
{\vphantom {1 {T_a }}} \right.
\kern-\nulldelimiterspace} {T_a }}} \right),t_a } \right\rangle } \right|^2 \approx \left( {\frac{{3m_{Pl}^2 }}
{{\pi ^2 \left( {t_b - t_a } \right)^3 }}} \right)\left( {\ln T_a } \right)^2 \left( {\ln Tb} \right)^2 \left( {1 - 3\gamma \left( {t_a + t_b } \right)} \right)
相似文献
16.
The notions of $(\overline{\in}, \overline{\in} \vee \overline{\hbox{q}})
17.
Direction-based surrounder queries for mobile recommendations 总被引:1,自引:0,他引:1
Xi Guo Baihua Zheng Yoshiharu Ishikawa Yunjun Gao 《The VLDB Journal The International Journal on Very Large Data Bases》2011,20(5):743-766
Location-based recommendation services recommend objects to the user based on the user’s preferences. In general, the nearest
objects are good choices considering their spatial proximity to the user. However, not only the distance of an object to the
user but also their directional relationship are important. Motivated by these, we propose a new spatial query, namely a direction-based surrounder (DBS) query, which retrieves the nearest objects around the user from different directions. We define the DBS query not only
in a two-dimensional Euclidean space
\mathbbE{\mathbb{E}} but also in a road network
\mathbbR{\mathbb{R}} . In the Euclidean space
\mathbbE{\mathbb{E}} , we consider two objects a and b are directional close w.r.t. a query point q iff the included angle Daqb{\angle aqb} is bounded by a threshold specified by the user at the query time. In a road network
\mathbbR{\mathbb{R}} , we consider two objects a and b are directional close iff their shortest paths to q overlap. We say object a dominates object b iff they are directional close and meanwhile a is closer to q than b. All the objects that are not dominated by others based on the above dominance relationship constitute direction-based surrounders (DBSs). In this paper, we formalize the DBS query, study it in both the snapshot and continuous settings, and conduct extensive
experiments with both real and synthetic datasets to evaluate our proposed algorithms. The experimental results demonstrate
that the proposed algorithms can answer DBS queries efficiently. 相似文献
18.
Sayed Yousef Monir Vaghefi Sayed Mahmoud Monir Vaghefi 《Neural computing & applications》2011,20(7):1055-1060
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 + + /\textH2 \textPO2 - - 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. 相似文献
19.
Avram Sidi 《Journal of scientific computing》2013,54(1):145-176
In the first part of this work, we derive compact numerical quadrature formulas for finite-range integrals $I[f]=\int^{b}_{a}f(x)\,dx$ , where f(x)=g(x)|x?t| ?? , ?? being real. Depending on the value of ??, these integrals are defined either in the regular sense or in the sense of Hadamard finite part. Assuming that g??C ??[a,b], or g??C ??(a,b) but can have arbitrary algebraic singularities at x=a and/or x=b, and letting h=(b?a)/n, n an integer, we derive asymptotic expansions for ${T}^{*}_{n}[f]=h\sum_{1\leq j\leq n-1,\ x_{j}\neq t}f(x_{j})$ , where x j =a+jh and t??{x 1,??,x n?1}. These asymptotic expansions are based on some recent generalizations of the Euler?CMaclaurin expansion due to the author (A.?Sidi, Euler?CMaclaurin expansions for integrals with arbitrary algebraic endpoint singularities, in Math. Comput., 2012), and are used to construct our quadrature formulas, whose accuracies are then increased at will by applying to them the Richardson extrapolation process. We pay particular attention to the case in which ??=?2 and f(x) is T-periodic with T=b?a and $f\in C^{\infty}(-\infty,\infty)\setminus\{t+kT\}^{\infty}_{k=-\infty}$ , which arises in the context of periodic hypersingular integral equations. For this case, we propose the remarkably simple and compact quadrature formula $\widehat{Q}_{n}[f]=h\sum^{n}_{j=1}f(t+jh-h/2)-\pi^{2} g(t)h^{-1}$ , and show that $\widehat{Q}_{n}[f]-I[f]=O(h^{\mu})$ as h??0 ???>0, and that it is exact for a class of singular integrals involving trigonometric polynomials of degree at most n. We show how $\widehat{Q}_{n}[f]$ can be used for solving hypersingular integral equations in an efficient manner. In the second part of this work, we derive the Euler?CMaclaurin expansion for integrals $I[f]=\int^{b}_{a} f(x)dx$ , where f(x)=g(x)(x?t) ?? , with g(x) as before and ??=?1,?3,?5,??, from which suitable quadrature formulas can be obtained. We revisit the case of ??=?1, for which the known quadrature formula $\widetilde{Q}_{n}[f]=h\sum^{n}_{j=1}f(t+jh-h/2)$ satisfies $\widetilde{Q}_{n}[f]-I[f]=O(h^{\mu})$ as h??0 ???>0, when f(x) is T-periodic with T=b?a and $f\in C^{\infty}(-\infty,\infty)\setminus\{t+kT\}^{\infty}_{k=-\infty}$ . We show that this formula too is exact for a class of singular integrals involving trigonometric polynomials of degree at most n?1. We provide numerical examples involving periodic integrands that confirm the theoretical results. 相似文献
20.
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 = (xij) can be expressed as a determinant of an m × m matrix, where the entries of the determinant matrix are affine linear functions of xij ’s, and the equality is in
\mathbbF[X]{\mathbb{F}}[{\bf X}]. Mignon and Ressayre (2004) proved a quadratic lower bound m = W(n2)m = \Omega(n^{2}) for fields of characteristic 0. We extend the Mignon–Ressayre quadratic lower bound to all fields of characteristic ≠ 2. 相似文献
|