共查询到20条相似文献,搜索用时 343 毫秒
1.
Given a “black box” function to evaluate an unknown rational polynomial
f ? \mathbb Q[ 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 ? \mathbb Q\alpha \in {\mathbb{Q}}, the exponents 0 £ e1 < e2 < ? < et{0 \leq e_{1} < e_{2} < \cdots < e_{t}}, and the coefficients
c1, ?, ct ? \mathbb Q \{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.
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 1, ?, f r\phi_{1}, \ldots , \phi_{r} : {− 1, 1} n →
\mathbb R{\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 1, ?, 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/ n)\Omega(2^{n}/n) , which almost meets the trivial upper bound of 2 n 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. 相似文献
3.
If k = O(log n) and a predicate P is approximation resistant for the reoptimization of the Max-EkCSP-P problem, then, after inserting a truth-value into the
predicate and imposing some constraint, there exists a polynomial algorithm with the approximation ratio
q( P) = \frac12 - d( P) q(P) = \frac{1}{{2 - d(P)}} , where d( P) = 2 - k| P - 1(1) | d(P) = {2^{ - k}}\left| {{P^{ - 1}}(1)} \right| is a “random” threshold approximation ratio of the predicate P. The ratio q( P) is a threshold approximation ratio. 相似文献
4.
We present new baby steps/giant steps algorithms of asymptotically fast running time for dense matrix problems. Our algorithms compute the determinant, characteristic polynomial, Frobenius normal form and Smith normal form of a dense n × n matrix A with integer entries in
and
bit operations; here
denotes the largest entry in absolute value and the exponent adjustment by +o(1) captures additional factors
for positive real constants C1, C2, C3. The bit complexity
results from using the classical cubic matrix multiplication algorithm. Our algorithms are randomized, and we can certify that the output is the determinant of A in a Las Vegas fashion. The second category of problems deals with the setting where the matrix A has elements from an abstract commutative ring, that is, when no divisions in the domain of entries are possible. We present algorithms that deterministically compute the determinant, characteristic polynomial and adjoint of A with n3.2+o(1) and O( n2.697263) ring additions, subtractions and multiplications.To B. David Saunders on the occasion of his 60th birthday 相似文献
5.
We show a construction of a PCP with both sub-constant error and almost-linear size. Specifically, for some constant 0 < α < 1, we construct a PCP verifier for checking satisfiability of Boolean formulas that on input of size n uses log n+ O((log n) 1-a)\log\, n+O((\log\, n)^{1-\alpha}) random bits to make 7 queries to a proof of size n·2 O((log n)1-a)n·2^{O((\log\, n)^{1-\alpha})}, where each query is answered by O((log n) 1-a)O((\log\, n)^{1-\alpha}) bit long string, and the verifier has perfect completeness and error 2 -W((log n)a)2^{-\Omega((\log\, n)^{\alpha})}. 相似文献
6.
For ultraspherical weight functions ω λ(x)=(1–x 2) λ–1/2, we prove asymptotic bounds and inequalities for the variance Var(Q n G ) of the respective Gaussian quadrature formulae Q n G . A consequence for a large class of more general weight functions ω and the respective Gaussian formulae is the following asymptotic result, $$\mathop {lim}\limits_{n \to \infty } n \cdot Var\left( {Q_n^G } \right) = \pi \int_{ - 1}^1 {\omega ^2 \left( x \right)\sqrt {1 - x^2 } dx.} $$ 相似文献
7.
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)
相似文献
8.
In this paper, we first define two generalized Wigner–Yanase skew information \(|K_{\rho ,\alpha }|(A)\) and \(|L_{\rho ,\alpha }|(A)\) for any non-Hermitian Hilbert–Schmidt operator A and a density operator \(\rho \) on a Hilbert space H and discuss some properties of them, respectively. We also introduce two related quantities \(|S_{\rho ,\alpha }|(A)\) and \(|T_{\rho ,\alpha }|(A)\). Then, we establish two uncertainty relations in terms of \(|W_{\rho ,\alpha }|(A)\) and \(|\widetilde{W}_{\rho ,\alpha }|(A)\), which read $$\begin{aligned}&|W_{\rho ,\alpha }|(A)|W_{\rho ,\alpha }|(B)\ge \frac{1}{4}\left| \mathrm {tr}\left( \left[ \frac{\rho ^{\alpha }+\rho ^{1-\alpha }}{2} \right] ^{2}[A,B]^{0}\right) \right| ^{2},\\&\sqrt{|\widetilde{W}_{\rho ,\alpha }|(A)| \widetilde{W}_{\rho ,\alpha }|(B)}\ge \frac{1}{4} \left| \mathrm {tr}\left( \rho ^{2\alpha }[A,B]^{0}\right) \mathrm {tr} \left( \rho ^{2(1-\alpha )}[A,B]^{0}\right) \right| . \end{aligned}$$ 相似文献
9.
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 3n(log R+loglog n + 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. 相似文献
10.
In this article, we propose the reproducing kernel Hilbert space method to obtain the exact and the numerical solutions of fuzzy Fredholm–Volterra integrodifferential equations. The solution methodology is based on generating the orthogonal basis from the obtained kernel functions in which the constraint initial condition is satisfied, while the orthonormal basis is constructing in order to formulate and utilize the solutions with series form in terms of their r-cut representation form in the Hilbert space \( W_{2}^{2} \left( \varOmega \right) \oplus W_{2}^{2} \left( \varOmega \right) \). Several computational experiments are given to show the good performance and potentiality of the proposed procedure. Finally, the utilized results show that the present method and simulated annealing provide a good scheduling methodology to solve such fuzzy equations. 相似文献
11.
Suppose we are given an unsorted database with N items and N is sufficiently large. By using a simpler approximate method, we re-derive the approximate formula cos 2
Φ, which represents the maximum success probability of Grover’s algorithm corresponding to the case of identical rotation angles
f = q{\phi=\theta} for any fixed deflection angle F ? [0,p/2){\Phi \in\left[0,\pi/2\right)}. We further show that for any fixed F ? [0,p/2){\Phi \in\left[0,\pi/2\right)}, the case of identical rotation angles f = q{\phi=\theta} is energetically favorable compared to the case |q- f| >> 0{\left|{\theta - \phi}\right|\gg 0} for enhancing the probability of measuring a unique desired state. 相似文献
12.
We present several results related to the complexity-performance tradeoff in lossy compression. The first result shows that for a memoryless source with rate-distortion function R( D) and a bounded distortion measure, the rate-distortion point ( R( D) + γ, D + ?) can be achieved with constant decompression time per (separable) symbol and compression time per symbol proportional to $\left( {{{\lambda _1 } \mathord{\left/ {\vphantom {{\lambda _1 } \varepsilon }} \right. \kern-0em} \varepsilon }} \right)^{{{\lambda _2 } \mathord{\left/ {\vphantom {{\lambda _2 } {\gamma ^2 }}} \right. \kern-0em} {\gamma ^2 }}}$ , where λ 1 and λ 2 are source dependent constants. The second result establishes that the same point can be achieved with constant decompression time and compression time per symbol proportional to $\left( {{{\rho _1 } \mathord{\left/ {\vphantom {{\rho _1 } \gamma }} \right. \kern-0em} \gamma }} \right)^{{{\rho _2 } \mathord{\left/ {\vphantom {{\rho _2 } {\varepsilon ^2 }}} \right. \kern-0em} {\varepsilon ^2 }}}$ . These results imply, for any function g( n) that increases without bound arbitrarily slowly, the existence of a sequence of lossy compression schemes of blocklength n with O( ng( n)) compression complexity and O( n) decompression complexity that achieve the point ( R( D) , D) asymptotically with increasing blocklength. We also establish that if the reproduction alphabet is finite, then for any given R there exists a universal lossy compression scheme with O( ng( n)) compression complexity and O( n) decompression complexity that achieves the point ( R, D( R)) asymptotically for any stationary ergodic source with distortion-rate function D(·). 相似文献
13.
Let { ξ
k
}
k=0∞ be a sequence of i.i.d. real-valued random variables, and let g( x) be a continuous positive function. Under rather general conditions, we prove results on sharp asymptotics of the probabilities
$
P\left\{ {\frac{1}
{n}\sum\limits_{k = 0}^{n - 1} {g\left( {\xi _k } \right) < d} } \right\}
$
P\left\{ {\frac{1}
{n}\sum\limits_{k = 0}^{n - 1} {g\left( {\xi _k } \right) < d} } \right\}
, n → ∞, and also of their conditional versions. The results are obtained using a new method developed in the paper, namely,
the Laplace method for sojourn times of discrete-time Markov chains. We consider two examples: standard Gaussian random variables
with g( x) = | x|
p
, p > 0, and exponential random variables with g( x) = x for x ≥ 0. 相似文献
14.
In this paper we study quadrature formulas of the types (1) $$\int\limits_{ - 1}^1 {(1 - x^2 )^{\lambda - 1/2} f(x)dx = C_n^{ (\lambda )} \sum\limits_{i = 1}^n f (x_{n,i} ) + R_n \left[ f \right]} ,$$ (2) $$\int\limits_{ - 1}^1 {(1 - x^2 )^{\lambda - 1/2} f(x)dx = A_n^{ (\lambda )} \left[ {f\left( { - 1} \right) + f\left( 1 \right)} \right] + K_n^{ (\lambda )} \sum\limits_{i = 1}^n f (\bar x_{n,i} ) + \bar R_n \left[ f \right]} ,$$ with 0<λ<1, and we obtain inequalities for the degree N of their polynomial exactness. By using such inequalities, the non-existence of (1), with λ=1/2, N= n+1 if n is even and N=n if n is odd, is directly proved for n=8 and n≥10. For the same value λ=1/2 and N= n+3 if n is even N= n+2 if n is odd, the formula (2) does not exist for n≥12. Some intermediary results regarding the first zero and the corresponding Christoffel number of ultraspherical polynomial P n (λ) ( x) are also obtained. 相似文献
15.
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:
1. |
We prove that depth-3 circuits with bottom fan-in (log n)/2 that compute approximate majority on n bits must have size at least 2n0.12^{n^{0.1}}. As a corollary we obtain that there is no black-box proof that BPTime (t) í ?2\subseteq \sum_2Time (o(t2)). This complements the (black-box) result that BPTime (t) í ?2\subseteq \sum_2Time (t2 · poly log t) (Sipser and Gács, STOC ’83; Lautemann, IPL ’83).
|
2. |
We prove that approximate majority is computable by uniform polynomial-size circuits of depth 3. Prior to our work, the only known polynomial-size depth-3 circuits for approximate majority
were non-uniform (Ajtai, Ann. Pure Appl. Logic ’83). We also prove that BPTime (t) í ?3\subseteq \sum_3Time (t · poly log t). This complements our results in (1).
|
3. |
We prove new lower bounds for solving QSAT3 ? ?3\in \sum_3Time (n · poly log n) on probabilistic computational models. In particular, we prove that solving QSAT3 requires time n1+Ω(1) on Turing machines with a random-access input tape and a sequential-access work tape that is initialized with random bits.
No nontrivial lower bound was previously known on this model (for a function computable in linear space).
|
相似文献
16.
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) b ut 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). 相似文献
17.
This paper examine the Euler-Lagrange equations for the solution of the large deformation diffeomorphic metric mapping problem studied in Dupuis et al. (1998) and Trouvé (1995) in which two images I
0, I
1 are given and connected via the diffeomorphic change of coordinates I
0○ϕ −1= I
1 where ϕ=Φ 1 is the end point at t= 1 of curve Φ
t
, t∈[0, 1] satisfying .Φ
t
= v
t (Φ
t
), t∈ [0,1] with Φ 0= id. The variational problem takes the form
where ‖ v
t‖
V
is an appropriate Sobolev norm on the velocity field v
t(·), and the second term enforces matching of the images with ‖·‖ L
2 representing the squared-error norm.In this paper we derive the Euler-Lagrange equations characterizing the minimizing vector fields v
t, t∈[0, 1] assuming sufficient smoothness of the norm to guarantee existence of solutions in the space of diffeomorphisms. We describe the implementation of the Euler equations using semi-lagrangian method of computing particle flows and show the solutions for various examples. As well, we compute the metric distance on several anatomical configurations as measured by ∫ 0
1‖ v
t‖
V
d t on the geodesic shortest paths. 相似文献
18.
We study some problems solvable in deterministic polynomial time given oracle access to the (promise version of) Arthur–Merlin
class. Our main results are the following:
° BPPNP|| í PprAM||.\circ\quad{\rm BPP}^{{\rm NP}}_{||} \subseteq {{\rm P}^{{{\rm pr}{\rm AM}}}_{||}}. 相似文献
19.
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:
(I) |
For each k≥2,
PSpk[2]tt í ZPPSpk[1]T PH=Spk\mathrm{P}^{\Sigma^{p}_{k}[2]}_{tt}\subseteq \mathrm{ZPP}^{\Sigma^{p}_{k}[1]}\Rightarrow \mathrm{PH}=\Sigma^{p}_{k}
, and
|
(II) |
P
tt
NP[2]⊆ZPPNP[1]
⇒PH=S2
p
.
|
Here, for any complexity class
C\mathcal{C}
and integer j≥1, we define
ZPP C[j]\mathrm{ZPP}^{\mathcal{C}[j]}
to be the class of problems solvable by zero-error randomized algorithms that run in polynomial time, make at most j queries to
C\mathcal{C}
, and succeed with probability at least 1/2+1/poly(⋅). This same definition of
ZPP C[j]\mathrm{ZPP}^{\mathcal{C}[j]}
, also considered in Cai and Chakaravarthy (J. Comb. Optim. 11(2):189–202, 2006), subsumes the class of problems solvable by randomized algorithms that always answer correctly in expected polynomial time
and make at most j queries to
C\mathcal{C}
.
Hemaspaandra, Hemaspaandra, and Hempel (SIAM J. Comput. 28(2):383–393, 1998), for k>2, and Buhrman and Fortnow (J. Comput. Syst. Sci. 59(2):182–194, 1999), for k=2, had obtained the same consequence as ours in (I) using the stronger hypothesis
P Spk[2]tt í P Spk[1]\mathrm{P}^{\Sigma^{p}_{k}[2]}_{tt}\subseteq \mathrm{P}^{\Sigma^{p}_{k}[1]}
. Fortnow, Pavan, and Sengupta (J. Comput. Syst. Sci. 74(3):358–363, 2008) had obtained the same consequence as ours in (II) using the stronger hypothesis P
tt
NP[2]⊆P NP[1]. 相似文献
20.
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(d n/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. 相似文献
|
|
| |