Optimal controls for stochastic systems with singular noise

Stochastic control systems of the form dx₁ = f(t, x, u_t)dt + g(t, x)db_t (0 t 1), with g singular and general cost, are discussed. It is shown that there is an optimal relaxed control u that depends on the past of x and the driving process b. Nonstandard methods are used.     

一种基于彩色编码技术的基序发现算法

从DNA序列中发现基序是生物计算中的一个重要问题,序列条数K=20包含基序用例的序列条数k=16的(l,d)-(K-k)问题(记作(l,d)-(20-16)问题)是目前生物学家十分关注的基序发现问题.针对该问题提出了一种基于彩色编码技术的SDA(sample-driven algorithm)搜索算法--彩色编码基序搜索算法(color coding motif finding algorithm,简称CCMF算法).它利用彩色编码技术将该问题转化为(l,d)-(16-16)问题,再采用分治算法和分支定界法来求解.在解决将(l,d)-(20-16)问题转化为(l,d)-(16-16)问题时,CCMF算法利用彩色编码技术将4 845个组合降低到403个着色,这将极大地提高算法的整体运行效率.使用模拟数据和生物数据进行测试的结果表明,CCMF算法能够快速发现所有(l,d)-(20-16)问题的基序模型和基序用例,具有优于其他算法的综合性能评价,能够用于真实的基序发现问题.同时,通过修改着色方案,CCMF算法可以用于求解一般的(l,d)-(K-k)问题,其中,k＜K.     

A sufficient condition for pancyclic graphs

In 2005, Rahman and Kaykobad proved that if G is a connected graph of order n such that d(x)+d(y)+d(x,y)n+1 for each pair x, y of distinct nonadjacent vertices in G, where d(x,y) is the length of a shortest path between x and y in G, then G has a Hamiltonian path [Inform. Process. Lett. 94 (2005) 37–41]. In 2006 Li proved that if G is a 2-connected graph of order n3 such that d(x)+d(y)+d(x,y)n+2 for each pair x,y of nonadjacent vertices in G, then G is pancyclic or G=K_n/2,n/2 where n4 is an even integer [Inform. Process. Lett. 98 (2006) 159–161]. In this work we prove that if G is a 2-connected graph of order n such that d(x)+d(y)+d(x,y)n+1 for all pairs x, y of distinct nonadjacent vertices in G, then G is pancyclic or G belongs to one of four specified families of graphs.     

A generalization of Nemhauser and Trotter?s local optimization theorem

The Nemhauser–Trotter local optimization theorem applies to the NP-hard Vertex Cover problem and has applications in approximation as well as parameterized algorithmics. We generalize Nemhauser and Trotter?s result to vertex deletion problems, introducing a novel algorithmic strategy based on purely combinatorial arguments (not referring to linear programming as the Nemhauser–Trotter result originally did). The essence of our strategy can be understood as a doubly iterative process of cutting away “easy parts” of the input instance, finally leaving a “hard core” whose size is (almost) linearly related to the cardinality of the solution set. We exhibit our approach using a generalization of Vertex Cover, called Bounded-Degree Vertex Deletion. For some fixed d?0, Bounded-Degree Vertex Deletion asks to delete at most k vertices from a graph in order to transform it into a graph with maximum vertex degree at most d. Vertex Cover is the special case of d=0. Our generalization of the Nemhauser–Trotter-Theorem implies that Bounded-Degree Vertex Deletion, parameterized by k, admits an O(k)-vertex problem kernel for d?1 and, for any ?>0, an O(k1+?)-vertex problem kernel for d?2. Finally, we provide a W[2]-completeness result for Bounded-Degree Vertex Deletion in case of unbounded d-values.     

Efficiency of semisynchronous versus asynchronous networks

