The query complexity of order-finding

We consider the problem where π is an unknown permutation on {0,1,…,2ⁿ−1}, y₀{0,1,…,2ⁿ−1}, and the goal is to determine the minimum r>0 such that π^r(y₀)=1. Information about π is available only via queries that yield π^x(y) from any x{0,1,…,2^m−1} and y{0,1,…,2ⁿ−1} (where m is polynomial in n). The main resource under consideration is the number of these queries. We show that the number of queries necessary to solve the problem in the classical probabilistic bounded-error model is exponential in n. This contrasts sharply with the quantum bounded-error model, where a constant number of queries suffices.     

Ordering the order of a distributive lattice by itself

We order the ordering relation of an arbitrary poset P component-wise by itself, obtaining a poset Φ(P) extending P. In particular, the effects of Φ on L  DLAT01, the category of all bounded distributive lattices, are studied, mainly with the aid of Priestley duality. We characterize those L  DLAT01 which occur as Φ(K) for some K  DLAT01, decide this situation in polynomial time for finite L, characterize fixpoints of Φ within DLAT01 and relate them to free objects in DLAT01.     

Elements of small norm in Shanks’ cubic extensions of imaginary quadratic fields

Let be an imaginary quadratic number field with ring of integers Z_k and let k(α) be the cubic extension of k generated by the polynomial f_t(x)=x³−(t−1)x²−(t+2)x−1 with tZ_k. In the present paper we characterize all elements γZ_k[α] with norms satisfying |N_k(α)/k|≤|2t+1| for |t|≥14. This generalizes a corresponding result by Lemmermeyer and Pethő for Shanks’ cubic fields over the rationals.     

Adjustable speed surface subdivision

We introduce a non-uniform subdivision algorithm that partitions the neighborhood of an extraordinary point in the ratio σ:1−σ, where σ(0,1). We call σ the speed of the non-uniform subdivision and verify C¹ continuity of the limit surface. For σ=1/2, the Catmull–Clark limit surface is recovered. Other speeds are useful to vary the relative width of the polynomial spline rings generated from extraordinary nodes.     

Interactions Between PVS and Maple in Symbolic Analysis of Control Systems

This paper presents a decision procedure for problems relating polynomial and transcendental functions. The procedure applies to functions that are continuously differentiable with a finite number of points of inflection in a closed convex set. It decides questions of the form ‘is f0?’, where {=,>,<}. An implementation of the procedure in Maple and PVS exploits the existing Maple, PVS and QEPCAD connections. It is at present limited to those twice differentiable functions whose derivatives are rational functions (rationally differentiable). This procedure is particularly applicable to the analysis of control systems in determining important properties such as stability.     

Liquid–solid equilibria in quinary system Na,Mg/Cl,SO4,NO3–H2O at 298.15 K

In order to develop the nitrate deposits found close to Lop Nur in the Xinjiang region in China, the solubilities of the system Na⁺,Mg²⁺/Cl⁻,SO₄²⁻, NO₃⁻–H₂O and its subsystems, the quaternary systems Na⁺,Mg²⁺/SO₄²⁻,NO₃⁻–H₂O and Mg²⁺/Cl⁻,SO₄²⁻,NO₃⁻–H₂O, were studied at 298.15 K. The phase diagrams were plotted according to the solubilities achieved. In the equilibrium phase diagram of Mg²⁺/Cl⁻,SO₄²⁻,NO₃⁻–H₂O, there are two invariant points, five univariant curves and four regions of crystallization: Mg(NO₃)₂6H₂O,MgCl₂6H₂O,MgSO₄7H₂O and MgSO₄(1–6)H₂O. In the equilibrium phase diagram of Na⁺,Mg²⁺/SO₄²⁻, NO₃⁻–H₂O, there are five invariant points, eleven univariant curves and seven regions of crystallization: Na₂SO₄,Na₂SO₄10H₂O,NaNO₃,MgSO₄Na₂SO₄4H₂O,NaNO₃Na₂SO₄2H₂O,Mg(NO₃)₂6H₂O and MgSO₄7H₂O. In the equilibrium phase diagram of the Na⁺, Mg²⁺/Cl⁻,SO₄²⁻,NO₃⁻–H₂O system, there are six invariant points, and ten regions of crystallization: NaCl, NaNO₃,Na₂SO₄,Na₂SO₄10H₂O,MgSO₄Na₂SO₄4H₂O, NaNO₃Na₂SO₄2H₂O,MgCl₂6H₂O,Mg(NO₃)₂6H₂O, MgSO₄(1–6)H₂O and MgSO₄7H₂O.     

