New York University
Courant Institute of Mathematical Sciences
Department of Computer Science
Technical Report Repository
Following is a listing of all technical reports currently available in
/pub/tech-reports. Please contact christie@cs.nyu.edu with any questions.
TR 086-U100 A. Gottlieb. An Overview of the NYU Ultracomputer
Project (Oct. 1987, Revised)
TR 221-U101 G. Landau, U. Vishkin. Efficient Parallel and Serial
Approximate String Matching. (Feb. 1986)
TR 222-U102 Y. Maon, B. Schieber, U. Vishkin. Parallel Ear Decomposition
Search (EDS) and ST-Numbering in Graphs. (Feb. 1986)
TR 223-U103 Y. Azar, U. Vishkin. Tight Comparison Bounds on the Complexity
of Parallel Sorting. (Feb. 1986)
TR 242-U108 R. Cole, U. Vishkin. The Accelerated Centroid Decomposition
Technique for Optimal Parallel Tree Evaulation in
Logarithmic Time. (Sep. 1986)
TR 243-U109 R. Cole, C. O'Dunlaing. Note on the AKS Sorting Network. (Sep.
1986)
TR 485 D. Szyld, O. Widlund. Variational Analysis of Some Conjugate
Gradient Methods. (Dec. 1989)
TR 486-U167 M. Dryja, O. Widlund. Towards a Unified Theory of Domain
Decomposition Algorithms for Elliptic Problems. (Dec. 1989)
TR 489 D. Rennels, E. Schonberg. A Program Analysis Tool for
Evaluating the ADA Compiler Validation Suite. (Jan. 1990)
TR 498 K. Donovan. Performance of Shared Memory in a Parallel
Computer. (Mar. 1990)
TR 502 E. Weyuker, B. Jeng. Analyzing Partition Testing Strategies.
(Apr. 1990)
TR 503 V. Lanin, D. Shasha. Tree Locking on Changing Trees. (Apr.
1990)
TR 504-R230 M. Pellegrini. Stabbing and Ray Shooting in 3-Dimensional
Space. (May 1990)
TR 505 M. Overton. Large-Scale Optimization of Eigenvalues. (May
1990)
TR 506 X. Cai, O. Widlund. Domain Decomposition Algorithms for
Indefinite Elliptic Problems. (May 1990)
TR 507 M. Dryja, O. Widlund. Multilevel Additive Methods for
Elliptic Finite Element Problems. (May 1990)
TR 510 S. Cox, M. Overton. On the Optimal Design of Columns
Against Buckling. (Jun. 1990)
TR 512 R. Cole, Tight Bounds on the Complexity of the Bover-Moore
Pattern Matching Algorithm. (Jun. 1990)
TR 514 D. Shasha, J. Turek. Beyond Fail-Stop: Wait-Free
Serializability and Resiliency in the Presence of
Slow-Down Failures. (Sep. 1990)
TR 518 K. Li. Dag Representation and Optimization of Rewriting.
(Sep. 1990)
TR 517 B. Smith. Domain Decomposition Algorithms for the Partial
Differential Equations of Linear Elasticity. (Sep. 1990)
TR 519 B. Smith. A Domain Decomposition Algorithm for Elliptic
Problems in Three Dimensions. (Oct. 1990)
TR 520 J. Burke. Stable Perturbations of Nonsymmetric. (Oct. 1990)
TR 523 P. Ouyang. Execution of Regular DO Loops on Asynchronous
Multiprocessors. (Oct. 1990)
TR 529 M. Dryja. Substructuring Methods for Parabolic Problems.
(Nov. 1990)
TR 531 W. Jockush, N. Prabhu. Cutting a Polytype. (Nov. 1990)
TR 532 G. Bohus, W. Jockush, C. Lee, N. Prabhu. On Triangulations of
the 3-Ball and the Solid Torus. (Nov. 1990)
TR 533 N. Prabhu. On a Conjecture of Micha Perles.
(Nov. 1990)
TR 534 E. Davis. Physical Idealization as Plausible Inference.
(Nov. 1990)
TR 536-R241 M. Pellegrini. Combinatorial and Algorithmic Analysis of
Stabbing and Visibility Problems in 3-Dimensional Space.
(Dec. 1990)
TR 539 R. Cole, O. Zajicek. The APRAM - The Rounds Complexity
Measure and the Explicit Costs of Synchronization.
(Jan. 1991)
TR 541 E. Davis. The Kinematics of Cutting Solid Objects.
(Jan. 1991)
TR 542-U170 R. Cytron, J. Lipkis, E. Schonberg. A Computer-Assisted
Approach to SPMD Execution. (Jul. 1990)
TR 546 R. Cole, O. Zajicek. An Asynchronous Parallel Algorithm
for Undirected Graph Connectivity. (Feb. 1991)
TR 547-R244 G. Gallo, B. Mishra. Some Constructions in Rings of
Differential Polynomials. (Mar. 1991)
TR 548 K. L. Clarkson, R. Cole, R. E. Tarjan. Randomized Parallel
Algorithms for Trapezoidal Diagrams. (Mar. 1991)
TR 549-R245 S. Mallat, W. L. Hwang. Singularity Detection and Processing
with Wavelets. (Mar. 1991)
TR 552 P. Charles. A Practical Method for Constructing Efficient
LALR(k) Parsers with Automatic Error Recovery. (Mar. 1991)
TR 553 I. Rigoutsos, R. Hummel. Scalable Parallel Geometric
Hashing for Hypercube SIMD Architectures. (Jan. 1991)
TR 554 I. Rigoutsos, R. Hummel. On a Parallel Implementation of
Geometric Hashing on the Connection Machine. (Apr. 1991)
TR 555 K. Laufer. Comparing Three Approaches to Transformational
Programming. (Apr. 1991)
TR 556 F. Henglein, K. Laufer. Programming with Structures, Functions,
and Objects. (Apr. 1991)
TR 557 R. Cole, U. Vishkin. On the Detection of Robust Curves.
(Apr. 1991)
TR 558-R246 G. Koren, B. Mishra, A. Raghunathan, D. Shasha. On-Line
Schedulers for Overloaded Real-Time Systems. (May 1991)
TR 561 R. Sundar. Amortized Complexity of Data Structures. (May 1991)
TR 562 S. Nepomnyaschikh. Decomposition and Fictitious Domains
Methods for Elliptic Boundary Value Problems. (May 1991)
TR 565 E. Davis. Lucid Representations. (Jun. 1991)
TR 566 M. Overton, R. Womersley. Optimality Conditions and Duality
Thoery for Minimizing Sums of the Largest Eigenvalues of
Symmetric Matrices. (Jun. 1991)
TR 567 J. Burke, M. Overton. On the Subdifferentiability of a
Matrix Spectrum I: Mathematical Foundations. (Jun. 1991)
TR 568 J. Burke, M. Overton. On the Subdifferentiability of a
Matrix Spectrum II: Subdifferential Formulas. (Jun. 1991)
TR 569-R250 P. Tetali. Applications and Analysis of Probablistic
Techniques. (Jun. 1991)
TR 570 M. Dryja, O. Widlund. Additive Schwarz Methods for Elliptic
Finite Element Problems in Three Dimensions. (Jun. 1991)
TR 571 F. Gasperoni, U. Schweigelshohn. Efficient Algorithms for
Cyclic Scheduling. (Jul. 1991)
TR 572 G. Koren, D. Shasha. An Optimal Scheduling Algorithm with
a Competitive Factor for Real-Time Systems. (Jul. 1991)
TR 573 R. Cole, A. Raghunathan. Online Algorithms for Finger
Searching. (Aug. 1991)
TR 574 R. Cole, O. Zajicek. The Expected Advantage of Asynchrony.
(Sep. 1991)
TR 579 J. Burke, M. Overton. Differential Properties of Eigenvalues.
(Sep. 1991)
TR 580 L. Pavarino. An Additive Schwarz Method for the P-Version
Finite Element Method. (Sep. 1991)
TR 581 O. Widlund. Some Schwarz Methods for Symmetric and Nonsymmetric
Elliptic Problems. (Sep. 1991)
TR 582 X. Zhang. Multilevel Additive Schwarz Methods. (Sep. 1991)
TR 583 X. Zhang. Domain Decompositioin Algorithms for the
Biharmonic Dirichlet Problem. (Sep. 1991)
TR 584 X. Zhang. Studies in Domain Decomposition: Multilevel Methods
and the Biharmonic Dirichlet Problem. (Sep. 1991)
TR 585 M. Hind. Efficient Loop-Level Parallelism in ADA. (Sep. 1991)
TR 586 J. Haeberly. On Shape Optimizing the Ratio of the First Two
Eigenvalues of the Laplacian. (Oct. 1991)
TR 587 C. Chang, R. Paige. New Theoretical and Computational Results
for Regular Languages. (Oct. 1991)
TR 588-R255 B. Bederson, R. Wallace, E. Schwartz. A Miniaturized Active
Vision System. (Nov. 1991)
TR 589-R256 R. Wallace, P. Ong, B. Bederson, E. Schwartz. Space-Variant
Image Processing. (Nov. 1991)
TR 590 E. Davis. Axiomating Qualitative Process Theory. (Nov. 1991)
TR 594 G. Koren, D. Shasha. An Optimal On-Line Scheduling Algorithm
for Overloaded Real-Time Systems. (Jan. 1992)
TR 595 X.-C. Cai, O. Widlund. Multiplicative Schwarz Algorithms for
Some Nonsymmetric and Indefinite Problems. (Feb. 1992)
TR 597 G. Park. Semantic Analyses for Storage Management Optimizations
in Functional Language Implementations. (Feb. 1992)
TR 599 E. Davis. Infinite Loops in Finite Time: Some Observations.
(Feb. 1992)
TR 601-R264 B. Bederson, R. Wallace, E. Schwartz. A Miniature Pan-Tilt
Actuator: The Spherical Pointing Motor. (Apr. 1992)
TR 602 J. Cai, X. Han, R. Tarjan. An $O(m$log$n)$-Time Algorithm for
the Maximal Planar Subgraph Problem. (Apr. 1992)
TR 603 J. Cai. Counting Embeddings of Planar Graphs Using DFS Trees.
(Apr. 1992)
TR 604 J. Cai, R. Paige, R. Tarjan. More Efficient Bottom-Up
Multi-Pattern Matching in Trees. (Apr. 1992)
TR 606 M. Dryja, O. Widlund. Domain Deomposition Algorithms with
Small Overlap. (May 1992)
TR 607 A. Greenbaum, L. Trefethen. GMRES/CR and Arnoldi/Lanczos
as Matrix Approximations Problems. (May 1992)
TR 608 A. Greenbaum, Z. Strakos. Matrices that Generate the
Same Krylov Residual Spaces. (May 1992)
TR 609 J. Cai, R. Paige. Multiset Discrimination -- A Method for
Implementing Programming Language Systems Without Hashing.
(Jun. 1992)
TR 610 V. Averbukh, S. Figueroa, T. Schlick. HESFCN -- A FORTRAN
Package of Hessian Subroutines for Testing Nonlinear
Optimization Software. (Jun. 1992)
TR 611-R266 B. Bederson. Miniature Space-Variant Active Vision System:
Cortex-I. (Jul. 1992)
TR 612-R267 D. Karron, J. Cox, B. Mishra. The Spiderweb Algorithm
for Surface Construction from Medical Volume Data:
Geometric Properties of its Surface. (Jul. 1992)
TR 614 L. Pavarino. Some Schwarz Algorithms for the P-Version
Finite Element Method. (Sep. 1992)
TR 615 M. Dryja, O. Widlund. Some Recent Results on Schwarz
Type Domain Decomposition Algorithms. (Sep. 1992)
TR 616 L. Pavarino. Domain Decomposition Algorithms for the
P-Version Finite Element Method for Elliptic Problems.
(Sep. 1992)
TR 619 S. Mallat, Z. Zhang. Matching Pursuits with Time-Frequency
Dictionaries. (Revised Aug. 1993)
TR 620 T.-R. Chuang, B. Goldberg. Backward Analysis for Higher-Order
Functions Using Inverse Images. (Nov. 1992)
TR 621 F. Tsai. Statistical Approach to Affine Invariant Matching
with Line Features. (Nov. 1992)
TR 622 K. Laufer. Polymorphic Type Inference and Abstract Data
Types. (Dec. 1992)
TR 623 J. Cullum, A. Greenbaum. Residual Relationships Within
Three Pairs of Iterative Algorithms for Solving $Ax = b$.
(Feb. 1993)
TR 624 J. Haeberly, M. Overton. A Hybrid Algorithm for Optimizing
Eigenvalues of Symmetric Definite Pencils. (Feb. 1993)
TR 625 F. Tsai. Using Line Invariants for Object Recognition
by Geometric Hashign. (Feb. 1993)
TR 626 M. Dryja, O. Widlund. Schwarz Methods of Neumann-Neumann
Type for Three-Dimensional Elliptic Finite Element
Problems. (Mar. 1993)
TR 627 M. Overton, R. Womersley. Second Derivatives for Optimizing
Eigenvalues of Symmetric Matrices. (Mar. 1993)
TR 628 G. Gallo, B. Mishra. The Complexity of Resolvent Resolved.
(Mar. 1993)
TR 629 M. Sarkis. Two-Level Schwarz Methods for Nonconforming
Finite Elements and Discontinous Coefficients. (Mar. 1993)
TR 630 P. Agarwal. The Cell Programming Language. (Mar. 1993)
TR 631 M. Overton, X. Ye. Towards Second-Order Methods for
Structured Nonsmooth Optimization. (Apr. 1993)
TR 632 Muthukrishnan, K. Palem. Highly Efficient Dictionary
Matching in Parallel. (Apr. 1993)
TR 633 R. Wallace, P. Ong, B. Bederson, E. Schwartz. Space
Variant Image Processing. (Apr. 1993)
TR 634 R. Wallace. Miniature Direct Drive Rotary Actuators.
(Apr. 1993)
TR 635 J. Cai. A Language for Semantic Analysis. (May 1993)
TR 636 R. Wallace, B. Bederson, E. Schwartz. Voice-Bandwidth
Visual Communication Through Logmaps: The Telecortex.
(May 1993)
TR 637 E. Davis. Knowledge Preconditions for Plans. (May 1993)
TR 638 M. Dryja, B. Smith, O. Widlund. Schwarz Analysis of
Iterative Substructuring Algorithms for Elliptic Problems
in Three Dimensions. (May 1993)
TR 639 G. Koren, D. Shasha. Competitive Algorithms and Lower
Bounds for On-line Scheduling of Multiprocessor Real-time
Systems. (Jun. 1993)
TR 640 F. Tsai. A Probabilistic Approach to Geometric Hashing
Using Line Features. (Jun. 1993)
TR 641 H. Hwang, S. Mallat. Characterization of Self-Similar
with Wavelet Maxima. (Aug. 1993)
TR 642 N. Silver. Control of a Dextrous Robot Hand: Theory,
Implementation, and Experiment. (Aug. 1993; not avail.
via FTP; email mishra@cs.nyu.edu)
TR 643 B. Mishra, M. Antoniotti. ED I: NYU Educational Robot
Design and Evaluation. (Aug. 1993)
TR 644 T.-R. Chuang. New Techniques for the Analysis and
Implementation of Functional Programs. (Aug. 1993)
TR 645 A. Greenbaum. Norms of Functions of Matrices. (Aug. 1993)
TR 646 B. Mishra. Bidirectional Edges Problem: Part I, a
Simple Algorithm. (Sep. 1993)
TR 647 B. Mishra. Bidirectional Edges Problem: Part II, an
Efficient Algorithm. (Sep. 1993)
TR 648 L. Pavarino, O. Widlund. Iterative Substructuring Methods
for Special Elements in Three Dimensions. (Sep. 1993)
TR 649 H. Cheng. Iterative Solution of Elliptic Finite Element
Problems on Partially Refined Meshes and the Effect of
Using Inexact Solvers. (Oct. 1993)
TR 650 B. Mishra. A Survey of Computational Differential Algebra.
(Oct. 1993)
TR 651 R. Wallace. Miniature Direct Drive Rotary Actuators II:
Eye, Finger, and Leg. (Nov. 1993)
TR 652 D. Max, R. Wallace. Feedback Control of Miniature Direct
Drive Devices. (Nov. 1993)
TR 653 B. Mishra, M. Antoniotti, F. Hansen, R. Wallace. NYU
Educational Robotics Project: A Pedagogic Overview.
(Nov. 1993)
TR 654 H. Chen. Multilevel Schwarz Methods with Partial Refinement.
(Mar. 1994)
TR 655 C. Yao, B. Goldberg. Pscheme: Extending Continuations to
Express Control and Synchronization in a Parallel LISP.
(Mar. 1994)
TR 657 G. Davis, S. Mallat, Z. Zhang. Adaptive Time-Frequency
Approximations with Matching Pursuits. (Mar. 1994)
TR 658 J. Maddocks, M. Overton. Stability Theory for Dissipatively
Perturbed Hamiltonian Systems. (Mar. 1994)
TR 659 F. Alizadeh, J.P. Haeberly, M. Overton. A New Primal-Dual
Interior-Point Method for Semidefinite Programming.
(Mar. 1994)
TR 660 J.P. Haeberly, M. Overton. Optimizing Eigenvalues of Symmetric
Definite Pencils. (Mar. 1994)
TR 661 L. Pavarino, O. Widlund. A Polylogarithmic Bound for an
Iterative Substructuring Method for Spectal Elements in
Three Dimensions. (Mar. 1994)
TR 662 M. Dryja, M. Sarkis, O. Widlung. Multilevel Schwarz Methods
for Elliptic Problems with Discontinuous Coefficients in
Three Dimensions. (Mar. 1994)
TR 663 L. Pavarino, O. Widlund. Iterative Substructuring Methods
for Spectral Elements: Problems in Three Dimensions Based
on Numerical Quadrature. (May 1994)
TR 664 M. Antoniotti. Conceptual and Pragmatic Tools for Design
and Control of Manufacturing Systems (Petrinets and
Ramadge-Wonham Discrete Event Systems). (Jul. 1993)
TR 665 S. Gomory, R. Wallace. Cursor Stereo. (May 1994)
TR 666 E. Davis. Branching Continuous Time and the Semantics of
Continuous Action. (Jul 1994)
TR 667 C. Yao. Representing Control in Parallel Applicative
Programming. (Sep 1994)
TR 668 M. Ebner, R. Wallace. A Direct--Drive Hand: Design, Modeling
and Control. (Jun 1994)
TR 669 R. Wallace, J. Selig. Scaling Direct Drive Robots. (Sep 1994)
TR 670 J. Choi, J. Sellen, C.K. Yap. Approximate Euclidean Shortest
Path in 3-Space.
TR 671 M.S. Martins, Schwarz Preconditioners for Elliptic Problems
with Discontinuous Coefficients Using Conforming and
Non-Conforming Elements.