Thes-session problem is studied inasynchronous andsemisynchronous networks. Processes are located at the nodes of an undirected graphG and communicate by sending messages along links that correspond to the edges ofG. A session is a part of an execution in which each process takes at least one step; an algorithm for thes-session problem guarantees the existence of at leasts disjoint sessions. The existence of many sessions guarantees a degree of interleaving which is necessary for certain computations. It is assumed that the (real) time for message delivery is at mostd. In the asynchronous model it is assumed that the time between any two consecutive steps of any process is in the interval [0, 1]; in the semisynchronous model the time between any two consecutive steps of any process is in the interval [c, 1] for somec such that 0 <c 1,the synchronous model being the special case wherec = 1. All processes are initially synchronized and take a step at time 0.For the asynchronous model, an upper bound ofdiam(G)(d + l)(s – 1) and a lower bound ofdiam(G)d(s – 1) are presented;diam(G) is thediameter ofG. For the semisynchronous model, an upper bound of 1 + min{1/c + 1,diam(G)(d + 1)}(s – 2) is presented. The main result of the paper is a lower bound of 1 + min{1/2c,diam(G)d}(s – 2) for the time complexity of any semisynchronous algorithm for thes-session problem, under the assumption thatd (d/min{1/2c, diam(G)d}) + 2. These results imply a time separation between semisynchronous (in particular, synchronous) and asynchronous networks. Similar results are proved for the case where delays are not uniform.A preliminary version of this paper appeared in theProceedings of the 28th Annual Allerton Conference on Communication, Control, and Computing, October 1990, pp. 578–587. H. Attiya was partially supported by B. and G. Greenberg Research Fund (Ottawa) and by Techion V.P.R. funds. Part of this work was performed when she was at the Laboratory for Computer Science, MIT, supported by ONR Contract N00014-85-K-0168, by NSF Grant CCR-8915206, and by DARPA Contract N00014-87-K-0825. M. Mavronicolas was supported by ONR Contract N00014-91-J-1981. His current address is: Department of Computer Science, University of Cyprus, Cyprus, and Institute of Computer Science, Foundation of Research and Technology, Hellas, Greece.     

Lower estimation of approximation rate for neural networks

Let SFd and Πψ,n,d = { nj=1bjψ(ωj·x+θj) :bj,θj∈R,ωj∈Rd} be the set of periodic and Lebesgue’s square-integrable functions and the set of feedforward neural network (FNN) functions, respectively. Denote by dist (SF d, Πψ,n,d) the deviation of the set SF d from the set Πψ,n,d. A main purpose of this paper is to estimate the deviation. In particular, based on the Fourier transforms and the theory of approximation, a lower estimation for dist (SFd, Πψ,n,d) is proved. That is, dist(SF d, Πψ,n,d) (nlogC2n)1/2 . T...     

Accurate determination of pretilt angle in twisted‐nematic liquid‐crystal cells by using a rotating analyzer

Abstract— A new optical method for determining the pretilt angle ψ⁰, particularly on twisted‐nematic (TN) liquid‐crystal (LC) cells, is proposed. ψ⁰ was rapidly determined with good reproducibility on a TN‐LC cell by using a rotating analyzer optical system, a twist angle Φ, the azimuth of the director at a substrate, ϕ⁰, and the retardation Δnd as known values. The thickness d was also determined simultaneously with ψ⁰. ψ⁰ and d were determined within minutes. ψ⁰ was previously determined to be in the range of 0.1° with a standard deviation of 0.01°; this was obtained by repeating the measurement 50 times. The principle behind the determination and the experimental set up are described in detail.     

The Nonexistence of Ternary [284, 6, 188] Codes

Let [n, k, d] _q codes be linear codes of length n, dimension k, and minimum Hamming distance d over GF(q). Let n _q (k, d) be the smallest value of n for which there exists an [n, k, d] _q code. It is known from [1, 2] that 284 n ₃(6, 188) 285 and 285 n ₃(6, 189) 286. In this paper, the nonexistence of [284, 6, 188]₃ codes is proved, whence we get n ₃(6, 188) = 285 and n ₃(6, 189) = 286.     

On one application of computations with oracle

Let P(d) be a program implementing a partial recursive function φ. Let $ \mathcal{O} $ \mathcal{O} _P denote a function defined on the domain of function φ that maps an input data d ₀ onto the path of computation of P on the input d ₀. Let Q(p, d) be a program returning a value if and only if p = $ \mathcal{O} $ \mathcal{O} _P (d), and let the value of the program be Q($ \mathcal{O} $ \mathcal{O} _P (d), d) = P(d). Program Q(p, d), which is totally absurd from the point of view of its practical computation on concrete input data, may be practically useful when it is analyzed by a metaprogram. It is shown in the paper how program Q(p, d) can be used for verification of a postcondition imposed on program P(d). The proposed method was tested on verification tasks for cache coherence protocols and other distributed computing systems.     

Relaxing the Triangle Inequality in Pattern Matching

Any notion of closeness in pattern matching should have the property that if A is close to B, and B is close to C, then A is close to C. Traditionally, this property is attained because of the triangle inequality (d(A, C) d(A, B) + d(B, C), where d represents a notion of distance). However, the full power of the triangle inequality is not needed for this property to hold. Instead, a relaxed triangle inequality suffices, of the form d(A, C) c(d(A, B) + d(B, C)), where c is a constant that is not too large. In this paper, we show that one of the measures used for distances between shapes in (an experimental version of) IBM's QBIC¹ ("Query by Image Content") system (Niblack et al., 1993) satisfies a relaxed triangle inequality, although it does not satisfy the triangle inequality.     

