共查询到20条相似文献,搜索用时 236 毫秒
1.
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 £ e1 < e2 < ? < et{0 \leq e_{1} < e_{2} < \cdots < e_{t}}, and the coefficients
c1, ?, ct ? \mathbbQ \{0}c_{1}, \ldots , c_{t} \in {\mathbb{Q}} \setminus \{0\} such that
f(x) = c1(x-a)e1+c2(x-a)e2+ ?+ct(x-a)etf(x) = c_{1}(x-\alpha)^{e_{1}}+c_{2}(x-\alpha)^{e_{2}}+ \cdots +c_{t}(x-\alpha)^{e_{t}} 相似文献
2.
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. 相似文献
3.
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. 相似文献
4.
The concept of $(\overline{\in},\overline{\in} \vee \overline{q})
5.
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. 相似文献
6.
Complexity of Hard-Core Set Proofs 总被引:1,自引:1,他引:0
We study a fundamental result of Impagliazzo (FOCS’95) known as the hard-core set lemma. Consider any function f:{0,1}n?{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/(\frac1e2log(\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. 相似文献
7.
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 e3{\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. 相似文献
8.
Emanuele Viola 《Computational Complexity》2009,18(3):337-375
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:
9.
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. 相似文献
10.
Philippe Raïpin Parvédy Michel Raynal Corentin Travers 《Theory of Computing Systems》2010,47(1):259-287
The k-set agreement problem is a generalization of the consensus problem: considering a system made up of n processes where each process proposes a value, each non-faulty process has to decide a value such that a decided value is a proposed value, and no more than k different values are decided. It has recently be shown that, in the crash failure model, $\min(\lfloor \frac{f}{k}\rfloor+2,\lfloor \frac{t}{k}\rfloor +1)
11.
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}
12.
An edge-Markovian process with birth-rate p and death-rate q generates infinite sequences of graphs (G
0, G
1, G
2,…) with the same node set [n] such that G
t
is obtained from G
t-1 as follows: if e ? E(Gt-1){e\notin E(G_{t-1})} then e ? E(Gt){e\in E(G_{t})} with probability p, and if e ? E(Gt-1){e\in E(G_{t-1})} then e ? E(Gt){e\notin E(G_{t})} with probability q. In this paper, we establish tight bounds on the complexity of flooding in edge-Markovian graphs, where flooding is the basic
mechanism in which every node becoming aware of an information at step t forwards this information to all its neighbors at all forthcoming steps t′ > t. These bounds complete previous results obtained by Clementi et al. Moreover, we also show that flooding in dynamic graphs
can be implemented in a parsimonious manner, so that to save bandwidth, yet preserving efficiency in term of simplicity and
completion time. For a positive integer k, we say that the flooding protocol is k-active if each node forwards an information only during the k time steps immediately following the step at which the node receives that information for the first time. We define the reachability threshold for the flooding protocol as the smallest integer k such that, for any source s ? [n]{s\in [n]} , the k-active flooding protocol from s completes (i.e., reaches all nodes), and we establish tight bounds for this parameter. We show that, for a large spectrum
of parameters p and q, the reachability threshold is by several orders of magnitude smaller than the flooding time. In particular, we show that
it is even constant whenever the ratio p/(p + q) exceeds log n/n. Moreover, we also show that being active for a number of steps equal to the reachability threshold (up to a multiplicative
constant) allows the flooding protocol to complete in optimal time, i.e., in asymptotically the same number of steps as when being perpetually active. These results demonstrate that flooding
can be implemented in a practical and efficient manner in dynamic graphs. The main ingredient in the proofs of our results
is a reduction lemma enabling to overcome the time dependencies in edge-Markovian dynamic graphs. 相似文献
13.
Connected dominating set (CDS) in unit disk graphs has a wide range of applications in wireless ad hoc networks. A number
of approximation algorithms for constructing a small CDS in unit disk graphs have been proposed in the literature. The majority
of these algorithms follow a general two-phased approach. The first phase constructs a dominating set, and the second phase
selects additional nodes to interconnect the nodes in the dominating set. In the performance analyses of these two-phased
algorithms, the relation between the independence number α and the connected domination number γ
c
of a unit-disk graph plays the key role. The best-known relation between them is
a £ 3\frac23gc+1\alpha\leq3\frac{2}{3}\gamma_{c}+1. In this paper, we prove that α≤3.4306γ
c
+4.8185. This relation leads to tighter upper bounds on the approximation ratios of two approximation algorithms proposed
in the literature. 相似文献
14.
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. 相似文献
15.
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. 相似文献
16.
We use the recently introduced advising scheme framework for measuring the difficulty of locally distributively computing a Minimum Spanning Tree (MST). An (m,t)-advising scheme for a distributed problem ? is a way, for every possible input I of ?, to provide an “advice” (i.e., a bit string) about I to each node so that: (1) the maximum size of the advices is at most m bits, and (2) the problem ? can be solved distributively in at most t rounds using the advices as inputs. In case of MST, the output returned by each node of a weighted graph G is the edge leading to its parent in some rooted MST T of G. Clearly, there is a trivial (?log?n?,0)-advising scheme for MST (each node is given the local port number of the edge leading to the root of some MST T), and it is known that any (0,t)-advising scheme satisfies $t\geq\tilde{\Omega}(\sqrt{n})
17.
A M-matrix which satisfies the Hecke algebraic relations is presented. Via the Yang–Baxterization approach, we obtain a unitary
solution
\breveR(q,j1,j2){\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 j1 = j2{\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. 相似文献
18.
Ryszard Janicki 《Acta Informatica》2008,45(4):279-320
The paper deals with the foundations of concurrency theory. We show how structurally complex concurrent behaviours can be
modelled by relational structures
(X, ¨, \sqsubset){(X, \diamondsuit, \sqsubset)} , where X is a set (of event occurrences), and ¨{\diamondsuit} (interpreted as commutativity) and
\sqsubset{\sqsubset} (interpreted as weak causality) are binary relations on X. The paper is a continuation of the approach initiated in Gaifman and Pratt (Proceedings of LICS’87, pp 72–85, 1987), Lamport
(J ACM 33:313–326, 1986), Abraham et al. (Semantics for concurrency, workshops in computing. Springer, Heidelberg, pp 311–323,
1990) and Janicki and Koutny (Lect Notes Comput Sci 506:59–74, 1991), substantially developed in Janicki and Koutny (Theoretical
Computer Science 112:5–52, 1993) and Janicki and Koutny (Acta Informatica 34:367–388, 1997), and recently generalized in Guo
and Janicki (Lect Notes Comput Sci 2422:178–191, 2002) and Janicki (Lect Notes Comput Sci 3407:84–98, 2005). For the first
time the full model for the most general case is given. 相似文献
19.
V. R. Fatalov 《Problems of Information Transmission》2010,46(1):62-85
Let w(t) be a standard Wiener process, w(0) = 0, and let η
a
(t) = w(t + a) − w(t), t ≥ 0, be increments of the Wiener process, a > 0. Let Z
a
(t), t ∈ [0, 2a], be a zeromean Gaussian stationary a.s. continuous process with a covariance function of the form E
Z
a
(t)Z
a
(s) = 1/2[a − |t − s|], t, s ∈ [0, 2a]. For 0 < p < ∞, we prove results on sharp asymptotics as ɛ → 0 of the probabilities
|
设为首页 | 免责声明 | 关于勤云 | 加入收藏 |
Copyright©北京勤云科技发展有限公司 京ICP备09084417号 |