Below are our technical reports which are viewable through the web. The catalogue file contains the same information seen here, plus some reports not available via FTP.

You may also view a Postscript file of the abstracts of the latest papers or see a menu for all abstracts.

NYU Department of Computer Science Technical Reports

A. Gottlieb, "An Overview of the NYU Ultracomputer Project (Revised)", Oct. 1987

G. Landau, U. Vishkin, "Efficient Parallel and Serial Approximate String Matching", Feb. 1986

Y. Maon, B. Schieber, U. Vishkin, "Parallel Ear Decomposition Search (EDS) and ST-Numbering in Graphs", Feb. 1986

Y. Azar, U. Vishkin, "Tight Comparison Bounds on the Complexity of Parallel Sorting", Feb. 1986

R. Cole, U. Vishkin, "The Accelerated Centroid Decomposition Technique for Optimal Parallel Tree Evaluation in Logarithmic Time", Sep. 1986

R. Cole, C. O'Dunlaing, "Note on the AKS Sorting Network", Sep. 1986

D. Szyld, O. Widlund, "Variational Analysis of Some Conjugate Gradient Methods", Dec. 1989

M. Dryja, O. Widlund, "Towards a Unified Theory of Domain Decomposition Algorithms for Elliptic Problems", Dec. 1989

D. Rennels, E. Schonberg, "A Program Analysis Tool for Evaluating the ADA Compiler Validation Suite", Jan. 1990

K. Donovan, "Performance of Shared Memory in a Parallel Computer", Mar. 1990

V. Lanin, D. Shasha, "Tree Locking on Changing Trees", Apr. 1990

M. Pellegrini, "Stabbing and Ray Shooting in 3-Dimensional Space", May 1990

tr505 M. Overton, "Large-Scale Optimization of Eigenvalues", May 1990

X. Cai, O. Widlund, "Domain Decomposition Algorithms for Indefinite Elliptic Problems", May 1990

M. Dryja, O. Widlund, "Multilevel Additive Methods for Elliptic Finite Element Problems", May 1990

S. Cox, M. Overton, "On the Optimal Design of Columns Against Buckling", June 1990

R. Cole, "Tight Bounds on the Complexity of the Boyer-Moore Pattern Matching Algorithm", June 1990

D. Shasha, J. Turek, "Beyond Fail-Stop: Wait-Free Serializability and Resiliency in the Presence of Slow-Down Failures", Sep. 1990

B. Smith, "Domain Decomposition Algorithms for the Partial Differential Equations of Linear Elasticity", Sep. 1990

K. Li, "Dag Representation and Optimization of Rewriting", Sep. 1990

B. Smith, "A Domain Decomposition Algorithm for Elliptic Problems in Three Dimensions", Oct. 1990

J. Burke, "Stable Perturbations of Nonsymmetric", Oct. 1990

P. Ouyang, "Execution of Regular DO Loops on Asynchronous Multiprocessors", Oct. 1990

M. Dryja, "Substructuring Methods for Parabolic Problems", Nov. 1990

W. Jockush, N. Prabhu, "Cutting a Polytope", Nov. 1990

G. Bohus, W. Jockush, C. Lee, N. Prabhu, "On Triangulations of the 3-Ball and the Solid Torus", Nov. 1990

N. Prabhu, "On a Conjecture of Micha Perles", Nov. 1990

E. Davis, "Physical Idealization as Plausible Inference", Nov. 1990

R. Cole, O. Zajicek, "The APRAM - The Rounds Complexity Measure and the Explicit Costs of Synchronization", Jan. 1991

E. Davis, "The Kinematics of Cutting Solid Objects", Jan. 1991

R. Cytron, J. Lipkis, E. Schonberg, "A Compiler-Assisted Approach to SPMD Execution", Jul. 1990

R. Cole, O. Zajicek, "An Asynchronous Parallel Algorithm for Undirected Graph Connectivity", Feb. 1991

G. Gallo, B. Mishra, "Some Constructions in Rings of Differential Polynomials", Mar. 1991

K. L. Clarkson, R. Cole, R. E. Tarjan, "Randomized Parallel Algorithms for Trapezoidal Diagrams", Mar. 1991

S. Mallat, W. L. Hwang, "Singularity Detection and Processing with Wavelets", Mar. 1991

