Microsoft Research Blog

English

Nondeterministic Linear-Time Tasks May Require Substantially Nonlinear Deterministic Time in the Case of Sublinear Work Space

June 4, 1990 | Yuri Gurevich and Saharon Shelah

We develop a technique to prove time-space trade-offs and exhibit natural search problems (e.g. Log-size Clique Problem) that are solvable in linear time on polylog-space (and sometimes even log-space) nondeterministic Turing machine, but no deterministic machine (in a very general sense of this term) with…
Memory Management in the Tera MTA Computer System

June 1, 1990 | Richard Korry, Cathy McCann, and Burton Smith

This paper describes memory scheduling for the Tera MTA (Multi Threaded Architecture) computer system. The Tera MTA is intended to support a mixture of large and small tasks running in parallel, and ensure that they all make progress commensurate with their importance. We describe the…
Lapped Transforms for Efficient Transform/Subband Coding

June 1, 1990 | Henrique S. Malvar

Two new lapped transforms for subband/transform coding of signals are introduced: a new version of the lapped orthogonal transform (LOT), which can be efficiently computed for any transform length; and the modulated lapped transform (MLT), which is based on a modulated quadrature mirror filter (QMF)…
Conceptual Set Covering: Improving Fit-and-Split Algorithms

June 1, 1990 | Carl Kadie

Many learning systems implicitly use the fit-and-split learning method to create a comprehensive hypothesis from a set of partial hypotheses. At the core of the fit-and-split method is the assignment of examples to partial hypotheses. To date, however, this core has been neglected. This paper…
Towards Microphone-Independent Spoken Language Systems

June 1, 1990 | Alex Acero

TOWARDS MICROPHONE-INDEPENDENT SPEECH RECOGNITION
Finite-Size Scaling for Potts Models

June 1, 1990 | Christian Borgs, Roman Kotecky, and Salvador Miracle-Sole

Recently, two of the authors (C.B. and R.K.) developed a rigorous theory of finite-size effects near first-order phase transitions.
Modulated QMF Filter Banks with Perfect Reconstruction

June 1, 1990 | Henrique S. Malvar

Necessary and sufficient conditions for perfect reconstruction (PR) in a modulated filter bank are derived. It is shown that, for a bank of M filters of length L, PR can be obtained when L = 2KM, for any positive integer K, whereas previous results guaranteed…
Fast surface interpolation using hierarchical basis functions

May 31, 1990 | Rick Szeliski

An alternative to multigrid relaxation that is much easier to implement and more generally applicable is presented. Conjugate gradient descent is used in conjunction with a hierarchical (multiresolution) set of basis functions. The resultant algorithm uses a pyramid to smooth the residual vector before the…
Live Text

May 2, 1990 | Balachauder Krishnamurthy and Christopher Fraser

Describes a software package that allows the user to edit the output of several common software tools and to cause the changes to be written back to the input files. For example, it is possible to edit the output of a spelling checker and have…
Local Spatial Frequency Analysis for Computer Vision

May 1, 1990 | John Krumm and Steven A. Shafer

A sense of vision is a prerequisite for a robot to function in an unstructured environment. However, real-world scenes contain many interacting phenomena that lead to complex images which are difficult to interpret automatically. Typical computer vision research proceeds by analyzing various effects in isolation…
An overview of the SPHINX speech recognition system

April 30, 1990 | Kai-Fu Lee, Hsiao-Wuen Hon, and R. Reddy

A description is given of SPHINX, a system that demonstrates the feasibility of accurate, large-vocabulary, speaker-independent, continuous speech recognition. SPHINX is based on discrete hidden Markov models (HMMs) with LPC- (linear-predictive-coding) derived parameters. To provide speaker independence, knowledge was added to these HMMs in several…
VideoDraw: A Video Interface for Collaborative Drawing

April 15, 1990 | John Tang

This paper describes VideoDraw, a shared drawing tool, and the process by which it is being designed and developed. VideoDraw is a prototype, video-based, tool that provides a shared “virtual sketchbook” among two or more collaborators. It not only allows the collaborators to see each…

No results