An Optimal Multisecret Threshold Scheme Construction

A multisecret threshold scheme is a system which protects a number of secret keys among a group of n participants. There is a secret s_K associated with every subset K of k participants such that any t participants in K can reconstruct the secret s_K, but a subset of w participants cannot get any information about a secret they are not associated with. This paper gives a construction for the parameters t = 2, k = 3 and for any n and w that is optimal in the sense that participants hold the minimal amount of information. Communicated by: P. Wild     

Polynomial time approximation schemes for dense instances of minimum constraint satisfaction

It is known that large fragments of the class of dense Minimum Constraint Satisfaction (MIN‐CSP) problems do not have polynomial time approximation schemes (PTASs) contrary to their Maximum Constraint Satisfaction analogs. In this paper we prove, somewhat surprisingly, that the minimum satisfaction of dense instances of kSAT ‐formulas, and linear equations mod 2, Ek‐LIN2, do have PTASs for any k. The MIN‐Ek‐LIN2 problems are equivalent to the k‐ary versions of the Nearest Codeword problem, the problem which is known to be exceedingly hard to approximate on general instances. The method of solution of the above problems depends on the development of a new density sampling technique for k‐uniform hypergraphs which could be of independent interest. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 73–91, 2003     

Supervision of teachers based on adjusted arithmetic learning in special education

This article reports on 20 children's learning in arithmetic after teaching was adjusted to their conceptual development. The report covers periods from three months up to three terms in an ongoing intervention study of teachers and children in schools for the intellectually disabled and of remedial teaching in regular schools. The researcher classified each child's current counting scheme before and after each term. Recurrent supervision, aiming to facilitate the teachers’ modelling of their children's various conceptual levels and needs of learning, was conducted by the researcher. The teaching content in harmony with each child's ability was discussed with the teachers. This approach gives the teachers the opportunity to experience the children's own operational ways of solving problems. At the supervision meetings, the teachers theorized their practice together with the researcher, ending up with consistent models of the arithmetic of the child. So far, the children's and the teachers’ learning patterns are promising.     

A study of upstream-weighted high-order differencing for approximation to flow convection

This paper is concerned with a number of upstream-weighted second- and third-order difference schemes. Also considered are the conventional upwind and central difference schemes for comparison. It commences with a general difference equation which unifies all the given first-, second- and third-order schemes. The various schemes are evaluated through the use of the general equation. The unboundedness and accuracy of the solutions by the difference schemes are assessed via various analyses: examination of the coefficients of the difference equation, Taylor series truncation error analysis, study of the upstream connection to numerical diffusion, single-cell analysis. Finally, the difference schemes are tested on one- and two-dimensional model problems. It is shown that the high-order schemes suffer less from the problem of numerical diffusion than the first-order upwind difference scheme. However, unboundedness cannot be avoided in the solutions by these schemes. Among them the linear upwind difference scheme presents the best compromise between numerical diffusion and solution unboundedness.     

Efficient solutions schemes for interface problems

A computationally efficient two-level iterative scheme is proposed for the solution of the interface problems with Lagrange multipliers, where the oscillatory part of the solution is resolved by means off smoothing using a new, efficient preconditioner whereas the smooth component of the solution is captured by the collocation-based problem on the auxilliary grid, that is solved directly using a sparse direct solver. A simple adaptive feature is built into the proposed solution method in order to guarantee convergence for ill-conditioned problems. Nmerical results presented for example problems including that of a Boeing crown panel show that the proposed tww-level solution technique outperfrmsnce the standard, single level iterative and direect solvers.     

On Error Bounds for Approximation Schemes for Non-Convex Degenerate Elliptic Equations

In this paper we provide estimates of the rates of convergence of monotone approximation schemes for non-convex equations in one space-dimension. The equations under consideration are the degenerate elliptic Isaacs equations with x-depending coefficients, and the results applies in particular to certain finite difference methods and control schemes based on the dynamic programming principle. Recently, Krylov, Barles, and Jakobsen obtained similar estimates for convex Hamilton–Jacobi–Bellman equations in arbitrary space-dimensions. Our results are only valid in one space-dimension, but they are the first results of this type for non-convex second-order equations.     

Parallel computation of the flow of integral viscoelastic fluids on a heterogeneous network of workstations

We consider the parallel computation of flows of integral viscoelastic fluids on a heterogeneous network of workstations. The proposed methodology is relevant to computational mechanics problems which involve a compute-intensive treatment of internal variables (e.g. fibre suspension flow and deformation of viscoplastic solids). The main parallel computing issue in such applications is that of load balancing. Both static and dynamic allocation of work to processors are considered in the present paper. The proposed parallel algorithms have been implemented in an experimental, parallel version of the commercial POLYFLOW package developed in Louvain-la-Neuve. The implementation uses the public domain PVM software library (Parallel Virtual Machine), which we have extended in order to ease porting to heterogeneous networks. We describe parallel efficiency results obtained with three PVM configurations, involving up to seven workstations with maximum relative processing speeds of five. The physical problems are the stick/slip and abrupt contraction flows of a K.B.K.Z. integral fluid. Using static allocation, parallel efficiencies in the range 67%–85% were obtained on a PVM network with four workstations having relative speeds of 2:1:1:1. Parallel efficiencies higher than 90% were obtained on the three PVM configurations using the dynamic load-balancing schemes.     

XOR-based Visual Cryptography Schemes

A recent publication introduced a Visual Crypto (VC) system, based on the polarisation of light. This VC system has goodresolution, contrast and colour properties.Mathematically, the VC system is described by the XOR operation (modulo two addition). In this paper we investigate Threshold Visual Secret Sharing schemes associated to XOR-based VC systems. Firstly, we show that n out of n schemes with optimal resolution and contrast exist, and that (2,n) schemes are equivalent to binary codes. It turns out that these schemes have much better resolution than their OR-based counterparts. Secondly, we provide two explicit constructions for general k out of n schemes. Finally, we derive bounds on the contrast and resolution of XOR-based schemes. It follows from these bounds that for k<n, the contrast is strictly smaller than one. Moreover, the bounds imply that XOR-based k out of n schemes for even k are fundamentally different from those for odd k.AMS Classification: 94A60