tr552 Part 1 Part 2 Part 3 Part 4 Part 5
P. Charles, "A Practical Method for Constructing Efficient LALR(k) Parsers with automatic Error Recovery", Mar. 1991

I. Rigoutsos, R. Hummel, "Scalable Parallel Geometric Hashing for Hypercube SIMD Architechtures", Jan. 1991

I. Rgoutsos, R. Hummel, "On a Parallel Implementation of Geometric Hashing on the Connection Machine", Apr. 1991

K. Laufer, "Comparing Three Approaches to Transformational Programming", Apr. 1991

F. Henglein, K. Laufer, "Programming with Structures, Functions, and Objects", Apr. 1991

R. Cole, U. Vishkin, "On the Detection of Robust Curves", Apr. 1991

G. Koren, B. Mishra, A. Raghunathan, D. Shasha, "On-Line Schedulers for Overloaded Real-Time Systems", May 1991

R. Sundar, "Amortized Complexity of Data Structures", May 1991

S. Nepomnyaschikh, "Decomposition and Fictitious Domains Methods for Elliptic Boundary Value Problems", May 1991

E. Davis, "Lucid Representations", June 1991

M. Overton, R. Womersley, "Optimality Conditions and Duality Theory for Minimizing Sums of the Largest Eigenvalues of Symmetric Matrices", June 1991

J. Burke, M. Overton, "On the Subdifferentiability of a Matrix Spectrum I: Mathematical Foundations", June 1991

J. Burke, M. Overton, "On the Subdifferentiability of a Matrix Spectrum II: Subdifferential Formulas", June 1991

P. Tetali, "Applications and Analysis of Probabilistic Techniques", June 1991

M. Dryja, O. Widlund, "Additive Schwarz Methods for Elliptic Finite Element Problems in Three Dimensions", June 1991

F. Gasperoni, U. Schwiegelshohn, "Efficient Algorithms for Cyclic Scheduling", July 1991

G. Koren, D. Shasha, "An Optimal Scheduling Algorithm with a Competitive Factor for Real-Time Systems", July 1991

R. Cole, A. Raghunathan, "Online Algorithms for Finger Searching", Aug. 1991

R. Cole, O. Zajicek, "The Expected Advantage of Asynchrony", Sep. 1991

J. Burke, M. Overton, "Differential Properties of Eigenvalues", Sep. 1991

L. Pavarino, "An Additive Schwarz Method for the P-Version Finite Element Method", Sep. 1991

O. Widlund, "Some Schwarz Methods for Symmetric and Nonsymmetric Elliptic Problems", Sep. 1991

X. Zhang, "Multilevel Additive Schwarz Methods", Sep. 1991

X. Zhang, "Domain Decomposition Algorithms for the Biharmonic Dirichlet Problem", Sep. 1991

X. Zhang, "Studies in Domain Decomoposition: Multilevel Methods and the Biharmonic Dirichlet Problem", Sep. 1991

M. Hind, "Efficient Loop-Level Parallelishm in ADA", Sep. 1991

J. Haeberly, "On Shape Optimizing the Ratio of the First Two Eigenvalues of the Laplacian", Oct. 1991

C. Chang, R. Paige, "New Theoretical and Computational Results for Regular Languages", Oct. 1991

B. Bederson, R. Wallace, E. Schwartz, "A Miniaturized Active Vision System", Nov. 1991

R. Wallace, P. Ong, B. Bederson, E. Schwartz, "Space Variant Image Processing", Nov. 1991

E. Davis, "Axiomating Qualitative Process Theory", Nov. 1991

X.-C. Cai, O. Widlund, "Multiplicative Schwarz Algorithms for Some Nonsymmetric and Indefinite Problems", Feb. 1992

G. Park, "Semantic Analyses for Storage Management Optimizations in Functional Language Implementations", Feb. 1992

B. Bederson, R. Wallace, E. Schwartz, "A Miniature Pan-Tilt Actuator: The Sperical Pointing Motor", Apr. 1992

J. Cai, X. Han, R. Tarjan, "An $O(m$log$n)$-Time Algorithm for the Maximal Planar Subgraph Problem", Apr. 1992

J. Cai, "Counting Embeddings of Planar Graphs Using DFS Trees", Apr. 1992