On Some Schützenberger Conjectures

In this paper we consider factorizing codes C over A, i.e., codes verifying the factorization conjecture by Schützenberger. Let n be the positive integer such that aⁿC, we show how we can construct C starting with factorizing codes C′ with a^n′C′ and n′ < n, under the hypothesis that all words aⁱza^j in C, with z(A\a)A*(A\a) (A\a), satisfy i, j, > n. The operation involved, already introduced by Anselmo, is also used to show that all maximal codes C=P(A−1)S+1 with P, SZA and P or S in Za can be constructed by means of this operation starting with prefix and suffix codes. Old conjectures by Schützenberger have been revised.     

Lower Bounds for Merging Networks

A lower bound theorem is established for the number of comparators in a merging network. Let M(m, n) be the least number of comparators required in the (m, n)-merging networks, and let C(m, n) be the number of comparators in Batcher's (m, n)-merging network, respectively. We prove for n≥1 that M(4, n)=C(4, n) for n≡0, 1, 3 mod 4, M(4, n)≥C(4, n)−1 for n≡2 mod 4, and M(5, n)=C(5, n) for n≡0, 1, 5 mod 8. Furthermore Batcher's (6, 8k+6)-, (7, 8k+7)-, and (8, 8k+8)-merging networks are optimal for k≥0. Our lower bound for (m, n)-merging networks, m≤n, has the same terms as C(m, n) has as far as n is concerned. Thus Batcher's (m, n)-merging network is optimal up to a constant number of comparators, where the constant depends only on m. An open problem posed by Yao and Yao (Lower bounds on merging networks, J. Assoc. Comput. Mach.23, 566–571) is solved: lim_n→∞M(m, n)/n=log m/2+m/2^{log m}.     

A note on Rooted Survivable Networks

The (undirected) Rooted Survivable Network Design (Rooted SND) problem is: given a complete graph on node set V with edge-costs, a root sV, and (node-)connectivity requirements , find a minimum cost subgraph G that contains r(t) internally-disjoint st-paths for all tT. For large values of k=max_tTr(t) Rooted SND is at least as hard to approximate as Directed Steiner Tree [Y. Lando, Z. Nutov, Inapproximability of survivable networks, Theoret. Comput. Sci. 410 (21–23) (2009) 2122–2125]. For Rooted SND, [J. Chuzhoy, S. Khanna, Algorithms for single-source vertex-connectivity, in: FOCS, 2008, pp. 105–114] gave recently an approximation algorithm with ratio O(k²logn). Independently, and using different techniques, we obtained at the same time a simpler primal–dual algorithm with the same ratio.     

Existence of set-interpolating and energy-minimizing curves

We consider existence of curves which minimize an energy of the form ∫c^(k)p (k=1,2,… , 1<p<∞) under side-conditions of the form G_j(c(t_1,j),…,c^(k−1)(t_k,j))M_j, where G_j is a continuous function, t_i,j[0,1], M_j is some closed set, and the indices j range in some index set J. This includes the problem of finding energy minimizing interpolants restricted to surfaces, and also variational near-interpolating problems. The norm used for vectors does not have to be Euclidean.It is shown that such an energy minimizer exists if there exists a curve satisfying the side conditions at all, and if among the interpolation conditions there are at least k points to be interpolated. In the case k=1, some relations to arc length are shown.