Star reduction among minimal length addition chains

An addition chain for a natural number n is a sequence \({1=a_0 < a_1 < \cdots < a_r=n}\) of numbers such that for each 0 < i ≤ r, a _i  = a _j  + a _k for some 0 ≤ k ≤ j < i. The minimal length of an addition chain for n is denoted by ?(n). If j = i ? 1, then step i is called a star step. We show that there is a minimal length addition chain for n such that the last four steps are stars. Then we conjecture that there is a minimal length addition chain for n such that the last \({\lfloor\frac{\ell(n)}{2}\rfloor}\)-steps are stars. We verify that the conjecture is true for all numbers up to 2¹⁸. An application of the result and the conjecture to generate a minimal length addition chain reduce the average CPU time by 23–29% and 38–58% respectively, and memory storage by 16–18% and 26–45% respectively for m-bit numbers with 14 ≤ m ≤ 22.     

Negation-Limited Complexity of Parity and Inverters

In negation-limited complexity, one considers circuits with a limited number of NOT gates, being motivated by the gap in our understanding of monotone versus general circuit complexity, and hoping to better understand the power of NOT gates. We give improved lower bounds for the size (the number of AND/OR/NOT) of negation-limited circuits computing Parity and for the size of negation-limited inverters. An inverter is a circuit with inputs x ₁,…,x _n and outputs ¬ x ₁,…,¬ x _n . We show that: (a) for n=2 ^r ?1, circuits computing Parity with r?1 NOT gates have size at least 6n?log?₂(n+1)?O(1), and (b) for n=2 ^r ?1, inverters with r NOT gates have size at least 8n?log?₂(n+1)?O(1). We derive our bounds above by considering the minimum size of a circuit with at most r NOT gates that computes Parity for sorted inputs x ₁≥???≥x _n . For an arbitrary r, we completely determine the minimum size. It is 2n?r?2 for odd n and 2n?r?1 for even n for ?log?₂(n+1)??1≤r≤n/2, and it is ?3n/2??1 for r≥n/2. We also determine the minimum size of an inverter for sorted inputs with at most r NOT gates. It is 4n?3r for ?log?₂(n+1)?≤r≤n. In particular, the negation-limited inverter for sorted inputs due to Fischer, which is a core component in all the known constructions of negation-limited inverters, is shown to have the minimum possible size. Our fairly simple lower bound proofs use gate elimination arguments in a somewhat novel way.     

Error bounds for complementarity problems with tridiagonal nonlinear functions

In this paper we consider the complementarity problem NCP(f) with f(x) = Mx + φ(x), where M ∈ R ^n×n is a real matrix and φ is a so-called tridiagonal (nonlinear) mapping. This problem occurs, for example, if certain classes of free boundary problems are discretized. We compute error bounds for approximations \({\hat x}\) to a solution x* of the discretized problems. The error bounds are improved by an iterative method and can be made arbitrarily small. The ideas are illustrated by numerical experiments.     

An orthogonal analysis method for decoupling the nozzle geometrical parameters of microthrusters

This paper proposes an orthogonal analysis method for decoupling the multiple nozzle geometrical parameters of microthrusters, thus an reconfigured design can be implemented to generate a proper thrust. In this method, the effects of various nozzle geometrical parameters, including throat width W _t , half convergence angle θ _in , half divergence angle θ _out , exit-to-throat section ratio W _e /W _t and throat radius of the curvature R _t /W _t , on the performance of microthrusters are sorted by range analysis. Analysis results show that throat width seriously affects thrust because range value of 67.53 mN is extremely larger than the range value of other geometry parameters. For average specific impulse (ASI), the range value of exit-to-throat section ratio W _e /W _t and half divergence angle θ _out are 4.82 s and 3.72 s, respectively. Half convergence angle with the range value of 0.39 s and throat radius with 0.32 s have less influence on ASI compared with exit-to-throat section ratio and half divergence angle. When increasing the half convergence angle from 10° to 40° and throat radius of the curvature from 3 to 9, average specific impulse initially decreases and then increases. A MEMS solid propellant thruster (MSPT) with the reconfigured geometrical parameters of nozzle is fabricated to verify the feasibility of the proposed method. The thrust of the microthruster can reach 25 mN. Power is estimated to be 0.84 W. This work provides design guideline to reasonably configure geometry parameters of microthruster.     

Threshold quantum secret sharing based on single qubit