J. Cai, R. Paige, R. Tajan, "More Efficient Bottom-Up Mult-Pattern Matching in Trees", Apr. 1992

M. Dryja, O. Widlund, "Domain Decomposition Algorithms with Small Overlap", May 1992

A. Greenbaum, L. Trefethen, "GMRES/CR and Arnoldi/Lanczos as Matrix Approximation Problems", May 1992

A. Greenbaum, Z. Strakos, "Matrices that Generate the Same Krylov Residual Spaces", May 1992

J. Cai, R. Paige, "Multiset Discrimination - A Method for Implementing Programming Language Systems without Hashing", June 1992

V. Averbukh, S. Figueroa, T. Schlick, "HESFCN - A Fortran package of Hessian Subroutines for Testing Nonlinear Optimization Software", June 1992

tr611-R266 Part 1 Part 2
B. Bederson, "Miniature Space-Variant Active Vision System: Cortex-I", July 1992

D. Karron, J. Cox, B. Mishra, "The Spiderweb Algorithm for Surface Construction from Medical Volume Data: Geometric Properties of its Surface", July 1992

L. Pavarino, "Some Schwarz Algorithms for the P-Version Finite Element Method", Sep. 1992

M. Dryja, O. Widlund, "Some Recent Results on Schwarz Type Domain Decomposition Algorithms", Sep. 1992

L. Pavarino, "Domain Decomposition Algorithms for the P-Version Finite Element Method for Elliptic Problems", Sep. 1992

S. Mallat, Z. Zhang, "Matching Pursuits with Time-Frequency Dictionaries", Rev. Aug. 1993

T.-R. Chuang, B. Goldberg, "Backward Analysis for Higher-Order Functions Using Inverse Images", Nov. 1992

F. Tsai, "Statistical Approach to Affine Invariant Matching with Line Features", Nov. 1992

tr622 Part 1 Part 2
K. Laufer, "Polymorphic Type Inference and Abstract Data Types", Dec. 1992

J. Cullum, A. Greenbaum, "Residual Relationships within Three Pairs of Iterative Algorithms for Solving $Ax - b$", Feb. 1993

J. Haeberly, M. Overton, "A Hybrid Algorithm for Optimizing Eigenvalues of Symmetric Definite Pencils", Feb. 1993

F. Tsai, "Using Line Invariants for Object Recognition by Geometric Hasing", Feb. 1993

M. Dryja, O. Widlund, "Schwarz Methods of Neumann-Neumann Type for Three-Dimensional Elliptic Finite Element Problems", Mar. 1993

M. Overton, R. Womersly, "Second Derivatives for Optimizing Eigenvalues of Symmetric Matrices", Mar. 1993

G. Gallo, B. Mishra, "The Complexity of Resolvent Resolved", Mar. 1993

M. Sarkis, "Two-Level Schwarz Methods for Nonconforming Finite Elements and Discontinuous Coefficients", Mar. 1993

P. Agarwal, "The Cell Programming Language", Mar. 1993

M. Overton, X. Ye, "Towards Second-Order Methods for Structured Nonsmooth Optimization", Apr. 1993

Mutukrishnan, K. Palem, "Highly Efficient Dictionary Matching in Parallel", Apr. 1993

R. Wallace, P. Ong, B. Bederson, E. Schwartz, "Space Variant Image Processing", Apr. 1993

R. Wallace, "Miniature Direct-Drive Rotary Actuators", Apr. 1993

J. Cai, "A Language for Semantic Analysis", May 1993

R. Wallace, B. Bederson, E. Schwartz, "Voice-Bandwidth Visual Communication Through Logmaps: The Telecortex", May 1993

E. Davis, "Knowledge Preconditions for Plans", May 1993

M. Dryja, B. Smith, O. Widlund, "Schwarz Analysis of Iterative Substructuring Algorithms for Elliptic Problems in Three Dimensions", May 1993

G. Koren, D. Shasha, "Competitive Algorithms and Lower Bounds for On-Line Scheduling of Multiprocessor Real-Time Systems", June 1993

F. Tsai, "A Probabilistic Approach to Geometric Hashing Using Line Features", June 1993

W. Hwang, S. Mallat, "Chacterization of Self-Similar with Wavelet Maxima", Aug. 1993

B. Mishra, M. Antoniotti, "ED I: NYU Educational Robot Design and Evaluation", Aug. 1993

