Diagonalisation schemes and applications

These notes develop aspects of perturbation theory of matrices related to so-called diagonalisation schemes. Primary focus is on constructive tools to derive asymptotic expansions for small/large parameters of eigenvalues and eigenprojections of families of matrices depending upon real/complex parameters. Applications of the schemes in different frameworks are also discussed and references to further applications given.     

Volume-preserving algorithms for source-free dynamical systems

Summary. In this paper, we first expound why the volume-preserving algorithms are proper for numerically solving source-free systems and then prove all the conventional methods are not volume-preserving. Secondly, we give a general method of constructing volume-preserving difference schemes for source-free systems on the basis of decomposing a source-free vector field as a finite sum of essentially 2-dimensional Hamiltonian fields and of composing the corresponding essentially symplectic schemes into a volume-preserving one. Lastly, we make some special discussions for so-called separable source-free systems for which arbitrarily high order explicit revertible volume-preserving schemes can be constructed. Received March 22, 1994 / Revised version received January 25, 1995     

Signcryption schemes with threshold unsigncryption,and applications

The goal of a signcryption scheme is to achieve the same functionalities as encryption and signature together, but in a more efficient way than encrypting and signing separately. To increase security and reliability in some applications, the unsigncryption phase can be distributed among a group of users, through a (t, n)-threshold process. In this work we consider this task of threshold unsigncryption, which has received very few attention from the cryptographic literature up to now (maybe surprisingly, due to its potential applications). First we describe in detail the security requirements that a scheme for such a task should satisfy: existential unforgeability and indistinguishability, under insider chosen message/ciphertext attacks, in a multi-user setting. Then we show that generic constructions of signcryption schemes (by combining encryption and signature schemes) do not offer this level of security in the scenario of threshold unsigncryption. For this reason, we propose two new protocols for threshold unsigncryption, which we prove to be secure, one in the random oracle model and one in the standard model. The two proposed schemes enjoy an additional property that can be very useful. Namely, the unsigncryption protocol can be divided in two phases: a first one where the authenticity of the ciphertext is verified, maybe by a single party; and a second one where the ciphertext is decrypted by a subset of t receivers, without using the identity of the sender. As a consequence, the schemes can be used in applications requiring some level of anonymity, such as electronic auctions.     

New results and applications for multi-secret sharing schemes

In a multi-secret sharing scheme (MSSS), \(\ell \) different secrets are distributed among the players in some set \(\mathcal{P }=\{P_1,\ldots ,P_n\}\) , each one according to an access structure. The trivial solution to this problem is to run \(\ell \) independent instances of a standard secret sharing scheme, one for each secret. In this solution, the length of the secret share to be stored by each player grows linearly with \(\ell \) (when keeping all other parameters fixed). Multi-secret sharing schemes have been studied by the cryptographic community mostly from a theoretical perspective: different models and definitions have been proposed, for both unconditional (information-theoretic) and computational security. In the case of unconditional security, there are two different definitions. It has been proved that, for some particular cases of access structures that include the threshold case, a MSSS with the strongest level of unconditional security must have shares with length linear in \(\ell \) . Therefore, the optimal solution in this case is equivalent to the trivial one. In this work we prove that, even for a more relaxed notion of unconditional security, and for some kinds of access structures (in particular, threshold ones), we have the same efficiency problem: the length of each secret share must grow linearly with \(\ell \) . Since we want more efficient solutions, we move to the scenario of MSSSs with computational security. We propose a new MSSS, where each secret share has constant length (just one element), and we formally prove its computational security in the random oracle model. To the best of our knowledge, this is the first formal analysis on the computational security of a MSSS. We show the utility of the new MSSS by using it as a key ingredient in the design of two schemes for two new functionalities: multi-policy signatures and multi-policy decryption. We prove the security of these two new multi-policy cryptosystems in a formal security model. The two new primitives provide similar functionalities as attribute-based cryptosystems, with some advantages and some drawbacks that we discuss at the end of this work.     

Characters of table algebras and applications to association schemes