On the joint nonlinear filtering-smoothing of diffusion processes

The smoothing of diffusions dx_t = f(x_t) dt + σ(x_t) dw_t, measured by a noisy sensor dy_t = h(x_t) dt + dv_t, where w_t and v_t are independent Wiener processes, is considered in this paper. By focussing our attention on the joint p.d.f. of (x_τ x_t), 0 ≤ τ < t, conditioned on the observation path {y_s, 0 ≤ s ≤ t}, the smoothing problem is represented as a solution of an appropriate joint filtering problem of the process, together with its random initial conditions. The filtering problem thus obtained possesses a solution represented by a Zakai-type forward equation. This solution of the smoothing problem differs from the common approach where, by concentrating on the conditional p.d.f. of x_τ alone, a set of ‘forward and reverse’ equations needs to be solved.     

取定s的严格d-正则随机(3,2s)-SAT问题的可满足临界

3-CNF公式的随机难解实例生成对于揭示3-SAT问题的难解实质和设计满足性测试的有效算法有着重要意义.对于整数k>2和s>0,如果在一个k-CNF公式中每个变量正负出现次数均为s,则称该公式是严格正则（k,2s）-CNF公式.受严格正则（k,2s）-CNF公式的结构特征启发,提出每个变量正负出现次数之差的绝对值均为d的严格d-正则（k,2s）-CNF公式,并使用新提出的SDRRK2S模型生成严格d-正则随机（k,2s）-CNF公式.取定整数5<s<11,模拟实验显示,严格d-正则随机（3,2s）-SAT问题存在SAT-UNSAT相变现象和HARD-EASY相变现象.因此,立足于3-CNF公式的随机难解实例生成,研究了严格d-正则随机（3,2s）-SAT问题在s取定时的可满足临界.通过构造一个特殊随机实验和使用一阶矩方法,得到了严格d-正则随机（3,2s）-SAT问题在s取定时可满足临界值的一个下界.模拟实验结果验证了理论证明所得下界的正确性.     

On the security of Goldreich’s one-way function

Goldreich (ECCC 2000) suggested a simple construction of a candidate one-way function f : {0, 1} ⁿ → {0, 1} ^m where each bit of output is a fixed predicate P of a constant number d of (random) input bits. We investigate the security of this construction in the regime m = Dn, where D(d) is a sufficiently large constant. We prove that for any predicate P that correlates with either one or two of its inputs, f can be inverted with high probability.     

Implementing Shared Memory on Mesh-Connected Computers and on the Fat-Tree

We present deterministic upper and lower bounds on the slowdown required to simulate an (n, m)-PRAM on a variety of networks. The upper bounds are based on a novel scheme that exploits the splitting and combining of messages. This scheme can be implemented on an n-node d-dimensional mesh (for constant d) and on an n-leaf pruned butterfly and attains the smallest worst-case slowdown to date for such interconnections, namely, O(n^1/d(log(m/n))^1-1/d) for the d-dimensional mesh (with constant d) and O( ) for the pruned butterfly. In fact, the simulation on the pruned butterfly is the first PRAM simulation scheme on an area-universal network. Finally, we prove restricted and unrestricted lower bounds on the slowdown of any deterministic PRAM simulation on an arbitrary network, formulated in terms of the bandwidth properties of the interconnection as expressed by its decomposition tree.     

Embedding a fault-free hamiltonian cycle in a class of faulty generalized honeycomb tori

Generalized honeycomb torus (GHT) is recognized as an attractive alternative to existing torus interconnection networks in parallel computing systems. Assume that m and d are integers with m ? 2 and d ? 8. This paper addresses the fault-tolerant hamiltonicity of GHT(m, 2d, d) with fault set F = {(w, y), (x, y)}, where w < x, w + y is even and x + y is odd. We show that such a faulty GHT is hamiltonian by presenting a systematic method for constructing a fault-free hamiltonian cycle. This result reveals another appealing feature of GHTs.     

On the efficiency of effective Nullstellensätze

Letk be an infinite and perfect field,x ₁, ...,x _n indeterminates overk and letf ₁, ...,f _s be polynomials ink[x ₁, ...,x _n ] of degree bounded by a given numberd, which satisfiesdn. We prove an effective affine Nullstellensatz of the following particular form:For arbitrary given parametersd, s, n there exists a probabilistic (randomized) arithmetic network overk of sizes ^O(1) d ^O(n) and depthO(n ⁴log² sd) solving the following task:     

Spreading of Messages in Random Graphs

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.