tr644 Part 1 Part 2 Part 3
T.-R. Chuang, "New Techniques for the Analysis and Implementation of Functional Programs", Aug. 1993

A. Greenbaum, "Norms of Functions of Matrices", Aug. 1993

B. Mishra, "Bidirectional Edges Problem, Part I: A Simple Algorithm", Sep. 1993

B. Mishra, "Bidirectional Edges Problem, Part II: An Efficient Algorithm", Sep. 1993

L. Pavarino, O. Widlund, "Iterative Substructuring Methods for Spectral Elements in Three Dimensions", Sep. 1993

B. Mishra, "A Survey of Computational Differential Algebra", Oct. 1993

R. Wallace, "Miniature Direct Drive Rotary Actuators II: Eye, Finger, and Leg", Nov. 1993

D. Max, R. Wallace, "Feedback Control of Miniature Direct Drive Devices", Nov. 1993

B. Mishra, M. Antoniotti, F. Hansen, R. Wallace, "NYU Educational Robotics Project: A Pedagogic Overview", Nov. 1993

H. Chen, "Multilevel Schwarz Methods with Partial Refinement", Mar. 1994

C. Yao, B. Goldberg, "Pscheme: Extending Continuations to Express Control and Synchronization in a Parallel LISP", Mar. 1994

G. Davis, S. Mallat, Z. Zhang, "Adaptive Time-Frequency Approximations with Matching Pursuits", Mar. 1994

tr658 Figures
J. Maddocks, M. Overton, "Stability Theory for Dissipatively Perturbed Hamiltonian Systems", Mar. 1994

F. Alizadeh, J. P. Haeberly, M. Overton, "A New Primal-Dual Interior-Point Method for Semidefinite Programming", Mar. 1994

J. P. Haeberly, M. Overton, "Optimizing Eigenvalues of Symmetric Definite Pencils", Mar. 1994

L. Pavarino, O. Widlund, "A Polylogarithmic Bound for an Iterative Substructuring Method for Spectral Elements in Three Dimensions", Mar. 1994

M. Dryja, M. Sarkis, O. Widlund, "Multilevel Schwarz Methods for Elliptic Problems with Discontinuous Coefficients in Three Dimensions", Mar. 1994

L. Pavarino, O. Widlund, "Iterative Substructuring Methods for Spectral Elements: Problems in Three Dimensions Based on Numerical Quadrature", May 1994

M. Antoniotti, "Conceptual and Pragmatic Tools for Design and Control of Manufacturing Systems (Petrinets and Ramadge-Wonham Discrete Event Systems)"

S. Gomory, R. Wallace, "Cursor Stereo", May 1994

E. Davis, "Branching Continuous Time and the Semantics of Continuous Action", Jul. 1994

C. Yao, "Representing Control in Parallel Applicative Programing", Sep. 1994

M. Ebner, R. Wallace, "A Direct-Drive Hand: Design, Modeling and Control", Jun. 1994

R. Wallace, J. Selig, "Scaling Direct Drive Robots", Aug. 1994

J. Choi, J. Sellen, C.K. Yap, "Approximate Euclidean Shortest Path in 3-Space" Sep. 1994

M.S. Martins, "Schwarz Preconditioners for Elliptic Problems with Discontinuous Coefficients Using Conforming and Non-Conforming Elements", Sep. 1994

J. Sellen, "Planning Paths of Minimal Curvature", Oct. 1994

Abstract: We consider the problem of planning curvature constrained paths amidst polygonal obstacles, connecting given start and target configurations. Let the critical curvature Rc be the minimal curvature for which a constrained path exists. We describe an algorithm, which approximates the critical curvature and finds a corresponding path. Further, we give an efficient decision procedure to determine if there exists a path satisfying a given curvature constraint R, with running time polynomial in |R-Rc|/R.

S. M. Sokolov, D. P. Max, R. S. Wallace, "Simple Multi Function Vision System for 3D Data Acquisition", Oct. 1994

Abstract: We have developed a simple multi function vision system for 3D data acquisition for a wide range of applications in robotics and automation. The system uses one CCD video camera and an active directed laser light source based on a direct drive spherical pointing motor (SPM). The anatomy of the system and algorithms used are described. System calibration methods and measurements of accuracy of the outputs are presented. A list of applications is shown.

