Improved Schemes for Visual Cryptography

A (k,n)-threshold visual cryptography scheme ((k,n)-threshold VCS, for short) is a method to encode a secret image SI into n shadow images called shares such that any k or more shares enable the visual recovery of the secret image, but by inspecting less than k shares one cannot gain any information on the secret image. The visual recovery consists of xeroxing the shares onto transparencies, and then stacking them. Any k shares will reveal the secret image without any cryptographic computation.In this paper we analyze visual cryptography schemes in which the reconstruction of black pixels is perfect, that is, all the subpixels associated to a black pixel are black. For any value of k and n, where 2 k n, we give a construction for (k,n)-threshold VCS which improves on the best previously known constructions with respect to the pixel expansion (i.e., the number of subpixels each pixel of the original image is encoded into). We also provide a construction for coloured (2,n)-threshold VCS and for coloured (n,n)-threshold VCS. Both constructions improve on the best previously known constructions with respect to the pixel expansion.     

On (k,n)*-visual cryptography scheme

Let P = {1, 2, . . . , n} be a set of elements called participants. In this paper we construct a visual cryptography scheme (VCS) for the strong access structure specified by the set Γ₀ of all minimal qualified sets, where ${\Gamma_0=\{S: S\subseteq P, 1\in S}$ and |S| = k}. Any VCS for this strong access structure is called a (k, n)*-VCS. We also obtain bounds for the optimal pixel expansion and optimal relative contrast for a (k, n)*-VCS.     

Linear algebraic techniques to construct monochrome visual cryptographic schemes for general access structure and its applications to color images

Though the monochrome (black and white) visual cryptography has a very rich literature, a very few papers have been published for the construction of general access structure. In this paper we put forward a method of construction of a strong monochrome visual cryptographic scheme (VCS) for general access structure using linear algebra. As a particular case of general access structure, \((k,n)\) -VCS for \(2 \le k \le n\) is obtained. The \((n,n)\) -VCS obtained from the scheme attains the optimal pixel expansion as well as optimal relative contrast. We provide an efficient construction of \((n-1,n)\) -VCS. We further extend our monochrome VCS to color VCS for restricted access structures. Finally, we provide some interesting examples that will lead to some future research directions in the area of VCS.     

Quotient Complexes and Lexicographic Shellability

Let _n,k,k and _n,k,h , h < k, denote the intersection lattices of the k-equal subspace arrangement of type _n and the k,h-equal subspace arrangement of type _n respectively. Denote by the group of signed permutations. We show that ( _n,k,k )/ is collapsible. For ( _n,k,h )/ , h < k, we show the following. If n 0 (mod k), then it is homotopy equivalent to a sphere of dimension . If n h (mod k), then it is homotopy equivalent to a sphere of dimension . Otherwise, it is contractible. Immediate consequences for the multiplicity of the trivial characters in the representations of on the homology groups of ( _n,k,k ) and ( _n,k,h ) are stated.The collapsibility of ( _n,k,k )/ is established using a discrete Morse function. The same method is used to show that ( _n,k,h )/ , h < k, is homotopy equivalent to a certain subcomplex. The homotopy type of this subcomplex is calculated by showing that it is shellable. To do this, we are led to introduce a lexicographic shelling condition for balanced cell complexes of boolean type. This extends to the non-pure case work of P. Hersh (Preprint, 2001) and specializes to the CL-shellability of A. Björner and M. Wachs (Trans. Amer. Math. Soc. 4 (1996), 1299–1327) when the cell complex is an order complex of a poset.     

Best “Continuous” n-Term Approximations in the Spaces $$S_\phi ^p $$

We find exact values of upper bounds for the best approximations of q-ellipsoids by polynomials of degree n in the spaces in the case where the approximating polynomials are constructed on the basis of n-dimensional subsystems chosen successively from a given orthonormal system .     

