Algebraic properties of cryptosystem PGM

In the late 1970s Magliveras invented a private-key cryptographic system calledPermutation Group Mappings (PGM). PGM is based on the prolific existence of certain kinds of factorization sets, calledlogarithmic signatures, for finite permutation groups. PGM is an endomorphic system with message space ℤ_|G| for a given finite permutation groupG. In this paper we prove several algebraic properties of PGM. We show that the set of PGM transformations ℐ _G is not closed under functional composition and hence not a group. This set is 2-transitive on ℤ_|G| if the underlying groupG is not hamiltonian and not abelian. Moreover, if the order ofG is not a power of 2, then the set of transformations contains an odd permutation. An important consequence of these results is that the group generated by the set of transformations is nearly always the symmetric group ℒ_|G|. Thus, allowing multiple encryption, any permutation of the message space is attainable. This property is one of the strongest security conditions that can be offered by a private-key encryption system. S. S. Magliveras was supported in part by NSF/NSA Grant Number MDA904-82-H0001, by U.S. West Communications, and by the Center for Communication and Information Science of the University of Nebraska.     

Modeling of in situ monitored laser reflectance during MOCVD growth of HgCdTe

An effective way to in situ monitor the metalorganic chemical vapor deposition (MOCVD) of HgCdTe/CdTe/ZnTe on GaAs or GaAs/Si substrates is presented. Specular He-Ne laser reflectance was used to in situ monitor the growth rates, layer thickness, and morphology for each layer in the grown multilayer structure. In situ monitoring has enabled precise measurements of ZnTe nucleation and CdTe buffer layer thicknesses. Monitoring the constancy of reflectance during the thicker CdTe buffer growth where absorption in the CdTe reduces reflectance to just the surface component has led to optimum buffer growth ensuring good quality of subsequently grown HgCdTe. During the interdiffused multilayer process (IMP) HgCdTe growth, because multiple interfaces are present within the absorption length, a periodic reflectance signal is maintained throughout this growth cycle. A theoretical model was developed to extract IMP layer thicknesses from in situ recorded experimental data. For structures that required the growth of a larger band gap HgCdTe cap layer on top of a smaller band gap active layer, in situ monitored reflectance data allowed determination of alloy composition in the cap layer as well. Continuous monitoring of IMP parameters established the stability of growth conditions, translating into depth uniformity of the grown material, and allowed diagnosis of growth rate instabilities in terms of changes in the HgTe and CdTe parts of the IMP cycle. A unique advantage of in situ laser monitoring is the opportunity to perform “interactive” crystal growth, a development that is a key to real time MOCVD HgCdTe feedback growth control.     

Avoiding linear dependencies in LFSR test pattern generators

Linear Feedback Shift Registers (LFSRs) constitute a very efficient mechanism for generating pseudoexhaustive or pseudo-random test sets for the built-in self-testing of digital circuits. However, a well-known problem with the use of LFSRs is the occurrence of linear dependencies in the generated patterns. In this paper, we show for the first time that the amount of linear dependencies can be controlled by selecting appropriate characteristic polynomials and reordering the LFSR cells. We identify two classes of such polynomials which, by appropriate LFSR cell ordering, guarantee that a large ratio of linear dependencies cannot occur. Experimental results show significant enhancements on the fault coverage for pseudo-random testing and support the theoretical relation between minimization of linear dependencies and effective fault coverage.This work was partially supported by NSF grant MIP-9409905, a 1993–94 ACM/IEEE Design Automation Scholarship and a grant from Nissan Corporation. A preliminary version of this work appeared in A Class of Good Characteristic Polynomials for LFSR Test Pattern Generators, in Proc. of IEEE International Conference on Computer Design, Oct. 1994, pp. 292–295, where it received the ICCD'94 Best Paper Award.     

Randomized priority algorithms

Borodin, Nielsen and Rackoff [13] introduced the class of priority algorithms as a framework for modeling deterministic greedy-like algorithms. In this paper we address the effect of randomization in greedy-like algorithms. More specifically, we consider approximation ratios within the context of randomized priority algorithms. As case studies, we prove inapproximation results for two well-studied optimization problems, namely facility location and makespan scheduling.     

Efficient PAC Learning for Episodic Tasks with Acyclic State Spaces

