On Local Structural Stability of Differential 1-Forms and Nonlinear Hypersurface Systems on a Manifold with Boundary

In this paper we consider smooth differential 1-forms and smooth nonlinear control-affine systems with (n−1)-inputs evolving on an n-dimensional manifold with boundary. These systems are called hypersurface systems under the additional assumption that the drift vector field and control vector fields span the tangent space to the manifold. We locally classify all structurally stable differential 1-forms on a manifold with boundary. We give complete local classification of structurally stable hypersurface systems on a manifold with boundary under static state feedback defined by diffeomorphisms, which preserve the manifold together with its boundary. Date received: March 30, 2000. Date revised: October 30, 2000.     

Optimal fault-tolerant Hamiltonicity of star graphs with conditional edge faults

The star graph is viewed as an attractive alternative to the hypercube. In this paper, we investigate the Hamiltonicity of an n-dimensional star graph. We show that for any n-dimensional star graph (n≥4) with at most 3n−10 faulty edges in which each node is incident with at least two fault-free edges, there exists a fault-free Hamiltonian cycle. Our result improves on the previously best known result for the case where the number of tolerable faulty edges is bounded by 2n−7. We also demonstrate that our result is optimal with respect to the worst case scenario, where every other node of a cycle of length 6 is incident with exactly n−3 faulty noncycle edges.     

The only stable normal forms of affine systems under feedback are linear

We consider the problem of existence of structurally stable normal forms of affine control systems with m inputs and n-dimensional state space, equipped with C^∞-Whitney topology and acted on by the static state feedback group. It is proved that structurally stable normal forms exist only if m = n or m =1 and n = 2, and are linear. There are no stable normal forms in any other range of dimensions (m, n).     

Quantum Separation of Local Search and Fixed Point Computation

We give a lower bound of Ω(n ^(d−1)/2) on the quantum query complexity for finding a fixed point of a discrete Brouwer function over grid [n] ^d . Our lower bound is nearly tight, as Grover Search can be used to find a fixed point with O(n ^d/2) quantum queries. Our result establishes a nearly tight bound for the computation of d-dimensional approximate Brouwer fixed points defined by Scarf and by Hirsch, Papadimitriou, and Vavasis. It can be extended to the quantum model for Sperner’s Lemma in any dimensions: The quantum query complexity of finding a panchromatic cell in a Sperner coloring of a triangulation of a d-dimensional simplex with n ^d cells is Ω(n ^(d−1)/2). For d=2, this result improves the bound of Ω(n ^1/4) of Friedl, Ivanyos, Santha, and Verhoeven. More significantly, our result provides a quantum separation of local search and fixed point computation over [n] ^d , for d≥4. Aaronson’s local search algorithm for grid [n] ^d , using Aldous Sampling and Grover Search, makes O(n ^d/3) quantum queries. Thus, the quantum query model over [n] ^d for d≥4 strictly separates these two fundamental search problems.     

Arbitrary Pole Placement by Constant Output Feedback for Linear Time Invariant Systems

In this paper, the pole placement problem by constant output feedback for linear time invariant systems is investigated. In particular, is proven that, for the class of linear time invariant systems with m inputs, p outputs, and McMillan degree n, the condition (m + p) > n is necessary for the solution of the arbitrary pole placement problem by constant output feedback.     

Embedding fault-free cycles in crossed cubes with conditional link faults

The crossed cube, which is a variation of the hypercube, possesses some properties that are superior to those of the hypercube. In this paper, we show that with the assumption of each node incident with at least two fault-free links, an n-dimensional crossed cube with up to 2n−5 link faults can embed, with dilation one, fault-free cycles of lengths ranging from 4 to 2 ⁿ . The assumption is meaningful, for its occurrence probability is very close to 1, and the result is optimal with respect to the number of link faults tolerated. Consequently, it is very probable that algorithms executable on rings of lengths ranging from 4 to 2 ⁿ can be applied to an n-dimensional crossed cube with up to 2n−5 link faults.

Fault-Tolerant Embedding of Pairwise Independent Hamiltonian Paths on a Faulty Hypercube with Edge Faults

