Papadimitriou and Yannakakis were interested whether Unique Sat is hard for {L - L' : L, L' are NP} when NP differs from co-NP (otherwise the answer is obvious). We show that this is true under one oracle and false under another.
In 1975 Annals of Mathematics Shelah interpreted true first-order arithmetic in the monadic theory of order under the assumption of the continuum hypothesis. The assumption is removed here.
The original problem was to find an algorithm deciding logical validity of sentences of the usual first-order logic.
I have long felt that, because it was posed as a cute problem about philosophers seated around a table, Dijkstra's dining philosopher's problem received much more attention than it deserves. (For example, it has probably received more attention in the theory community than the readers/writers…
During the late 70s and early 80s, Susan Owicki and I worked together quite a bit. We were even planning to write a book on concurrent program verification. But this paper is the only thing we ever wrote together. In [23], I had introduced a…
The mathematical description of three-dimensional surfaces usually falls in one of two classifications; parametric and algebraic. The algebraic form is defined as all points which satisfy some equation F(x,y,z)=0. This form is ideally suited for image space shaded picture drawing, the pixel coordinates are substituted…
Linkers, although a well-established component of language translation, are typically machine-dependent, idiosyncratic, and hard for many users to understand. This paper describes a machine-independent linker and object language. The linker embodies those linking functions that are machine-independent and centralizes them in a single tool, simplifying…
The design of voltage- or current-controlled active filters with operational transconductance amplifiers (OTA’s) is much less expensive than with analog multipliers. This paper presents some experimental results on known circuits and a new configuration which allows the electronic control of the absolute bandwidth of a…
I visited Michael Fischer at Yale in the spring of 1982. It was known that solutions to the Byzantine generals problem that can handle n Byzantine failures require n+1 rounds of communication. While I was at Yale, Fischer and I proved that this number of…
Grapevine is a multicomputer system on the Xerox research internet. It provides facilities for the delivery of digital messages such as computer mail; for naming people, machines, and services; for authenticating people and machines; and for locating services on the internet. This paper has two…
It is well known that the dramatic developments of the last few years in integrated circuit technology have revolutionised the approach taken to the provision of computer hardware. The use of many microcomputers with substantial amounts of memory is considered routine,and it is quite reasonable…
