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…
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…
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…
We present a representation of partial confidence in belief and preference that is consistent with the tenets of decision-theory. The fundamental insight underlying the representation is that if a person is not completely confident in a probability or utility assessment, additional modeling of the assessment…
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…
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.
Performance analysis of a tactile sensor.
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.
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…
This paper describes the transition axiom method I introduced in [50]. It was written for a NATO Advanced Study Institute that took place in Turkey in August, 1986, and contains little that was new.
“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…
The analysis of signals that can be represented as a linear combination of exponentially damped sinusoids where the values of damping factors, frequencies, and the linear combination coefficients change at certain transition times is considered. These transitions represent the opening and closing of the glottis…