This paper considers the problem of computing an optimal policy for a Markov decision process, under lack of complete a priori knowledge of (1) the branching probability distributions determining the evolution of the process state upon the execution of the different actions, and (2) the probability distributions characterizing the immediate rewards returned by the environment as a result of the execution of these actions at different states of the process. In addition, it is assumed that the underlying process evolves in a repetitive, episodic manner, with each episode starting from a well-defined initial state and evolving over an acyclic state space. A novel efficient algorithm for this problem is proposed, and its convergence properties and computational complexity are rigorously characterized in the formal framework of computational learning theory. Furthermore, in the process of deriving the aforementioned results, the presented work generalizes Bechhofer’s “indifference-zone” approach for the ranking & selection problem, that arises in statistical inference theory, so that it applies to populations with bounded general distributions.

On the Optimality of Randomized Deadlock Avoidance Policies

This paper revisits the problem of selecting an optimal deadlock resolution strategy, when the selection criterion is the maximization of the system throughput, and the system is Markovian in terms of its timing and routing characteristics. This problem was recently addressed in some of our previous work, that (i) provided an analytical formulation for it, (ii) introduced the notion of randomized deadlock avoidance as a generalization of the more traditional approaches of deadlock prevention/avoidance, and detection and recovery, and (iii) provided a methodology for selecting the optimal randomized deadlock avoidance policy for a given resource allocation system (RAS) configuration. An issue that remained open in the problem treatment of that past work, was whether the proposed policy randomization is essential, i.e., whether there exist any RAS configurations for which a randomized deadlock avoidance policy is superior to any other policy that does not employ randomization. The work presented in this paper establishes that for the basic problem formulation where the only concern is the (unconstrained) maximization of the system throughput—or the other typical performance objectives of minimizing the system work-in-process and mean sojourn time—randomization of the deadlock resolution strategy is not essential. However, it is also shown that, sometimes, it can offer an effective mechanism for accommodating additional operational constraints, like the requirement for production according to a specified product mix. Furthermore, the undertaken analysis provides an analytical characterization of the dependence of the aforementioned performance measures on the transition rates relating to the various events of the underlying state space, which can be useful for the broader problem of synthesizing efficient scheduling policies for the considered class of resource allocation systems.     

Wave-generated fractures in river ice covers

The breakup of the ice cover in northern rivers is a brief but crucial event in the life cycle of many aquatic species and can trigger extreme ice jam events with major socio-economic impacts and significant climate change implications. An important, but vaguely understood, breakup process is the fracture of the winter ice cover by low-amplitude water waves. Previous work on this subject has been based on the assumption of an infinitely long wave propagating under an infinitely long and “edgeless” ice cover. This configuration does not account for structural constraints imposed by the proximity of an ice edge or a transverse crack. Consequently, it only furnishes approximate values of bending stresses, and tells little about the spacing of cracks that may be generated by an advancing wave, which is the only visual evidence that can identify the relevant fracture mechanism in the field. Herein, edge proximity is taken into account by making plausible simplifications to the ice response equation, and using wave forms of limited extent. It is shown that such conditions generally produce higher bending stresses than does the infinite wave/edgeless cover configuration. The distance of the peak bending stress from the edge, which defines the spacing of cracks, varies with wavelength and is less than 100 ice thicknesses or so. This is comparable to that of high-amplitude, single waves (or surges) that result from ice jam releases, but much less than fractures generated by bending on horizontal planes, caused by the meandering river plan form. Comparison of the present results with the limited available evidence indicates that wave-generated fractures occur during the passage of ice jam release surges.     

Hierarchical control approach to a composite inventory-marketing problem

A composite inventory-marketing problem is considered and treated for the case where there exist distributed time delays in the supply and/or the advertisement process, as well as product losses at constant rates. Since in a real large-scale situation a centralized solution may be impractical, two hierarchical coordinated control algorithms are presented which are based on a proper decomposition of the overall problem. Backlogging is not permitted and the delays are assumed fixed and known. The first algorithm makes use of the dual optimization technique, whereas the second algorithm is based on a decentralized procedure which allows each of the company's departments to solve its problem individually, and then with the coordination of an upper level to obtain the overall solution. Numerical examples are included which illustrate the effectiveness of the two algorithms.