Based on unitary phase shift operation on single qubit in association with Shamir’s (t, n) secret sharing, a (t, n) threshold quantum secret sharing scheme (or (t, n)-QSS) is proposed to share both classical information and quantum states. The scheme uses decoy photons to prevent eavesdropping and employs the secret in Shamir’s scheme as the private value to guarantee the correctness of secret reconstruction. Analyses show it is resistant to typical intercept-and-resend attack, entangle-and-measure attack and participant attacks such as entanglement swapping attack. Moreover, it is easier to realize in physic and more practical in applications when compared with related ones. By the method in our scheme, new (t, n)-QSS schemes can be easily constructed using other classical (t, n) secret sharing.     

Filtration of aerosol particles by cylindrical fibers within a parallel and staggered array

The World Health Organization (WHO) in 2013 reported that more than seven million unexpected losses every year are credited to air contamination. Because of incredible adaptability and expense viability of fibrous filters, they are broadly used for removing particulates from gasses. The influence of appropriate parameters, e.g., the fiber arrangement, solid volume fraction (SVF or α), fluid flow face velocity (mean inlet velocity), and filter thickness (I _x ), on pressure drop and deposition efficiency are researched. Furthermore, to study the effects of variation of the laminar flow regime and fiber’s cross-sectional shape on the deposition of particles, only a single square fiber has been placed in a channel. By means of finite volume method (FVM), the 2-D motion of 100–1000 nm particles was investigated numerically. The Lagrangian method has been employed and the Saffman’s lift, Drag, and Brownian forces have been considered to affect this motion. Contribution of increasing the Reynolds number to filtration performance increased with smaller fine aerosols to a level of 59.72 %. However, for over 500 nm, the Re = 100 has more efficient results up to 26.97 %. Remarkably, the single square fiber in Re = 200 regime performs similarly to the optimum choice of multi-fibrous filters. It was portrayed the parallel circular multi-fibrous filter with a ratio of horizontal-to-vertical distances between fibers, l/h = 1.143; α = 0.687, I _x  = 116.572, and h/d _f  = 1.0 is the most efficient filter’s structure. The increase in the ratio of vertical distances between fibers-to-fiber’s diameter (h/d _f ) and decrease in SVF or α, results in a drastically decrement of the filtration performance of both parallel and staggered structures. The obtained results have been validated with previous research findings.     

Effects of topological changes in microchannel geometries on the asymmetric breakup of a droplet

Passive asymmetric breakups of a droplet could be done in many microchannels of various geometries. In order to study the effects of different geometries on the asymmetric breakup of a droplet, four types of asymmetric microchannels with the topological equivalence of geometry are designed, which are T-90, Y-120, Y-150, and I-180 microchannels. A three-dimensional volume of fluid multiphase model is employed to investigate the asymmetric rheological behaviors of a droplet numerically. Three regimes of rheological behaviors as a function of the capillary numbers Ca and the asymmetries As defined by As = (b1 ? b2)/(b1 + b2) (where b1 and b2 are the widths of two asymmetric sidearms) have been observed. A power law model based on three major factors (Ca, As and the initial volume ratio r ₀) is employed to describe the volume ratio of two daughter droplets. The analysis of pressure fields shows that the pressure gradient inside the droplet is one of the major factors causing the droplet translation during its asymmetric breakup. Besides the above similarities among various microchannels, the asymmetric breakup in them also have some slight differences as various geometries have different enhancement or constraint effects on the translation of the droplet and the cutting action of flows. It is disclosed that I-180 microchannel has the smallest critical capillary number, the shortest splitting time, and is hardest to generate satellite droplets.     

Generation and distillation of non-Gaussian entanglement from nonclassical photon statistics

With a product state of the form \({{\rho}_{\rm in} = {\rho}_{a} \otimes |0 \rangle_b {_b} \langle 0|}\) as input to a beam splitter, the output two-mode state ρ _out is shown to be negative under partial transpose (NPT) whenever the photon number distribution (PND) statistics { p(n _a ) } associated with the possibly mixed state ρ _a of the input a-mode is antibunched or otherwise nonclassical, i.e., whenever { p(n _a ) } fails to respect any one of an infinite sequence of necessary and sufficient classicality conditions. Negativity under partial transpose turns out to be a necessary and sufficient test for entanglement of ρ _out which is generically non-Gaussian. The output of a PND distribution is further shown to be distillable if any one of an infinite sequence of three term classicality conditions is violated.     

A linear-time algorithm for finding Hamiltonian (<Emphasis Type="Italic">s</Emphasis>, <Emphasis Type="Italic">t</Emphasis>)-paths in odd-sized rectangular grid graphs with a rectangular hole