M. Antoniotti, B. Mishra, "Automatic Synthesis Algorithms for Supervisory Controllers (Preliminary Report)", Nov. 1994

Abstract: In this paper we describe our experience with a prototype system capable of synthesizing "Supervisor Controller Programs" based largely on the theory of discrete event systems (DES) first proposed by Ramadge and Wonham. We augment the theory by also allowing continuous time trajectories modeling transitions between events. We illustrate our approach by an example, - the discrete control of a walking machine - which poses some challenges on the applicability of the theory and finally, discuss some possible solutions.

Notes: Appeared in IEEE Proceedings of the Fourth International Conference on Computer Integrated Manufacturing and Automation Technology, Troy, NY, Oct. 1994

M. Antoniotti, B. Mishra, "Discrete Event Models + Temporal Logic = Supervisory Controller: Automatic Synthesis of Locomotion Controllers", Nov. 1994

Abstract: In this paper, we address the problem of the synthesis of controller programs for a variety of robotics and manufacturing tasks. The problem we choose for test and illustrative purposes is the standard ``Walking Machine Problem,'' a representative instance of a real "hybrid" problem with both logical/discrete and continuous properties and strong mutual influence without any reasonable separation. We aim to produce a ``compiler technology'' for this class of problems in a manner analogous to the development of the so-called ``Silicon Compilers'' for the VLSI technology. To cope with the difficulties inherent to the problem, we resort to a novel approach that combines many key ideas from a variety of disciplines: namely, ``Discrete Event Supervisory Systems'', Petri Nets approaches and ``Temporal Logic''.

Notes: Will appear in the 1995 IEEE International Conference on Robotics and Automation, Nagoya, Japan

A. Klawonn, "An Optimal Preconditioner for a Class of Saddle Point Problems with a Penalty Term", Dec. 1994

Abstract: Iterative methods are considered for a class of saddle point problems with a penalty term arising from finite element discretizations of certain elliptic problems. An optimal preconditioner which is independent of the and the penalty parameter is constructed. This approach is then used to design an iterative method with a convergence rate independent of the Lam\'{e} parameters occuring in the equations of linear elasticity.

Please see revised version tr683.

A. Knyazev, "New Estimates for Ritz Vectors", Dec. 1994

Abstract: The followiing estimate for the Rayleigh--Ritz method is proved: $$ | \tilde \lambda - \lambda | |( \tilde u , u )| \le { \| A \tilde u - \tilde \lambda \tilde u \| } \sin \angle \{ u ; \tilde U \}, \ \| u \| =1. $$ Here $A$ is a bounded self-adjoint operator in a real Hilbert/euclidian space, $\{ \lambda, u \}$ one of its eigenpairs, $\tilde U$ a trial subspace for the Rayleigh--Ritz method, and $\{ \tilde \lambda, \tilde u \}$ a Ritz pair. %$\| u \| = \| \tilde u \| = 1.$ This inequality makes it possible to analyze the fine structure of the error of the Rayleigh--Ritz method, in particular, it shows that $ |( \tilde u , u )| \le C \epsilon^2, $ if an eigenvector $u$ is close to the trial subspace with accuracy $\epsilon$ and a Ritz vector $\tilde u$ is an $\epsilon$ approximation to another eigenvector, with a different eigenvalue. Generalizations of the estimate to the cases of eigenspaces and invariant subspaces are suggested, and estimates of approximation of eigenspaces and invariant subspaces are proved.

tr678 Part 1 Part 2 Part 3 Part 4
A. Gueziec, R. Hummel, "The Wrapper Algorithm for Surface Extraction in Volumetric Data", Dec. 1994

Abstract: Beginning with digitized volumetric data, we wish to rapidly and efficiently extract and represent surfaces defined as isosurfaces in the interpolated data. The Marching Cubes algorithm is a standard approach to this problem. We instead perform a decomposition of each 8-cell associated with a voxel into five tetrahedra, as in the Payne-Toga algorithm. Following the ideas of Kalvin, Thirion et al., and using essentially the same algorithm as Doi and Koide, we guarantee the resulting surface representation to be closed and oriented, defined by a valid triangulation of the surface of the body, which in turn is presented as a collection of tetrahedra, some of which are only partly filled. The surface is extracted as a collection of closed triangles, where each triangle is an oriented closed curve contained within a single tetrahedron. The entire surface is ``wrapped'' by the collection of triangles, using especially efficient data structures. The representation is similar to the homology theory that uses simplices embedded in a manifold to define a closed curve within each tetrahedron.

