A novel idea for information security education created by the New York State Center for Information Forensics and Assurance (CIFA) is presented. This new approach incorporates a teaching hospital model originally developed for medical training. In this model, information security problems from industry and government are solved and abstracted into living-cases used for training and education of university students and public-sector employees. Such a model helps ensure that the curriculum stays current even as the field of information assurance continues to evolve. Solving industry problems hones research skills, while exposing students to living cases helps build context for concepts in information assurance. The success of this approach is contingent upon strong partnerships with government and private organizations that have real security issues as well as an active research program in information security that involves faculty and students. This article presents an implementation of this approach at CIFA. Development of the curriculum, observations gleaned through dissemination of the curriculum, and the infrastructure developed to support this concept are discussed. Evaluation of students has demonstrated the effectiveness of the “teaching hospital” concept and provided us with feedback to further refine its implementation.

We study the computational complexity of equivalence and minimization problems for expressions on many different lattices including each finite lattice and each distributive lattice. A general efficient expressibility condition C on a lattice is presented such that 1. The equivalence problem is co$NP$ hard for constant-free expressions on any lattice with at least two elements that satisfies condition C. Each finite or distributive lattice is shown to satisfy condition C. Moreover, if a lattice $\mathcal{L}$ satisfies condition C and $ \equiv $ is a congruence relation on $\mathcal{L}$, then ${\mathcal{L} / \equiv }$ also satisfies condition C. Several additional results are also presented. These results include the following: 2. In contrast to 1, the equivalence and operator minimization problems are solvable deterministically in polynomial time for disjunctive normal form and conjunctive normal form expressions on any lattice and for constant-free expressions on any free lattice with at least three generators: 3. Let $\mathcal{L}$ be a lattice. Then, the operator minimization problem and various approximate operator minimization problems for expressions on $\mathcal{L}$ are as hard as the problem of determining, for expressions F and G on $\mathcal{L}$, if $F \leqq G$.

The relationship between the setting in which an algebraic problem is posed and the complexity of solving the problem is considered.The problems stud~ed are equivalence, minimization, and approximate mimmlzatlon problems for formulas revolving variables, parentheses, operators, and (optionally) constants.General suffioent condmons on an algebraic structure Y for these problems to be NP-or coNP-hard are presented.Apphcations are gwen to a number of specific algebraic structures of independent interest including lattices, semirings, regular algebras, finite fields, rings 7/k, and Boolean nngs.Apphcations are also gwen to systems of rewrite rules and to several simple programming languages.

We present an algorithm which determines the shortest distances between all pairs of points in a nonnegatively weighted directed graph in average time $O(n^2 \log n\log ^ * n)$. This algorithm, which uses a search strategy similar to Dantzig [Management Sci., 2 (1960), pp. 187–190; Linear Programming and Extensions, Princeton Univ. Press, 1963] and Spira [SIAM J. Comput., 2 (1973), pp. 28–32] executes in the stated time over quite general classes of probability distributions on such graphs.

We present an algorithm which finds the shortest distance between all pairs of points in a non-negatively weighted directed graph in the average time stated in the title. This algorithm, an extension of Spira's solution [Sp], executes in the stated time over quite general classes of probability distributions on graphs.