A grid graph \(G_{\mathrm{g}}\) is a finite vertex-induced subgraph of the two-dimensional integer grid \(G^\infty \). A rectangular grid graph R(m, n) is a grid graph with horizontal size m and vertical size n. A rectangular grid graph with a rectangular hole is a rectangular grid graph R(m, n) such that a rectangular grid subgraph R(k, l) is removed from it. The Hamiltonian path problem for general grid graphs is NP-complete. In this paper, we give necessary conditions for the existence of a Hamiltonian path between two given vertices in an odd-sized rectangular grid graph with a rectangular hole. In addition, we show that how such paths can be computed in linear time.     

Pairs of Complementary Unary Languages with “Balanced” Nondeterministic Automata

For each sufficiently large n, there exists a unary regular language L such that both L and its complement L ^c are accepted by unambiguous nondeterministic automata with at most n states, while the smallest deterministic automata for these two languages still require a superpolynomial number of states, at least \(e^{\Omega(\sqrt[3]{n\cdot\ln^{2}n})}\). Actually, L and L ^c are “balanced” not only in the number of states but, moreover, they are accepted by nondeterministic machines sharing the same transition graph, differing only in the distribution of their final states. As a consequence, the gap between the sizes of unary unambiguous self-verifying automata and deterministic automata is also superpolynomial.     

An integrated microfluidic system using mannose-binding lectin for bacteria isolation and biofilm-related gene detection

Molecular diagnosis of biofilm-related genes (BRGs) in common bacteria that cause periprosthetic joint infections may provide crucial information for clinicians. In this study, several BRGs, including ica, fnbA, and fnbB, were rapidly detected (within 1 h) with a new integrated microfluidic system. Mannose-binding lectin (MBL)-coated magnetic beads were used to isolate these bacteria, and on-chip nucleic acid amplification (polymerase chain reaction, PCR) was then performed to detect BRGs. Both eukaryotic and prokaryotic MBLs were able to isolate common bacterial strains, regardless of their antibiotic resistance, and limits of detection were as low as 3 and 9 CFU for methicillin-resistant Staphylococcus aureus and Escherichia coli, respectively, when using a universal 16S rRNA PCR assay for bacterial identification. It is worth noting that the entire process including bacteria isolation by using MBL-coated beads for sample pre-treatment, on-chip PCR, and fluorescent signal detection could be completed on an integrated microfluidic system within 1 h. This is the first time that an integrated microfluidic system capable of detecting BRGs by using MBL as a universal capturing probe was reported. This integrated microfluidic system might therefore prove useful for monitoring profiles of BRGs and give clinicians more clues for their clinical judgments in the near future.     

Some properties of the disjunctive languages contained in <Emphasis Type="Italic">Q</Emphasis>

The set of all primitive words Q over an alphabet X was first defined and studied by Shyr and Thierrin (Proceedings of the 1977 Inter. FCT-Conference, Poznan, Poland, Lecture Notes in Computer Science 56. pp. 171–176 (1977)). It showed that for the case |X| ≥ 2, the set along with \({Q^{(i)} = \{f^i\,|\,f \in Q\}, i\geq 2}\) are all disjunctive. Since then these disjunctive sets are often be quoted. Following Shyr and Thierrin showed that the half sets \({Q_{ev} = \{f \in Q\,|\,|f| = {\rm even}\}}\) and Q _od = Q \ Q _ev of Q are disjunctive, Chien proved that each of the set \({Q_{p,r}= \{u\in Q\,|\,|u|\equiv r\,(mod\,p) \},\,0\leq r < p}\) is disjunctive, where p is a prime number. In this paper, we generalize this property to that all the languages \({Q_{n,r}= \{u\in Q\,|\,|u|\equiv r\,(mod\,n) \},\, 0\leq r < n}\) are disjunctive languages, where n is any positive integer. We proved that for any n ≥ 1, k ≥ 2, (Q _n,0) ^k are all regular languages. Some algebraic properties related to the family of languages {Q _n,r | n ≥ 2, 0 ≤ r < n } are investigated.     

The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number

In the framework of parameterized complexity, exploring how one parameter affects the complexity of a different parameterized (or unparameterized problem) is of general interest. A well-developed example is the investigation of how the parameter treewidth influences the complexity of (other) graph problems. The reason why such investigations are of general interest is that real-world input distributions for computational problems often inherit structure from the natural computational processes that produce the problem instances (not necessarily in obvious, or well-understood ways). The max leaf number ml(G) of a connected graph G is the maximum number of leaves in a spanning tree for G. Exploring questions analogous to the well-studied case of treewidth, we can ask: how hard is it to solve 3-Coloring, Hamilton Path, Minimum Dominating Set, Minimum Bandwidth or many other problems, for graphs of bounded max leaf number? What optimization problems are W[1]-hard under this parameterization? We do two things:

