Microsoft Research Blog

English

  1. The Architecture of the Agora Environment 

    July 8, 1987

    Agora is an environment that supports the construction of large, evolutionary programs that manipulate complex data structures, e.g., problem solving systems. Agora can be customized to support the computational model that is most suitable for a given application. Agora has been designed explicitly to support…

  2. Expected Computation Time for Hamiltonian Path Problem 

    July 8, 1987 | Yuri Gurevich and Saharon Shelah

    Let G(n,p) be a random graph with n vertices and the edge probability p. We give an algorithm for Hamiltonian Path Problem whose expected run-time on G(n,p) is cn/p + o(n) for any fixed p. This is the best possible result for the case of…

  3. The Byzantine Generals 

    July 7, 1987 | Danny Dolev, Leslie Lamport, Marshall Pease, and Robert Shostak

    I have only a vague memory of this paper. I believe Bhargava asked me to write a chapter about the results in [41] and [46]. I was probably too lazy and asked Dolev to write a chapter that combined his more recent results on connectivity…

  4. Ray Tracing Complex Models Containing Surface Tessellations 

    July 1, 1987 | John Snyder and Alan H. Barr

    An approach to ray tracing complex models containing mathematically defined surfaces is presented. Parametric and implicit surfaces, and boolean combinations of these, are first tessellated into triangles. The resulting triangles from many such surfaces are organized in a hierachy of lists and 3D grids, allowing…

  5. Document Production: Visual or Logical? 

    June 8, 1987 | Leslie Lamport

    Richard Palais ran a column on mathematical typesetting in the AMS Notices, and he invited me to be guest columnist. This is what I wrote--a short exposition of my ideas about producing mathematical documents.

  6. Distribution 

    May 28, 1987 | Leslie Lamport

    This message is the source of the following observation, which has been quoted (and misquoted) rather widely: A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable.

  7. Monotone Versus Positive 

    April 8, 1987 | Miklos Ajtai and Yuri Gurevich

    A number of famous theorems about first-order logic were disproved in [60] in the case of finite structures, but Lyndon's theorem on monotone vs. positive resisted the attack. It is defeated here. The counter-example gives a uniform sequence of constant-depth polynomial-size (functionally) monotone boolean circuits…

  8. The Implementation of Functional Programming Languages 

    April 1, 1987 | Simon Peyton Jones

    “The Implementation of Functional Languages” is a book about implementing functional programming languages using lazy graph reduction, and it divides into three parts. The first part describes how to translate a high-level functional language into an intermediate language, called the lambda calculus, incuding detailed coverage…