On the Computation of Powers of Sparse Polynomials

This paper examines the time for computing integer powers of a class of polynomials in one or several variables. A member f of the class of “sparse” polynomials can be characterized by the number of nonzero terms, t, in the representation of f. Where, for power 4, the most obvious methods result in multiplications, a method is presented which requires fewer than multiplications. This algorithm requires, for t » n » 1 about tⁿ/n! + O(t^{n ? 1} /(2(n ? 2)!)) multiplications, which is proved to be a lower-bound on the computation.     

Multi-party computation with conversion of secret sharing

Classical results in unconditionally secure multi-party computation (MPC) protocols with a passive adversary indicate that every n-variate function can be computed by n participants, such that no set of size t < n/2 participants learns any additional information other than what they could derive from their private inputs and the output of the protocol. We study unconditionally secure MPC protocols in the presence of a passive adversary in the trusted setup (‘semi-ideal’) model, in which the participants are supplied with some auxiliary information (which is random and independent from the participant inputs) ahead of the protocol execution (such information can be purchased as a “commodity” well before a run of the protocol). We present a new MPC protocol in the trusted setup model, which allows the adversary to corrupt an arbitrary number t < n of participants. Our protocol makes use of a novel subprotocol for converting an additive secret sharing over a field to a multiplicative secret sharing, and can be used to securely evaluate any n-variate polynomial G over a field F, with inputs restricted to non-zero elements of F. The communication complexity of our protocol is O(ℓ · n ²) field elements, where ℓ is the number of non-linear monomials in G. Previous protocols in the trusted setup model require communication proportional to the number of multiplications in an arithmetic circuit for G; thus, our protocol may offer savings over previous protocols for functions with a small number of monomials but a large number of multiplications.     

On the reduction of a symmetric matrix to tridiagonal form

A stable algorithm for reducing a symmetric, non-definite matrix of ordern to tridiagonal form, involving aboutn ³/6 additions and multiplications is presented.     

The retraction algorithm for factoring banded symmetric matrices

Let A be an n × n symmetric matrix of bandwidth 2m + 1. The matrix need not be positive definite. In this paper we will present an algorithm for factoring A which preserves symmetry and the band structure and limits element growth in the factorization. With this factorization one may solve a linear system with A as the coefficient matrix and determine the inertia of A, the number of positive, negative, and zero eigenvalues of A. The algorithm requires between 1/2nm² and 5/4nm² multiplications and at most (2m + 1)n locations compared to non‐symmetric Gaussian elimination which requires between nm² and 2nm² multiplications and at most (3m + 1)n locations. Our algorithm reduces A to block diagonal form with 1 × 1 and 2 × 2 blocks on the diagonal. When pivoting for stability and subsequent transformations produce non‐zero elements outside the original band, column/row transformations are used to retract the bandwidth. To decrease the operation count and the necessary storage, we use the fact that the correction outside the band is rank‐1 and invert the process, applying the transformations that would restore the bandwidth first, followed by a modified correction. This paper contains an element growth analysis and a computational comparison with LAPACKs non‐symmetric band routines and the Snap‐back code of Irony and Toledo. Copyright © 2007 John Wiley & Sons, Ltd.     

Lower Bounds for Shellsort

We show lower bounds on the worst-case complexity of Shellsort. In particular, we give a fairly simple proof of an Ω(n (lg² n)/(lg lg n)²) lower bound for the size of Shellsort sorting networks for arbitrary increment sequences. We also show an identical lower bound for the running time of Shellsort algorithms, again for arbitrary increment sequences. Our lower bounds establish an almost tight trade-off between the running time of a Shellsort algorithm and the length of the underlying increment sequence.     

On classification of orthogonal multiplications à la do carmo-wallach

The space of range-equivalence classes of full orthogonal multiplications F: ℝ ⁿ ×ℝ ⁿ →ℝ ^p , n≤p ≤n ², is shown to be a compact convex body lying in so(n)⊗so(n). Furthermore, the dimension of the space of equivalence classes is determined to be (n ²(n−1)²)/4−n(n−1).     

Base tensorielle des matrices de Hankel (ou de Toeplitz) Applications

Summary The set of all Hankel (or Toeplitz) matrices of dimensionn, is shown to possess tensorial bases: bases made ofn rank one matrices. Four families of such tensorial bases are possible. From this result, we deduce that the following computations can be performed with a number of multiplications of ordern instead of ordern ²: evaluation of the 2n+1 coefficients of the polynomial product of two polynomials of degreen, evaluation of the inverse of a lower triangular toeplitz matrix, evaluation of the quotient and of the remainder in the division of a polynomial of degree 2n by a polynomial of degreen.     

Can Montgomery parasites be avoided? A design methodology based on key and cryptosystem modifications

Montgomery's algorithm [8], hereafter denotedM _n(...,...), is a process for computingM _n (A, B)=ABN modn whereN is a constant factor depending only onn.Usually,A B modn is obtained byM _n (M _n (A, B),N ^–2 modn) but in this article, we introduce an alternative approach consisting in pre-integratingN into cryptographic keys so that a singleM _n(...,...) will replace directly each modular multiplication.Except the advantage of halving the number of Montgomery multiplications, our strategy skips the precalculation (and the storage) of the constantN ^–2 modn and turns to be particularly efficient when a hardware device implementingM _n(...,...) is the basic computational tool at one's command.     

B-spline quasi-interpolation on sparse grids

We propose a periodic B-spline quasi-interpolation for multivariate functions on sparse grids and develop a fast scheme for the evaluation of a linear combination of B-splines on sparse grids. We prove that both of these operations require only O(nlog^d−1n) number of multiplications, where n is the number of univariate B-spline basis functions used in each coordinate direction and d is the number of variables of the functions. We also establish the optimal approximation order of the periodic B-spline quasi-interpolation. Numerical examples are presented to confirm the theoretical estimates.     

