In Eurocrypt 1994 we proposed a a new type of cryptographic scheme, which can decode concealed images without any cryptographic computations, by placing two transparencies on top of each other and using the decoder...
详细信息
In implementation verification, we check that an implementation is correct with respect to a specification by checking whether the behaviors of a transition system that models the program's implementation correlat...
详细信息
ISBN:
(纸本)3540631410
In implementation verification, we check that an implementation is correct with respect to a specification by checking whether the behaviors of a transition system that models the program's implementation correlate with the behaviors of a transition system that models its specification. In this paper, we investigate the effect of concurrency on the complexity of implementation verification. We consider trace-based and tree-based approaches to the verification of concurrent transition systems, with and without fairness. Our results show that in almost all cases the complexity of the problem is exponentially harder than that of the sequential case. Thus, as in the model-checking verification methodology, the state-explosion problem cannot be avoided.
In this paper we apply the method of complexity regularization to derive estimation bounds for nonlinear function estimation using a single hidden layer radial basis function network. Our approach differs from the pre...
详细信息
ISBN:
(纸本)0262100657
In this paper we apply the method of complexity regularization to derive estimation bounds for nonlinear function estimation using a single hidden layer radial basis function network. Our approach differs from the previous complexity regularization neural network function learning schemes in that we operate with random covering numbers and l1 metric entropy, making it possible to consider much broader families of activation functions, namely functions of bounded variation. Some constraints previously imposed on the network parameters are also eliminated this way. The network is trained by means of complexity regularization involving empirical risk minimization. Bounds on the expected risk in terms of the sample size are obtained for a large class of loss functions. Rates of convergence to the optimal loss are also derived.
This paper describes a method for finding the least fixed points of higher-order functions over finite domains using symbolic manipulation. Fixed point finding is an essential component in the calculation of abstract ...
This paper describes a method for finding the least fixed points of higher-order functions over finite domains using symbolic manipulation. Fixed point finding is an essential component in the calculation of abstract semantics of functional programs, providing the foundation for program analyses based on abstract interpretation. Previous methods for fixed point finding have primarily used semantic approaches, which often must traverse large portions of the semantic domain even for simple programs. This paper provides the theoretical framework for a syntax-based analysis that is potentially very fast. The proposed syntactic method is based on an augmented simply typed lambda calculus where the symbolic representation of each function produced in the fixed point iteration is transformed to a syntactic normal form. Normal forms resulting from successive iterations are then compared syntactically to determine their ordering in the semantic domain, and to decide whether a fixed point has been reached. We show the method to be sound, complete and compositional. Examples are presented to show how this method can be used to perform strictness analysis for higher-order functions over non-flat domains. Our method is compositional in the sense that the strictness property of an expression can be easily calculated from those of its sub-expressions. This is contrary to most strictness analysers, where the strictness property of an expression has to be computed anew whenever one of its subexpressions changes. We also compare our approach with recent developments in strictness analysis.
Problems associated with m-ary trees have been studied by computer scientists and combinatorialists. It is well known that a simple generalization of the Catalan numbers counts the number of m-ary trees on n nodes. In...
Problems associated with m-ary trees have been studied by computer scientists and combinatorialists. It is well known that a simple generalization of the Catalan numbers counts the number of m-ary trees on n nodes. In this paper we consider τm,n, the number of m-ary search trees on n keys, a quantity that arises in studying the space of m-ary search trees under the uniform probability model. We prove an exact formula for τm,n, both by analytic and by combinatorial means. We use uniform local approximations for sums of i.i.d. random variables to study the asymptotic development of τm,n for fixed m as n → ∞. † Research for the first author supported by NSF grant DMS-9311367. ‡ Research carried out while the second author was a Postdoctoral Research Associate at the National Institute of Standards and Technology.
Many distance learning systems claim to be interactive, but few can offer tow-way video, on-the-fly interaction, and application sharing. The authors describe the interactive remote instruction system, which links sit...
详细信息
Many distance learning systems claim to be interactive, but few can offer tow-way video, on-the-fly interaction, and application sharing. The authors describe the interactive remote instruction system, which links sites intranet.
We improve the existence results for holey self-orthogonal Latin squares with symmetric orthogonal mates (HSOLSSOMs) and show that the necessary conditions for the existence of a HSOLSSOM of typeh ...
We improve the existence results for holey self-orthogonal Latin squares with symmetric orthogonal mates (HSOLSSOMs) and show that the necessary conditions for the existence of a HSOLSSOM of typeh
n
are also sufficient with at most 28 pairs (h, n) of possible exceptions.
We investigate the number and size of the maximal sublattices of a finite lattice. For any positive integer k, there is a finite lattice L with more that |L|k sublattices. On the other hand, there are arbitrary large ...
We investigate the number and size of the maximal sublattices of a finite lattice. For any positive integer k, there is a finite lattice L with more that |L|k sublattices. On the other hand, there are arbitrary large finite lattices which contain a maximal sublattice with only 14 elements. It is shown that every finite bounded lattice is isomorphic to the Frattini sublattice (the intersection of all maximal sublattices) of a finite bounded lattice.
Although platform-independent runtime systems for parallel programming languages are desirable, the need for low-level optimizations usually precludes their existence. This is because most optimizations involve some c...
详细信息
Although platform-independent runtime systems for parallel programming languages are desirable, the need for low-level optimizations usually precludes their existence. This is because most optimizations involve some combination of low-level communication and low-level threading the product of which is almost always platform-dependent. We propose a solution to the threading half of this dilemma by using a thread package, that allows fine-grain control over the behaviour of the threads while still providing performance comparable to hand-tuned, machine-dependent thread packages. This makes it possible to construct platform-independent thread modules for parallel runtime systems and, more importantly, to optimize them.
暂无评论