Hanaki [A. Hanaki, Representations of association schemes and their factor schemes, Graphs Combin. 19 (2003) 195-201; A. Hanaki, Characters of association schemes and normal closed subsets, Graphs Combin. 19 (2003) 363-369] generalized many properties of characters of finite groups to characters of association schemes. In this paper we show that many of these properties also hold for table algebras. Our approach is not to generalize the proofs in [A. Hanaki, Representations of association schemes and their factor schemes, Graphs Combin. 19 (2003) 195-201; A. Hanaki, Characters of association schemes and normal closed subsets, Graphs Combin. 19 (2003) 363-369] to table algebras, but to prove many stronger properties, and then obtain results in [A. Hanaki, Representations of association schemes and their factor schemes, Graphs Combin. 19 (2003) 195-201; A. Hanaki, Characters of association schemes and normal closed subsets, Graphs Combin. 19 (2003) 363-369] as direct consequences.     

On multiresolution schemes using a stencil selection procedure: applications to ENO schemes

This paper is devoted to multiresolution schemes that use a stencil selection procedure in order to obtain adaptation to the presence of edges in the images. Since non adapted schemes, based on a centered stencil, are less affected by the presence of texture, we propose the introduction of some weight that leads to a more frequent use of the centered stencil in regions without edges. In these regions the different stencils have similar weights and therefore the selection becomes an ill-posed problem with high risk of instabilities. In particular, numerical artifacts appear in the decompressed images. Our attention is centered in ENO schemes, but similar ideas can be developed for other multiresolution schemes. A nonlinear multiresolution scheme corresponding to a nonlinear interpolatory technique is analyzed. It is based on a modification of classical ENO schemes. As the original ENO stencil selection, our algorithm chooses the stencil within a region of smoothness of the interpolated function if the jump discontinuity is sufficiently big. The scheme is tested, allowing to compare its performances with other linear and nonlinear schemes. The algorithm gives results that are at least competitive in all the analyzed cases. The problems of the original ENO interpolation with the texture of real images seem solved in our numerical experiments. Our modified ENO multiresolution will lead to a reconstructed image free of numerical artifacts or blurred regions, obtaining similar results than WENO schemes. Similar ideas can be used in multiresolution schemes based in other stencil selection algorithms.      

A stratification of Hilbert schemes by initial ideals and applications

We show that the set of the homogeneous saturated ideals with given initial ideal in a fixed term-ordering is locally closed in the Hilbert scheme, and that it is affine if the initial ideal is saturated. Then, Hilbert schemes can be stratified using these subschemes. We investigate the behaviour of this stratification with respect to some properties of the closed points. As application, we describe the singular locus of the component of Hilb^{4 z +1} _ℙ4 containing the ACM curves of degree 4. Received: 30 November 1998 / Revised version: 16 September 1999     

On pseudocyclic table algebras and applications to pseudocyclic association schemes

We effect a complete study of the thermodynamic formalism, the entropy spectrum of Birkhoff averages, and the ergodic optimization problem for a family of parabolic horseshoes. We consider a large class of potentials that are not necessarily regular, and we describe both the uniqueness of equilibrium measures and the occurrence of phase transitions for nonregular potentials in this class. Our approach consists in reducing the problems to the study of renewal shifts. We also describe applications of this approach to hyperbolic horseshoes as well as to noninvertible maps, both parabolic (with the Manneville-Pomeau map) and uniformly expanding. This allows us to recover in a unified manner several results scattered in the literature. For the family of hyperbolic horseshoes, we also describe the dimension spectrum of equilibrium measures of a class of potentials that are not necessarily regular. In particular, the dimension spectra need not be strictly convex.     

On IP-graphs of association schemes and applications to group theory