A Hamiltonian path in G is a path which contains every vertex of G exactly once. Two Hamiltonian paths P ₁=〈u ₁,u ₂,…,u _n 〉 and P ₂=〈v ₁,v ₂,…,v _n 〉 of G are said to be independent if u ₁=v ₁, u _n =v _n , and u _i ≠v _i for all 1<i<n; and both are full-independent if u _i ≠v _i for all 1≤i≤n. Moreover, P ₁ and P ₂ are independent starting at u ₁, if u ₁=v ₁ and u _i ≠v _i for all 1<i≤n. A set of Hamiltonian paths {P ₁,P ₂,…,P _k } of G are pairwise independent (respectively, pairwise full-independent, pairwise independent starting at u ₁) if any two different Hamiltonian paths in the set are independent (respectively, full-independent, independent starting at u ₁). A bipartite graph G is Hamiltonian-laceable if there exists a Hamiltonian path between any two vertices from different partite sets. It is well known that an n-dimensional hypercube Q _n is bipartite with two partite sets of equal size. Let F be the set of faulty edges of Q _n . In this paper, we show the following results:

Orthogonal queries in segments

We consider theorthgonal clipping problem in a set of segments: Given a set ofn segments ind-dimensional space, we preprocess them into a data structure such that given an orthogonal query window, the segments intersecting it can be counted/reported efficiently. We show that the efficiency of the data structure significantly depends on a geometric discrete parameterK named theProjected-image complexity, which becomes Θ(n ²) in the worst case but practically much smaller. If we useO(m) space, whereK log^4d−7 n≥m≥n log^4d−7 n, the query time isO((K/m)^1/2 log^{max{4, 4d−5}} n). This is near to an Ω((K/m)^1/2) lower bound.     

Effect of dispersed phase viscosity on maximum droplet generation frequency in microchannel emulsification using asymmetric straight-through channels

Uniformly sized droplets of soybean oil, MCT (medium-chain fatty acid triglyceride) oil and n-tetradecane with a Sauter mean diameter of d _3,2 = 26–35 μm and a distribution span of 0.21–0.25 have been produced at high throughputs using a 24 × 24 mm silicon microchannel plate consisting of 23,348 asymmetric channels fabricated by photolithography and deep reactive ion etching. Each channel consisted of a 10-μm diameter straight-through micro-hole with a length of 70 μm and a 50 × 10 μm micro-slot with a depth of 30 μm at the outlet of each channel. The maximum dispersed phase flux for monodisperse emulsion generation increased with decreasing dispersed phase viscosity and ranged from over 120 L m⁻² h⁻¹ for soybean oil to 2,700 L m⁻² h⁻¹ for n-tetradecane. The droplet generation frequency showed significant channel to channel variations and increased with decreasing viscosity of the dispersed phase. For n-tetradecane, the maximum mean droplet generation frequency was 250 Hz per single active channel, corresponding to the overall throughput in the device of 3.2 million droplets per second. The proportion of active channels at high throughputs approached 100% for soybean oil and MCT oil, and 50% for n-tetradecane. The agreement between the experimental and CFD (Computational Fluid Dynamics) results was excellent for soybean oil and the poorest for n-tetradecane.     

Asymmetric quantum Reed-Solomon and generalized Reed-Solomon codes

Two new families of asymmetric quantum codes are constructed in this paper. The first one is derived from the Calderbank-Shor-Steane (CSS) construction applied to classical Reed-Solomon (RS) codes, providing quantum codes with parameters [[N = l(q ^l −1), K = l(q ^l −2d + c + 1), d _z ≥ d/d _x ≥ (d−c)]] _q , where q is a prime power and d > c + 1, c ≥ 1, l ≥ 1 are integers. The second family is derived from the CSS construction applied to classical generalized RS codes, generating quantum codes with parameters [[N = mn, K = m(2k−n + c), d _z ≥ d/d _x ≥ (d−c)]] _q , where q is a prime power, 1 < k < n < 2k + c ≤ q ^m , k = n − d + 1, and n, d > c + 1, c ≥ 1, m ≥ 1 are integers. Although the second proposed construction generalizes the first one, the techniques developed in both constructions are slightly different. These new codes have parameters better than or comparable to the ones available in the literature. Additionally, the proposed codes can be utilized in quantum channels having great asymmetry, that is, quantum channels in which the probability of occurrence of phase-shift errors is large when compared to the probability of occurrence of qudit-flip errors.     

Wavelength Assignment for Realizing Parallel FFT on Regular Optical Networks