From the triangles that comprise the wrapping of the surface, we give methods to evaluate surface curvatures and principal directions at each vertex, whenever these quantities are defined. We further present a fast method for rendering and approximating the surface. The triangles form a graph structure, which is very efficiently encoded, whose nodes are the triangles and whose edges are the common edges joining adjacent triangles. We can thus identify each surface using a connected component labelling algorithm applied to the graph.

This provides a highly parallelizable approach to boundary surface representation, providing an efficiently and compact surface representation. The wrapper algorithm has been used to extract surfaces of the cranium from CT-scans and cortical surfaces from MR-scans at full resolution.

Key words: B-rep, boundary representation, Marching Cubes, tetrahedral decomposition, homology theory, surface curvature.

C. Yap, "Report on NSF Workshop on Manufacturing and Computational Geometry", Jan. 1995

Abstract: This is a summary of the NSF Workshop on Manufacturing and Computational Geometry, held at the Courant Institute of Mathematical Sciences, New York University, on April 1-2, 1994. The meeting brought together about 30 participants from both the manufacturing and the computational geometry communities for the purposes of discussing current trends in the two communities, identifying areas of mutual interest, and proposing future joint activities.

B. Mishra, "Grasp Metrics: Optimality and Complexity", Jan. 1995

Abstract: In this paper, we discuss and compare various metrics for goodness of a grasp. We study the relations and trade-offs among the goodness of a grasp, geometry of the grasped object, number of fingers and the computational complexity of the grasp-synthesis algorithms. The results here employ the techniques from convexity theory first introduced by the author and his colleagues.

F. Alizadeh, J. Haeberly, M. Overton, "Complementarity and Nondegeneracy in Semidefinite Programming", Mar. 1995

Abstract: Primal and dual nondegeneracy conditions are defined for semidefinite programming. Given the existence of primal and dual solutions, it is shown that primal nondegeneracy implies a unique dual solution and that dual nondegeneracy implies a unique primal solution. The converses hold if strict complementarity is assumed. Primal and dual nondegeneracy assumptions do not imply strict complementarity, as they do in LP. The primal and dual nondegeneracy assumptions imply a range of possible ranks for primal and dual solutions $X$ and $Z$. This is in contrast with LP where nondegeneracy assumptions exactly determine the number of variables which are zero. It is shown that primal and dual nondegeneracy and strict complementarity all hold generically. Numerical experiments suggest probability distributions for the ranks of $X$ and $Z$ which are consistent with the nondegeneracy conditions.

K. Andersen, E. Christiansen, M. Overton, "Computing Limit Loads by Minimizing a Sum of Norms", Apr. 1995

Abstract: We consider the problem of computing the collapse state in limit analysis for a solid with a quadratic yield condition, such as, for example, the Mises condition. After discretization with the finite element method, using divergence-free elements for the plastic flow, the kinematic formulation turns into the problem of minimizing a sum of Euclidean vector norms, subject to a single linear constraint. This is a nonsmooth minimization problem, since many of the norms in the sum may vanish at the optimal point. However, efficient solution algorithms for this particular convex optimization problem have recently been developed.

The method is applied to test problems in limit analysis in two different plane models: plane strain and plates. In the first case more than 80 percent of the terms in the sum are zero in the optimal solution, causing severe ill-conditioning. In the last case all terms are nonzero. In both cases the algorithm works very well, and we solve problems which are larger by at least an order of magnitude than previously reported. The relative accuracy for the discrete problems, measured by duality gap and feasibility, is typically of the order 1.0E-8. The discretization error, due to the finite grid, depends on the nature of the solution. In the applications reported here it ranges from 1.0E-5 to 1.0E-2.

Keywords: Limit analysis, plasticity, finite element method, nonsmooth optimization.

A. Klawonn, "An Optimal Preconditioner for a Class of Saddle Point Problems with a Penalty Term, Part II: General Theory", Apr. 1995