Let G be a group acting transitively on a set X such that all subdegrees are finite. Isaacs and Praeger (1993) [5] studied the common divisor graph of (G,X). For a group G and its subgroup A, based on the results in Isaacs and Praeger (1993) [5], Kaplan (1997) [6] proved that if A is stable in G and the common divisor graph of (A,G) has two components, then G has a nice structure. Motivated by the notion of the common divisor graph of (G,X), Camina (2008) [3] introduced the concept of the IP-graph of a naturally valenced association scheme. The common divisor graph of (G,X) is the IP-graph of the association scheme arising from the action of G on X. Xu (2009) [8] studied the properties of the IP-graph of an arbitrary naturally valenced association scheme, and generalized the main results in Isaacs and Praeger (1993) [5] and Camina (2008) [3]. In this paper we first prove that if the IP-graph of a naturally valenced association scheme (X,S) is stable and has two components (not including the trivial component whose only vertex is 1), then S has a closed subset T such that the thin residue O?(T) and the quotient scheme (X/O?(T),S//O?(T)) have very nice properties. Then for an association scheme (X,S) and a closed subset T of S such that S//T is an association scheme on X/T, we study the relations between the closed subsets of S and those of S//T. Applying these results to schurian schemes and common divisor graphs of groups, we obtain the results of Kaplan [6] as direct consequences.     

Reduction of Volume—preserving Flows on an n—dimensional Manifold

A geometric reduction procedure for volume-preserving flows with a volume-preserving symme-try on an n-dimensional manifold is obtained.Instead of the coordinate-dependent theory and the concrete coordinate transformation,we xhow that a volume-preserving flow with a one-parameter volume-preserving symmetry on an n-dimensional manifold can be reduced to a volume-preserving flow on the corresponding (n-1)-dimensional quotient space.More generally,if it admits an r-parameter volume-preserving commutable symmetry,then the reduced folw preserves the corresponding (n-r)-dimensional volume form.     

Some structure theory of table algebras and applications to association schemes

In this paper we prove some basic structure theorems for arbitrary table algebras. In particular, we prove a Krull–Schmidt theorem for arbitrary table algebras, and give applications to association schemes.     

Ideals of the cohomology rings of Hilbert schemes and their applications

We study the ideals of the rational cohomology ring of the Hilbert scheme of points on a smooth projective surface . As an application, for a large class of smooth quasi-projective surfaces , we show that every cup product structure constant of is independent of ; moreover, we obtain two sets of ring generators for the cohomology ring .

Similar results are established for the Chen-Ruan orbifold cohomology ring of the symmetric product. In particular, we prove a ring isomorphism between and for a large class of smooth quasi-projective surfaces with numerically trivial canonical class.

     

Volume-preserving flow by powers of the mth mean curvature

We consider the evolution of a closed convex hypersurface under a volume preserving curvature flow. The speed is given by a power of the mth mean curvature plus a volume preserving term, including the case of powers of the mean curvature or of the Gauss curvature. We prove that if the initial hypersurface satisfies a suitable pinching condition, the solution exists for all times and converges to a round sphere.     

Decompositions of trigonometric polynomials with applications to multivariate subdivision schemes

We study multivariate trigonometric polynomials satisfying the “sum-rule” conditions of a certain order. Based on the polyphase representation of these polynomials relative to a general dilation matrix, we develop a simple constructive method for a special type of decomposition of such polynomials. These decompositions are of interest in the analysis of convergence and smoothness of multivariate subdivision schemes associated with general dilation matrices. The approach presented in this paper leads directly to constructive algorithms, and is an alternative to the analysis of multivariate subdivision schemes in terms of the joint spectral radius of certain operators. Our convergence results apply to arbitrary dilation matrices, while the smoothness results are limited to two classes of dilation matrices.     

The arbitrary order implicit multistep schemes of exponential fitting and their applications

We develop the arbitrary order implicit multistep schemes of exponential fitting (EF) for systems of ordinary differential equations. We use an explicit EF scheme to predict an approximation, and then use an implicit EF scheme to correct this prediction. This combination is called a predictor–corrector EF method. We demonstrate the accuracy and efficiency of the new predictor–corrector methods via application to a variety of test cases and comparison with other analytical and numerical results. The numerical results show that the schemes are highly accurate and computationally efficient.     

Polynomial-time approximation schemes for piercing and covering with applications in wireless networks

Let be a set of disks of arbitrary radii in the plane, and let be a set of points. We study the following three problems: (i) Assuming contains the set of center points of disks in , find a minimum-cardinality subset of (if exists), such that each disk in is pierced by at least h points of , where h is a given constant. We call this problem minimum h-piercing. (ii) Assuming is such that for each there exists a point in whose distance from D's center is at most αr(D), where r(D) is D's radius and 0α<1 is a given constant, find a minimum-cardinality subset of , such that each disk in is pierced by at least one point of . We call this problem minimum discrete piercing with cores. (iii) Assuming is the set of center points of disks in , and that each covers at most l points of , where l is a constant, find a minimum-cardinality subset of , such that each point of is covered by at least one disk of . We call this problem minimum center covering. For each of these problems we present a constant-factor approximation algorithm (trivial for problem (iii)), followed by a polynomial-time approximation scheme. The polynomial-time approximation schemes are based on an adapted and extended version of Chan's [T.M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, J. Algorithms 46 (2003) 178–189] separator theorem. Our PTAS for problem (ii) enables one, in practical cases, to obtain a (1+ε)-approximation for minimum discrete piercing (i.e., for arbitrary ).