Construction of a (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">n</Emphasis>)-visual cryptography scheme

In this paper we give an explicit construction of basis matrices for a (k, n)-visual cryptography scheme \((k,n){\hbox {-}}\mathrm{VCS}\) for integers k and n with \(2\le k \le n\). In balanced VCS every set of participants with equal cardinality has same relative contrast. The VCS constructed in this paper is a balanced \((k,n){\hbox {-}}\mathrm{VCS}\) for general k. Also we obtain a formula for pixel expansion and relative contrast. We also prove that our construction gives optimal contrast and minimum pixel expansion when \(k=n\) and \(n-1\).     

Hypersurfaces of restricted type in Minkowski space

A submanifold M _n ^r of Minkowski space is said to be of restricted type if its shape operator with respect to the mean curvature vector is the restriction of a fixed linear transformation of to the tangent space of M _n ^r at every point of M _n ^r . In this paper we completely classify hypersurfaces of restricted type in . More precisely, we prove that a hypersurface of is of restricted type if and only if it is either a minimal hypersurface, or an open part of one of the following hypersurfaces: S ^k × , S _k ¹ × , H ^k × , S _n ¹ , H ⁿ , with 1kn–1, or an open part of a cylinder on a plane curve of restricted type.This work was done when the first and fourth authors were visiting Michigan State University.Aangesteld Navorser N.F.W.O., Belgium.     

On the Hellinger type distances for filtered experiments

Summary We study the Hellinger type distances on a filtered space. Herep2 is an arbitrary number andP _T and are two probability measures stopped at a random timeT. We give lower and upper bounds for in predictable terms.     

On the Number of Subgraphs of a Specified Form Embedded in a Random Graph

Let U ₁, U ₂,... be a sequence of i.i.d. random elements in R^d. For x>0, a graph G _n (x) may be formed by connecting with an edge each pair of points in that are separated by a distance no greater than x. The points of G _n (x) could represent the stations in a telecommunications network and the edge set the lines of communication that exist among them. Let be a collection of graphs on mn points having a specified form or structure, and let denote the number of subgraphs embedded in G _n (x) and contained in . It is shown that a SLLN, CLT and LIL for follow easily from the theory of U-statistics. In addition, a uniform (in x) SLLN is proved for collections that satisfy a certain monotonicity condition. Some applications are mentioned and the results of some simulations presented. The scaling constants appearing in the CLT are usually hard to obtain. These are worked out for some special cases.     

On the isomorphisms and automorphism groups of circulants

Denote byC _n(S) the circulant graph (or digraph). LetM be a minimal generating element subset ofZ _n, the cyclic group of integers modulon, and In this paper, we discuss the problems about the automorphism group and isomorphisms ofC _n(S). When M S , we determine the automorphism group ofC _n(S) and prove that for any T if and only ifT = S, where is an integer relatively prime ton. The automorphism groups and isomorphisms of some other types of circulant graphs (or digraphs) are also considered. In the last section of this paper, we give a relation between the isomorphisms and the automorphism groups of circulants.     

Counting the number of isotone selfmappings of crowns

Letn>1. The number of all strictly increasing selfmappings of a 2n-element crown is . The number of all order-preserving selfmappings of a 2n-element crown is

On (q 2 + q + 2, q + 2)-arcs in the Projective Plane PG(2, q)

A (k,n)-arc in PG(2,q) is usually defined to be a set of k points in the plane such that some line meets in n points but such that no line meets in more than n points. There is an extensive literature on the topic of (k,n)-arcs. Here we keep the same definition but allow to be a multiset, that is, permit to contain multiple points. The case k=q ²+q+2 is of interest because it is the first value of k for which a (k,n)-arc must be a multiset. The problem of classifying (q ²+q+2,q+2)-arcs is of importance in coding theory, since it is equivalent to classifying 3-dimensional q-ary error-correcting codes of length q ²+q+2 and minimum distance q ². Indeed, it was the coding theory problem which provided the initial motivation for our study. It turns out that such arcs are surprisingly rich in geometric structure. Here we construct several families of (q ²+q+2,q+2)-arcs as well as obtain some bounds and non-existence results. A complete classification of such arcs seems to be a difficult problem.     

A Note on Extremes of Concomitants of Order Statistics

Let be a sequence of identically distributed variables. We study the asymptotic distribution of , where Y _[r:n] denotes the concomitant of the rth order statistic X _r:n , corresponding to , and is held fixed while . Conditions are given for the and to have the same asymptotic behavior as that we would apply if were i.i.d. The result is illustrated with a simple linear regression model , where is a stationary sequence with extremal index .     

The type set for some measures on \mathbb{R}^{2n} with n-dimensional support

Let be realhomogeneous functions in ofdegree and let bethe Borel measure on given by

The Intrinsic Enumerability of Linear Orders

We study into the question of which linearly ordered sets are intrinsically enumerable. In particular, it is proved that every countable ordinal lacks this property. To do this, we state a criterion for hereditarily finite admissible sets being existentially equivalent, which is interesting in its own right. Previously, Yu. L. Ershov presented the criterion for elements h ₀ , h ₁ in HF ) to realize a same type as applied to sufficiently saturated models . Incidentally, that criterion fits with every model on the condition that we limit ourselves to 1-types.     