Abstract: Iterative methods are considered for saddle point problems with penalty term. A positive definite preconditioner is constructed and it is proved that the condition number of the preconditioned system can be made independent of the discretization and the penalty parameters. Examples include the pure displacement problem in linear elasticity, the Timoshenko beam, and the Mindlin-Reissner plate.

Key words: Saddle point problems, penalty term, nearly incompressible materials, Timoshenko, Mindlin-Reissner, preconditioned conjugate residual method, multilevel, domain decomposition.

Please note: This report is a revised version of tr676.

A. Siegel, "On Universal Classes of Extremely Random Constant Time Hash Functions and their Time-space Tradeoff", Apr. 1995

Abstract: A family of functions F that map [0,n]->[0,n], is said to be h-wise independent if any h points in [0,n] have an image, for randomly selected f in F, that is uniformly distributed. This paper gives both probabilistic and explicit randomized constructions of (n**epsilon)-wise independent functions, for epsilon<1, that can be evaluated in constant time for the standard random access model of computation. Simple extensions give comparable behavior for larger domains. As a consequence, many probabilistic algorithms can for the first time be shown to achieve their expected asymptotic performance for a feasible model of computation.

This paper also establishes a tight tradeoff in the number of random seeds that must be precomputed for a random function that runs in time T and is h-wise independent.

A. Siegel, "Toward a Usable Theory of Chernoff Bounds for Heterogeneous and Partially Dependent Random Variables", Apr. 1995

Abstract: Let X be a sum of real valued random variables and have a bounded mean E[X]. The generic Chernoff-Hoeffding estimate for large deviations of X is: P{X-E[X]>=a}<=min_{y>=0}exp(-y(a+E[X]))E[exp(y X)], which applies with a>=0 to random variables with very small tails. At issue is how to use this method to attain sharp and useful estimates. We present a number of Chernoff-Hoeffding bounds for sums of random variables that may have a variety of dependent relationships and that may be heterogeneously distributed.

J. Schmidt, A. Siegel, "Double Hashing is Computable and Randomizable with Universal Hash Functions", Apr. 1995

Abstract: Universal hash functions that exhibit (c log n)-wise independence are shown to give a performance in double hashing and virtually any reasonable generalization of double hashing that has an expected probe count of 1/(1-alpha) + epsilon for the insertion of the (alpha n)-th item into a table of size n, for any fixed alpha < 1 and epsilon > 0. This performance is within epsilon of optimal. These results are derived from a novel formulation that overestimates the expected probe count by underestimating the presence of partial items already inserted into the hash table, and from a sharp analysis of the underlying stochastic structures formed by colliding items.

A. Siegel, J. Schmidt, "Closed Hashing is Computable and Optimally Randomizable with Universal Hash Functions", Apr. 1995

Abstract: Universal hash functions that exhibit (c log n)-wise independence are shown to give a performance in double hashing, uniform hashing and virtually anyreasonable generalization of double hashing that has an expected probe count of 1/(1-alpha)+O(1/n) for the insertion of the (alpha n)-th item into a table of size n, for any fixed alpha < 1. This performance is optimal. These results are derived from a novel formulation that overestimates the expected probe count by underestimating the presence of local items already inserted into the hash table, and from a very sharp analysis of the underlying stochasticstructures formed by colliding items.

Analogous bounds are attained for the expected r-th moment of the probe count, or any fixed r, and linear probing is also shown to achieve a performance with universal hash functions that is equivalent to the fully random case.

A. Muravitsky, "On the First Degree Entailment of Two 3-Valued Logics", May 1995

Abstract: We note first that the first degree entailment of {\L}ukasiewicz's 3-valued logic and a 3-valued logic that is extracted of Belnap's 4-valued logic is the same. Then, we give an axiomatization of that entailment as the calculus E_{fde} + A&-A->B\/-B, where E_{fde} is the first degree entailment of Anderson-Belnap's logic E of relevance and necessity.

A. Muravitsky, "Knowledge Representation as Domains", May 1995