Piecewise linear paths among convex obstacles

Let ℬ be a set ofn arbitrary (possibly intersecting) convex obstacles in ℝ ^d . It is shown that any two points which can be connected by a path avoiding the obstacles can also be connected by a path consisting ofO(n ^{(d−1)[d/2+1]}) segments. The bound cannot be improved below Ω(n ^d ); thus, in ℝ³, the answer is betweenn ³ andn ⁴. For open disjoint convex obstacles, a Θ(n) bound is proved. By a well-known reduction, the general case result also upper bounds the complexity for a translational motion of an arbitrary convex robot among convex obstacles. Asymptotically tight bounds and efficient algorithms are given in the planar case. This research was supported by The Netherlands' Organization for Scientific Research (NWO) and partially by the ESPRIT III Basic Research Action 6546 (PROMotion). J. M. acknowledges support by a Humboldt Research Fellowship. Part of this research was done while he visited Utrecht University.     

Stable Local Bases for Multivariate Spline Spaces

We present an algorithm for constructing stable local bases for the spaces ^r_d(Δ) of multivariate polynomial splines of smoothness r1 and degree dr2ⁿ+1 on an arbitrary triangulation Δ of a bounded polyhedral domain Ω ⁿ, n2.     

Generalized Cn-Manifolds

This paper proves an important topological characterization of C-manifolds and especially of arbitrary finite dimensional Cⁿ-manifolds and arbitrary C∞-BANACH manifolds. Whereas differentiability structures in the usual sense may be proper classes this characterization always enables a definition of differentiability structures as sets. Further this characterization suggests a suitable generalization of the notion of differentiable manifold which we call Cⁿ-manifold. C ⁿ-manifolds have a lot of better properties than Cⁿ-manifolds and may be useful therefore in physics and technics. Some examples of C ⁿ-manifolds are given in the last two sections defined by means of certain geometric structures.     

On isometries of matrix spaces

Let A _kbe the group of isometries of the space of n-by-n matrices over reals (resp. complexes, quaternions) with respect to the Ky Fan k-norm (see the Introduction for the definitions). Let Γ⁰ be the group of transformations of this space consisting of all products of left and right multiplications by the elements of SO(n)(resp. U(n), Sp(n)). It is shown that, except for three particular casesA_k coincides with the normalizer of Γ in Δ group of isometries of the above matrix space with respect to the standard inner product. We also give an alternative treatment of the case D = R n = 4k = 2 which was studied in detail by Johnson, Laffey, and Li [4].     

On connectionist models

We show that an arbitrary “connectionist” model of n neutrons, defined by an n X n real matrix, can be simulated by a system of O(n³log n) Boolean gates with an O(log n) time slow-down factor. This establishes that, even though n² real numbers possibly of high precision are required to define it, connectionist models do not possess any basic properties different from those of other (nonuniform) highly parallel hardware models.     

Polynomial area bounds for MST embeddings of trees

In their seminal paper on geometric minimum spanning trees, Monma and Suri (1992) [31] showed how to embed any tree of maximum degree 5 as a minimum spanning tree in the Euclidean plane. The embeddings provided by their algorithm require area O(n²²)×O(n²²) and the authors conjectured that an improvement below cn×cn is not possible, for some constant c>0. In this paper, we show how to construct MST embeddings of arbitrary trees of maximum degree 3 and 4 within polynomial area.     

Verifiable Partial Escrow of Integer Factors

We construct an efficient interactive protocol for realizing verifiable partial escrow of the factors of an integer n with time-delayed and threshold key recovery features. The computational cost of the new scheme amounts to 10k P multiplications of numbers of size of P, where P is a protocol parameter which permits n of size up to ( P) - 4 to be dealt with and k is a security parameter which controls the error probability for correct key escrow under 1/2^k. The new scheme realizes a practical method for fine tuning the time complexity for factoring an integer, where the complexity tuning has no respect to the size of the integer.     

Optimal receiver scheduling algorithms for a multicast problem

This paper studies a multicast problem arising in wavelength division multiplexing single-hop lightwave networks, as well as in Video-on-Demand systems. In this problem, the same message of duration Δ has to be transmitted to a set of n receivers which are not all available simultaneously. The receivers can be partitioned into subsets, each served by a different transmission, with the objective of minimizing their overall waiting cost. When there is a single data channel available for transmission, a dynamic programming algorithm is devised which finds an optimal solution in O(nlogn+min{n²,nΔ²}) time, improving over a previously known O(n³) time algorithm. When multiple data channels are available for transmission, an optimal O(n) time algorithm is proposed which finds an optimal solution if the message has constant transmission duration, whereas an NP-completeness proof is given if the message has arbitrary transmission duration.     

Operations on orbits of unimodular vectors

Taking the m-power of an entry is a well-defined operation on the unimodular vectors in Aⁿ modulo addition operations, if n is at least 3, for an arbitrary commutative ring A and any integer m.     

Wavelet sets in ℝ n

A congruency theorem is proven for an ordered pair of groups of homeomorphisms of a metric space satisfying an abstract dilation-translation relationship. A corollary is the existence of wavelet sets, and hence of single-function wavelets, for arbitrary expansive matrix dilations on L ² (ℝ ⁿ). Moreover, for any expansive matrix dilation, it is proven that there are sufficiently many wavelet sets to generate the Borel structure ofℝ ⁿ. The second author is supported in part by NSF Grant DMS-9401544. The third author was a Graduate Research Assistant at Workshop in Linear Analysis and Probability, Texas A&M University.