1. (1)
   We describe much improved FPT algorithms for a large number of graph problems, for input graphs G for which ml(G)≤k, based on the polynomial-time extremal structure theory canonically associated to this parameter. We consider improved algorithms both from the point of view of kernelization bounds, and in terms of improved fixed-parameter tractable (FPT) runtimes O ^*(f(k)).
    
2. (2)
   The way that we obtain these concrete algorithmic results is general and systematic. We describe the approach, and raise programmatic questions.
    

     

The weight-constrained maximum-density subtree problem and related problems in trees

Given a tree T=(V,E) of n nodes such that each node v is associated with a value-weight pair (val _v ,w _v ), where value val _v is a real number and weight w _v is a non-negative integer, the density of T is defined as \(\frac{\sum_{v\in V}{\mathit{val}}_{v}}{\sum_{v\in V}w_{v}}\). A subtree of T is a connected subgraph (V′,E′) of T, where V′?V and E′?E. Given two integers w _min? and w _max?, the weight-constrained maximum-density subtree problem on T is to find a maximum-density subtree T′=(V′,E′) satisfying w _min?≤∑_v∈V′ w _v ≤w _max?. In this paper, we first present an O(w _max? n)-time algorithm to find a weight-constrained maximum-density path in a tree T, and then present an O(w _max? ² n)-time algorithm to find a weight-constrained maximum-density subtree in T. Finally, given a node subset S?V, we also present an O(w _max? ² n)-time algorithm to find a weight-constrained maximum-density subtree in T which covers all the nodes in S.     

On the Price of Heterogeneity in Parallel Systems

Suppose we have a parallel or distributed system whose nodes have limited capacities, such as processing speed, bandwidth, memory, or disk space. How does the performance of the system depend on the amount of heterogeneity of its capacity distribution? We propose a general framework to quantify the worst-case effect of increasing heterogeneity in models of parallel systems. Given a cost function g(C,W) representing the system’s performance as a function of its nodes’ capacities C and workload W (such as the makespan of an optimum schedule of jobs W on machines C), we say that g has price of heterogeneity α when for any workload, cost cannot increase by more than a factor α if node capacities become arbitrarily more heterogeneous. The price of heterogeneity also upper bounds the “value of parallelism”: the maximum benefit obtained by increasing parallelism at the expense of decreasing processor speed. We give constant or logarithmic bounds on the price of heterogeneity of several well-known job scheduling and graph degree/diameter problems, indicating that in many cases, increasing heterogeneity can never be much of a disadvantage.     

Using neural networks to integrate structural analysis package and optimization package

To solve structural optimization problems, it is necessary to integrate a structural analysis package and an optimization package. Since most structural analysis packages suffer from closeness of system, it is very difficult to integrate it with an optimization package. To overcome the difficulty, we propose a possible alternative, DAMDO, which integrate Design, Analysis, Modeling, Definition, and Optimization phases into an integration environment as follows. (1) Design first generate many possible structural design alternatives. Each design alternative consists of many design variables X. (2) Analysis employ the structural analysis software to analyze all structural design alternatives to obtain their internal forces and displacements. They are the response variables Y. (3) Modeling employ artificial neural networks to build model Y = f(X) to obtain the relationship functions between the design variables X and the response variables Y. (4) Definition employ the design variables X and the response variables Y to define the objective function and constraint functions. (5) Optimization employ the optimization software to solve the optimization problem consisting of the objective function and the constraint functions to produce the optimum design variables X*. Optimization of truss structures was used to validate the DAMDO approach. The empirical results show that the truss optimization problems can be solved by the DAMDO approach, which employ neural networks to integrate the structural analysis package and optimization package without requiring direct integration of the two packages. This approach is promising in many engineering optimization domains which need to couple an analysis package and an optimization one to obtain the optimum solutions.     

Eliminating Cycles in the Discrete Torus

In this paper we consider the following question: how many vertices of the discrete torus must be deleted so that no topologically nontrivial cycles remain?We look at two different edge structures for the discrete torus. For (? _m ^d )₁, where two vertices in ? _m are connected if their ? ₁ distance is 1, we show a nontrivial upper bound of \(d^{\log_{2}(3/2)}m^{d-1}\approx d^{0.6}m^{d-1}\) on the number of vertices that must be deleted. For (? _m ^d )_∞, where two vertices are connected if their ? _∞ distance is 1, Saks et al. (Combinatorica 24(3):525–530, 2004) already gave a nearly tight lower bound of d(m?1) ^d?1 using arguments involving linear algebra. We give a more elementary proof which improves the bound to m ^d ?(m?1) ^d , which is precisely tight.     

