共查询到20条相似文献,搜索用时 31 毫秒
1.
S. Jukna 《Information Processing Letters》2009,109(5):286-289
We are interested in proving exponential lower bounds on the size of nondeterministic D-way branching programs computing functions in linear time, that is, in time at most kn for a constant k. Ajtai has proved such lower bounds for explicit functions over domains D of size about n, and Beame, Saks and Thathachar for functions over domains of size about k22. We prove an exponential lower bound 2Ω(n/ck) for an explicit function over substantially smaller domain D of size about k2. Our function is a universal function of linear codes. 相似文献
2.
Yuri Lifshits 《Information Processing Letters》2003,85(6):293-299
Hromkovic? et al. showed how to transform a regular expression of size n into an ε-free nondeterministic finite automaton (which defines the same language as the expression) with O(n) states and O(nlog2(n)) transitions. They also established a lower bound on the number of transitions. We improve the lower bound to . 相似文献
3.
4.
5.
The recursive circulant RC(n2,4) enjoys several attractive topological properties. Let max_?G(m) denote the maximum number of edges in a subgraph of graph G induced by m nodes. In this paper, we show that , where p0>p1>?>pr are nonnegative integers defined by . We then apply this formula to find the bisection width of RC(n2,4). The conclusion shows that, as n-dimensional cube, RC(n2,4) enjoys a linear bisection width. 相似文献
6.
Chris Giannella 《Information Processing Letters》2009,109(19):1109-1113
Consider a dataset of n(d) points generated independently from Rd according to a common p.d.f. fd with support(fd)=d[0,1] and sup{fd(Rd)} growing sub-exponentially in d. We prove that: (i) if n(d) grows sub-exponentially in d, then, for any query point and any ?>0, the ratio of the distance between any two dataset points and is less that 1+? with probability →1 as d→∞; (ii) if n(d)>d[4(1+?)] for large d, then for all (except a small subset) and any ?>0, the distance ratio is less than 1+? with limiting probability strictly bounded away from one. Moreover, we provide preliminary results along the lines of (i) when . 相似文献
7.
8.
Sang-Eon Han 《Information Sciences》2007,177(18):3731-3748
In this paper, we deal with the problem of computing the digital fundamental group of a closed k-surface by using various properties of both a (simple) closed k-surface and a digital covering map. To be specific, let be a simple closed ki-curve with li elements in Zni, i∈{1,2}. Then, the Cartesian product is not always a closed k-surface with some k-adjacency of Zn1+n2. Thus, we provide a condition for to be a (simple) closed k-surface with some k-adjacency depending on the ki-adjacency, i∈{1,2}. Besides, even if is not a closed k-surface, we show that the k-fundamental group of can be calculated by both a k-homotopic thinning and a strong k-deformation retract. 相似文献
9.
10.
Given a conjunctive normal form F with n variables and m=cn 2-clauses, it is interesting to study the maximum number of clauses satisfied by all the assignments of the variables (MAX 2-SAT). When c is sufficiently large, the upper bound of of random MAX 2-SAT had been derived by the first-moment argument. In this paper, we provide a tighter upper bound (3/4)cn+g(c)cn also using the first-moment argument but correcting the error items for f(n,cn), and when considering the ε3 error item. Furthermore, we extrapolate the region of the validity of the first-moment method is c>2.4094 by analyzing the higher order error items. 相似文献
11.
12.
13.
14.
15.
We show that i-directable nondeterministic automata can be i-directed with a word of length O(2n) for i=1,2, where n stands for the number of states. Since for i=1,2 there exist i-directable automata having i-directing words of length Ω(2n), these upper bounds are asymptotically optimal. We also show that a 3-directable nondeterministic automaton with n states can be 3-directed with a word of length , improving the previously known upper bound O(2n). Here the best known lower bound is . 相似文献
16.
17.
Testing juntas 总被引:1,自引:0,他引:1
Eldar Fischer Guy Kindler Shmuel Safra Alex Samorodnitsky 《Journal of Computer and System Sciences》2004,68(4):753-787
We show that a boolean valued function over n variables, where each variable ranges in an arbitrary probability space, can be tested for the property of depending on only J of them using a number of queries that depends only polynomially on J and the approximation parameter ε. We present several tests that require a number of queries that is polynomial in J and linear in ε−1. We show a non-adaptive test that has one-sided error, an adaptive version of it that requires fewer queries, and a non-adaptive two-sided version of the test that requires the least number of queries. We also show a two-sided non-adaptive test that applies to functions over n boolean variables, and has a more compact analysis.We then provide a lower bound of on the number of queries required for the non-adaptive testing of the above property; a lower bound of for adaptive algorithms naturally follows from this. In establishing this lower bound we also prove a result about random walks on the group Zq2 that may be interesting in its own right. We show that for some , the distributions of the random walk at times t and t+2 are close to each other, independently of the step distribution of the walk.We also discuss related questions. In particular, when given in advance a known J-junta function , we show how to test a function for the property of being identical to up to a permutation of the variables, in a number of queries that is polynomial in J and ε−1. 相似文献
18.
Yun Bao Huang 《Theoretical computer science》2011,412(45):6327-6339
19.
20.
Livio Colussi 《Theoretical computer science》2011,412(39):5409-5419