共查询到20条相似文献,搜索用时 15 毫秒
1.
Daniel M. Kane 《Computational Complexity》2014,23(2):151-175
We prove new bounds on the average sensitivity of polynomial threshold functions. In particular, we show that for f, a degree-d polynomial threshold function in n variables that $$\mathbb{AS}(f) \leq \sqrt{n}(\log(n))^{O(d log(d))}2^{O(d^2 log(d))}.$$ This bound amounts to a significant improvement over previous bounds, and in particular, for fixed d gives the same asymptotic exponent of n as the one predicted by the Gotsman–Linial Conjecture. 相似文献
2.
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. 相似文献
3.
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. 相似文献
4.
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)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(?\fracfk?+2,?\fractk?+1)\min(\lfloor \frac{f}{k}\rfloor+2,\lfloor \frac{t}{k}\rfloor +1)
is a lower bound on the number of rounds for the non-faulty processes to decide (where t is an upper bound on the number of process crashes, and f, 0≤f≤t, the actual number of crashes). 相似文献
5.
Quantum search in a possible three-dimensional complex subspace 总被引:1,自引:0,他引:1
Wenliang Jin 《Quantum Information Processing》2012,11(1):41-54
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 cos2
Φ, 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. 相似文献
6.
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. 相似文献
7.
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}} 相似文献
8.
This paper is concerned with the design and analysis of a random walk algorithm for the 2CNF implication problem (2CNFI).
In 2CNFI, we are given two 2CNF formulas f1{\phi_{1}} and f2{\phi_{2}} and the goal is to determine whether every assignment that satisfies f1{\phi_{1}} , also satisfies f2{\phi_{2}} . The implication problem is clearly coNP-complete for instances of kCNF, k ≥ 3; however, it can be solved in polynomial time, when k ≤ 2. The goal of this paper is to provide a Monte Carlo algorithm for 2CNFI with a bounded probability of error. The technique
developed for 2CNFI is then extended to derive a randomized, polynomial time algorithm for the problem of checking whether
a given 2CNF formula Nae-implies another 2CNF formula. 相似文献
9.
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. 相似文献
10.
Roel Verstappen 《Journal of scientific computing》2011,49(1):94-110
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(S2)q = \frac{1}{2}\mathrm{tr}(S^{2}) and
r = -\frac13tr(S3)r= -\frac{1}{3}\mathrm{tr}(S^{3}) of the (filtered) strain rate tensor S. The simplest model is then given by
ne = \frac32(D/p)2 |r|/q\nu_{e} = \frac{3}{2}(\Delta/\pi)^{2} |r|/q. This model is successfully tested for a turbulent channel flow (Re
τ
=590). 相似文献
11.
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. 相似文献
12.
For ultraspherical weight functions ωλ(x)=(1–x2)λ–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.} $$ 相似文献
13.
We study the string-property of being periodic and having periodicity smaller than a given bound. Let Σ be a fixed alphabet
and let p,n be integers such that
p £ \fracn2p\leq \frac{n}{2}
. A length-n string over Σ, α=(α
1,…,α
n
), has the property Period(p) if for every i,j∈{1,…,n}, α
i
=α
j
whenever i≡j (mod p). For an integer parameter
g £ \fracn2,g\leq \frac{n}{2},
the property Period(≤g) is the property of all strings that are in Period(p) for some p≤g. The property
Period( £ \fracn2)\mathit{Period}(\leq \frac{n}{2})
is also called Periodicity. 相似文献
14.
Every Linear Threshold Function has a Low-Weight Approximator 总被引:1,自引:1,他引:0
Rocco A. Servedio 《Computational Complexity》2007,16(2):180-209
15.
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. 相似文献
16.
P. Yu. Chebotarev V. A. Malyshev Ya. Yu. Tsodikova A. K. Loginov Z. M. Lezina V. A. Afonkin 《Automation and Remote Control》2018,79(4):725-736
Within the model of social dynamics determined by collective decisions in a stochastic environment (ViSE model), we consider the case of a homogeneous society consisting of classically rational economic agents (or homines economici, or egoists). We present expressions for the optimal majority threshold and the maximum expected capital increment as functions of the parameters of the environment. An estimate of the rate of change of the optimal threshold at zero is given, which is an absolute constant: \(\left( {\sqrt {2/\pi } - \sqrt {\pi /2} } \right)/2\). 相似文献
17.
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. 相似文献
18.
In this article we give several new results on the complexity of algorithms that learn Boolean functions from quantum queries
and quantum examples.
19.
In this paper, we demonstrate that there exist weak keys in the RSA public-key cryptosystem with the public exponent e = Nα ≤ N0.5. In 1999, Boneh and Durfee showed that when α ≈ 1 and the private exponent d = Nβ < N0.292, the system is insecure. Moreover, their attack is still effective for 0.5 < α < 1.875. We propose a generalized cryptanalytic method to attack the RSA cryptosystem with α ≤ 0.5. For \(c = \left\lfloor {\frac{{1 - \alpha }}{\alpha }} \right\rfloor \) and eγc ≡ d (mod ec), when γ, β satisfy \(\gamma < 1 + \frac{1}{c} - \frac{1}{{2\alpha c}}and\beta < \alpha c + \frac{7}{6} - \alpha \gamma c - \frac{1}{3}\sqrt {6\alpha + 6\alpha c + 1 - 6\alpha \gamma c} \), we can perform cryptanalytic attacks based on the LLL algorithm. The basic idea is an application of Coppersmith’s techniques and we further adapt the technique of unravelled linearization, which leads to an optimized lattice. Our advantage is that we achieve new attacks on RSA with α ≤ 0.5 and consequently, there exist weak keys in RSA for most α. 相似文献
|