On Optimally Partitioning a Text to Improve Its Compression

In this paper we investigate the problem of partitioning an input string T in such a way that compressing individually its parts via a base-compressor C gets a compressed output that is shorter than applying C over the entire T at once. This problem was introduced in Buchsbaum et al. (Proc. of 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 175–184, 2000; J. ACM 50(6):825–851, 2003) in the context of table compression, and then further elaborated and extended to strings and trees by Ferragina et al. (J. ACM 52:688–713, 2005; Proc. of 46th IEEE Symposium on Foundations of Computer Science, pp. 184–193, 2005) and Mäkinen and Navarro (Proc. of 14th Symposium on String Processing and Information Retrieval, pp. 229–241, 2007). Unfortunately, the literature offers poor solutions: namely, we know either a cubic-time algorithm for computing the optimal partition based on dynamic programming (Buchsbaum et al. in J. ACM 50(6):825–851, 2003; Giancarlo and Sciortino in Proc. of 14th Symposium on Combinatorial Pattern Matching, pp. 129–143, 2003), or few heuristics that do not guarantee any bounds on the efficacy of their computed partition (Buchsbaum et al. in Proc. of 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 175–184, 2000; J. ACM 50(6):825–851, 2003), or algorithms that are efficient but work in some specific scenarios (such as the Burrows-Wheeler Transform, see e.g. Ferragina et al. in J. ACM 52:688–713, 2005; Mäkinen and Navarro in Proc. of 14th Symposium on String Processing and Information Retrieval, pp. 229–241, 2007) and achieve compression performance that might be worse than the optimal-partitioning by a Ω(log?n/log?log?n) factor. Therefore, computing efficiently the optimal solution is still open (Buchsbaum and Giancarlo in Encyclopedia of Algorithms, pp. 939–942, 2008). In this paper we provide the first algorithm which computes in O(nlog?_1+ε n) time and O(n) space, a partition of T whose compressed output is guaranteed to be no more than (1+ε)-worse the optimal one, where ε may be any positive constant fixed in advance. This result holds for any base-compressor C whose compression performance can be bounded in terms of the zero-th or the k-th order empirical entropy of the text T. We will also discuss extensions of our results to BWT-based compressors and to the compression booster of Ferragina et al. (J. ACM 52:688–713, 2005).     

A new strategy for generating shortest addition sequences

An addition sequence problem is given a set of numbers X = {n ₁, n ₂, . . . , n _m }, what is the minimal number of additions needed to compute all m numbers starting from 1? This problem is NP-complete. In this paper, we present a branch and bound algorithm to generate an addition sequence with a minimal number of elements for a set X by using a new strategy. Then we improve the generation by generalizing some results on addition chains (m = 1) to addition sequences and finding what we will call a presumed upper bound for each n _j , 1 ≤ j ≤ m, in the search tree.     

Linear Time Algorithms for Generalizations of the Longest Common Substring Problem

In its simplest form, the longest common substring problem is to find a longest substring common to two or multiple strings. Using (generalized) suffix trees, this problem can be solved in linear time and space. A first generalization is the k -common substring problem: Given m strings of total length n, for all k with 2≤k≤m simultaneously find a longest substring common to at least k of the strings. It is known that the k-common substring problem can also be solved in O(n) time (Hui in Proc. 3rd Annual Symposium on Combinatorial Pattern Matching, volume 644 of Lecture Notes in Computer Science, pp. 230–243, Springer, Berlin, 1992). A further generalization is the k -common repeated substring problem: Given m strings T ⁽¹⁾,T ⁽²⁾,…,T ^(m) of total length n and m positive integers x ₁,…,x _m , for all k with 1≤k≤m simultaneously find a longest string ω for which there are at least k strings \(T^{(i_{1})},T^{(i_{2})},\ldots,T^{(i_{k})}\) (1≤i ₁<i ₂<???<i _k ≤m) such that ω occurs at least \(x_{i_{j}}\) times in \(T^{(i_{j})}\) for each j with 1≤j≤k. (For x ₁=???=x _m =1, we have the k-common substring problem.) In this paper, we present the first O(n) time algorithm for the k-common repeated substring problem. Our solution is based on a new linear time algorithm for the k-common substring problem.