Routing and wavelength assignment (RWA) is a central issue to increase efficiency and reduce cost in Wavelength Division Multiplexing (WDM) optical networks. In this paper, we address the problem of wavelength assignment for realizing parallel FFT on a class of regular optical WDM networks. We propose two methods for sequential mapping and shift-reversal mapping of FFT communication pattern to the optical WDM networks concerned. By sequential mapping, the numbers of wavelengths required to realize parallel FFT with 2ⁿ nodes on WDM linear arrays, rings, 2-D meshes and 2-D tori are 2^{n − 1}, 2^{n − 1}, 2^{max (k,n − k) − 1} and 2^{max (k,n − k) − 1} respectively. By shift-reversal mapping, the numbers of wavelengths required are max (3× 2^{n − 3},2), 2^{n − 2}, max (3× 2^{max (k,n − k) − 3},2) and 2^{max (k,n − k) − 2}. These results show that shift-reversal mapping outperforms sequential mapping. Our results have a clear significance for applications because FFT represents a common computation pattern shared by a large class of scientific and engineering problems and WDM optical networks as a promising technology in networking has an increasing popularity.     

Nonsmooth Robust Stabilization of a Class of Two-Dimensional Nonlinear Systems

In this paper we consider a class of parameterized families of nonlinear systems which cannot be robustly asymptotically stabilized by means of C ¹ feedback. We construct C ⁰ state feedback laws which are smooth away from the origin and which robustly asymptotically stabilize these families of systems. We then show that, in some cases, the regularity of the obtained robust asymptotic stabilizers is “maximum” in the sense that the considered families of systems do not admit any Lipschitz continuous robust asymptotic stabilizer. Date received: June 27, 1997. Date revised: July 28, 1998.     

Embedding of Cycles in Twisted Cubes with Edge-Pancyclic

In this paper, we study the embedding of cycles in twisted cubes. It has been proven in the literature that, for any integer l, 4≤l≤2 ⁿ , a cycle of length l can be embedded with dilation 1 in an n-dimensional twisted cube, n≥3. We obtain a stronger result of embedding of cycles with edge-pancyclic. We prove that, for any integer l, 4≤l≤2 ⁿ , and a given edge (x,y) in an n-dimensional twisted cube, n≥3, a cycle C of length l can be embedded with dilation 1 in the n-dimensional twisted cube such that (x,y) is in C in the twisted cube. Based on the proof of the edge-pancyclicity of twisted cubes, we further provide an O(llog l+n ²+nl) algorithm to find a cycle C of length l that contains (u,v) in TQ _n for any (u,v)∈E(TQ _n ) and any integer l with 4≤l≤2 ⁿ .     

Sublinear Fully Distributed Partition with Applications

We present new efficient deterministic and randomized distributed algorithms for decomposing a graph with n nodes into a disjoint set of connected clusters with radius at most k−1 and having O(n ^1+1/k ) intercluster edges. We show how to implement our algorithms in the distributed CONGEST\mathcal{CONGEST} model of computation, i.e., limited message size, which improves the time complexity of previous algorithms (Moran and Snir in Theor. Comput. Sci. 243(1–2):217–241, 2000; Awerbuch in J. ACM 32:804–823, 1985; Peleg in Distributed Computing: A Locality-Sensitive Approach, 2000) from O(n) to O(n ^1−1/k ). We apply our algorithms for constructing low stretch graph spanners and network synchronizers in sublinear deterministic time in the CONGEST\mathcal{CONGEST} model.     

Asymmetric multi-party quantum state sharing of an arbitrary m-qubit state

We present a scheme for asymmetric multi-party quantum state sharing of an arbitrary m-qubit state with n agents. The sender Alice first shares m − 1 Bell states and one n + 1-particle Greenberger–Horne–Zeilinger state with n agents, where the agent Bob, who is designated to recover the original m-qubit state, just keeps m particles and other agents (all controllers) n − 1 particles, that is, each controller only holds one particle in hand. Subsequently, Alice performs m Bell-basis measurements on her 2m particles and each controller only need take a single-particle measurement on his particle with the basis X. Finally, Bob can recover the original m-qubit state with the corresponding local unitary operations according to Alice and all controllers’ measurement results. Its intrinsic efficiency for qubits approaches 100%, and the total efficiency really approaches the maximal value, which is higher than those of the known symmetric schemes.     

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.     

Rearrangeability of (2 log n N− 1)-stage networks employing a uniform connection pattern

In this paper, we study the rearrangeablity of multistage networks. Although the necessity of (2 lg N− 1) stages for rearrangeability of a shuffle-exchange network has been known, the sufficiency of (2 lg N− 1) stages has never been proved. The best known upper bound for its rearrangeability is (3 lg N− 4). We prove that (2 log _n N− 1) stages are sufficient for the rearrangeability of a multistage network with (n×n)-switches employing a uniform interconnection pattern. This, in particular, implies the sufficiency of (2 lg N− 1) stages for the rearrangeability of a shuffle-exchange network. Received: February 2000 / Accepted: September 2000