Abstract: This is a continuing attempt in a series of papers [,, ] to show how computer-represented knowledge can be arranged as elements of an effectively represented semantic domain in the sense of [C.A.Gunter and D.S.Scott, Semantic Domains, in: J. van Leeuwen (ed.), Handbook of Theoretical Computer Science, Vol. B, pp. 635--674]. We present a direct deductive description of the domain, which was defined semantically in [ ], via the Scott's notion of information system. Also, the internal structure of the continuous ampliative operations coordinated with the domain's effective basis is established. Though we always remain in the paradigm of the toleration of contradictory information described in [N.D.Belnap, A Useful Four-Valued Logic: How a Computer Should Think, in: A.R.Anderson, N.D.Belnap, and J.M.Dunn, Entailment: the Logic of Relevance and Necessity, Vol. 2, Princeton Univ. Press, 1992], the approach in question could be extended to include domains for consistency knowledge bases.

A. Muravitsky, "A Framework for Knowledge-Based Systems", May 1995

Abstract: The paper continues the theme of [ ]. We differentiate between our approach to knowledge representation and that of others by expressing the following Working Hypothesis: Knowledge is a data type, and knowledge revision is accomplished by continuous operations on it, which are coordinated with its effective basis. Staying in the limits of Belnap's paradigm of the admittance of contradictory information into the computer's memory, our purpose in this paper is to reduce as much as possible all the computable processes needed for modifing the current state of the computer's knowledge and describe conditions for possible maneuvering. In particular, we solve some problems of decidability concerning operations on the minimal states, which are regarded as natural knowledge transformers. We show, also, how to express those operations in lattice theory terms that leads to the simplification of their computation on the lattice of minimal states. The problem of backtracking in the presented context is considered as well.

A. Muravitsky, "Some Knowledge Transformers: Infons and Constraints", May 1995

Abstract: The goal of this paper is twofold. First, it is to present a general scheme within which information is supposed to turn into the computer-represented knowledge and, second, to define two natural kinds of transfomers of this knowledge which this scheme thrusts us into considering.

Y. Kaluzhny, A. Muravitsky, "A Knowledge Representation Based on the Belnap's Four-Valued Logic", May 1995

Abstract: We treat knowledge from a computer-oriented point of view, considering it as a kind of data type. An axiomatic approach to the notion of data type undertaken by Dana Scott in [D.S.Scott, Outline of a Mathematical Theory of Computation, in: Proceedings of Princeton Conference on Information Science, 1971, pp. 169--176], is explored to find entities suitable for representation techniques. At the same time, we stay in Belnap's paradigm of the toleration of inconsistency. We propose a representation of knowledge (possible with contradictions) in simple propositional language, and we show how such knowledge can be maintained and how it should be transformed on receipt of new information. In this transformation, the key role is played by Scott's continuity rather than consistency.

A. Muravitsky, "A Perspective of New Foundations for Knowledge Maintenance Systems: Research Program", May 1995

Abstract: We propose to provide new mathematical foundations for the design of knowledge-based systems. The underlying idea is that the knowledge which the computer (``artificial agent'') operates with is considered as a kind of abstract data type. In this context, a relation of approximation arises in a natural way when one imagines the computer as operating in a changing information environment (``information flow''). This notion of pproximation can be studied using the techniques that have been developed for domain theory in the context of denotational semantics of programming languages.

A. Muravitsky, "Logic of Information Knowledge", May 1995 (see tr #691)

Abstract: We share with some philosophers the view that a state of knowledge, being a part of the real world, can bring contradiction into it. Such an ontological reading of knowledge is very important when one deals with information knowledge, which arises as the content of the computer's memory when the computer is placed into changeable information environment ("information flow"), and "must" be able to tolerate any (not excluding contradictions) from the computer's users. Continuing research begun in [KM 93], we consider in length one kind of Scott-continuous operations introduced there. Each such operation [A->B](x), where A and B are formulas in a propositional language, called a rule, moves the computer to a "minimal" state of knowledge, in which B is true, if in a current state A is true. Note that the notion of rule is used here in an information-transforming sense, rather than in the ordinary truth-sound sense. We distinguish between global and local rules and show that these notions are decidable. Also, we define a modal epistemic logic as a tool for the prediction of possible evolution of the system's knowledge and establish decidability of this logic.

A. Kheyfits, "Dirichlet Problem for the Schrodinger Operator in a Half-space with Boundary Data of Arbitrary Growth at Infinity", May 1995

Abstract: We consider the Dirichlet problem for the Schrodinger operator in a half-space with boundary data having an arbitrary growth at infinity. A solution is constructed as the generalized Poisson integral. Uniqueness of the solution is investigated too.