Regular Unitarily Invariant Spaces on the Complex Sphere

Let K be a compact space, let X be a closed subspace of C(K), and let be a positive measure on K. The triple is said to be regular if, for any positive function and for any , there exists a function such that on K and . The case where K is the unit sphere in and the subspace X is invariant with respect to the unitary group is investigated. Sufficient spectral conditions and a necessary condition for the regularity of a triple are obtained. Connections with compactness of certain Hankel operators and applications to interpolation problems are presented. Bibliography: 16 titles.     

On the convergence rate of imperfect minimization algorithms in Broyden'sβ-class

This paper presents a local convergence analysis of Broyden's class of rank-2 algorithms for solving unconstrained minimization problems, ,h C¹(R ⁿ ), assuming that the step-size ai in each iterationx _i+1 =x _i - _i H _i h(x _i ) is determined by approximate line searches only. Many of these methods including the ones most often used in practice, converge locally at least with R-order, .     

On Singular Functional Differential Inequalities

Classical theorems on differential inequalities [1, 2, 3] are generalized for initial value problems of the kind and where is a singular Volterra operator, is continuous and positive on ]a, b], is a norm in R ⁿ, and [u]₊ and [u]_– are respectively the positive and the negative part of the vector u R ⁿ.     

Auxiliary Problem Principle and Proximal Point Methods

An extension of the auxiliary problem principle to variational inequalities with non-symmetric multi-valued operators in Hilbert spaces is studied. This extension concerns the case that the operator is split into the sum of a single-valued operator , possessing a kind of pseudo Dunn property, and a maximal monotone operator . The current auxiliary problem is k constructed by fixing at the previous iterate, whereas (or its single-valued approximation ^k) k is considered at a variable point. Using auxiliary operators of the form ^k+ , with _k>0, the standard for the auxiliary problem principle assumption of the strong convexity of the function h can be weakened exploiting mutual properties of and h. Convergence of the general scheme is analyzed and some applications are sketched briefly.     

Die konvexe Hülle von n rotationssymmetrisch verteilten Punkten

Summary The number of edges A _n , the length l _n and the surface F _n of the convex hull of n independent, identically distributed random points in the plane are considered under the assumption of rotational symmetry. The asymptotic behaviour of the expectations E(A _n ), E(l _n ) and E(F _n ) is studied according to the behaviour of the function Pr( as x 1 (distributions on the unit disc) or x (distributions on the whole plane).

---

---

Herrn Prof. H. Hadwiger zu seinem 60. Geburtstag gewidmet.