Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson
Abstract. The consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. In this paper, it...
Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson
Abstract. The consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. In this paper, it...
Optimal Layout of Edge-Weighted Forests (2007)
Michael Fischer Yale, Michael J. Fischer, Michael S. Paterson
The layout problem for trees with weighted edges is motivated by the design of very large scale integrated circuits. Some of the nodes are fixed and the object is to position the remainder so that...
Optimal Carry Save Networks (2007)
Michael S. Paterson, Nicholas Pippenger, Uri Zwick
A general theory is developed for constructing the asymptotically shallowest networks and the asymptotically smallest networks (with respect to formula size) for the carry save addition of n numbers...
Optimal Layout of Edge-Weighted Forests (2007)
Michael Fischer Yale, Michael J. Fischer, Michael S. Paterson
The layout problem for trees with weighted edges is motivated by the design of very large scale integrated circuits. Some of the nodes are xed and the object is to position the remainder so that the...
Layout of the Batcher Bitonic Sorter (2007)
Extend Ed, Shimon Even, S. Muthukrishnan, Michael S. Paterson, Suleyman Cenk S
) Shimon Even S. Muthukrishnan y Michael S. Paterson z Suleyman Cenk S . ahinalp x Abstract The grid-area required by a sorting net for input vectors of length N is shown to be at least (N \Gamma 1)...
Layout of the Batcher Bitonic Sorter (Extended Abstract) (2007)
Shimon Even, S. Muthukrishnan, Michael S. Paterson, Süleyman Cenk Sahinalp, Suleyman Cenk S
The grid-area required by a sorting net for input vectors of length N is shown to be at least (N \Gamma 1) 2 =2. Of all sorting nets which use o(N 2 ) comparators, the bitonic sorting net of Batcher...
NOTICE WARNING CONCERNING (2007)
Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson, Coventry England
Code] governs the making of photocopies or other reproductions of copyrighted material Under certain conditions specified in the law, libraries and archives are authorized to furnish a photocopy or...
Michael S. Paterson, Michael S. Paterson, Michael J. Fischer, Michael J. Fischer, Albert R. Meyer, Albert R. Meyer
A lower bound of cNlogN is proved for the mean time complexity of an on-line multitape Turing machine performing the multiplication of N-digit binary integers. For a more general class of machines...
Comparative schematology (2007)
Michael S. Patterson, Michael S. Paterson, Carl E. Hewitt, Carl E. Hewitt
While we may have the intuitive idea of one programming language having greater power thaQanother, or of some subset of a language being an adequate "core" for that thguage, we find...
Michael S. Paterson, Heiko Schroder
Abstract: We give a short proof that the dilation of an m \Theta n toroidal mesh in an mn-vertex path equals 2 minfm; ng, if m 6 = n and 2n \Gamma 1, if m = n.
Which Patterns Are Hard to Find? (2007)
Richard Cole, Ramesh Hariharan, Michael S. Paterson, Uri Zwick
The paper considers the exact number of character comparisons needed to find all occurrences of a pattern of length m in a text of length n using on-line and general algorithms. For on-line...
The complexity of mean payoff games (2007)
Uri Zwick, Michael S. Paterson
We study the complexity of nding the values and optimal strategies of mean payoff games, a family of perfect information games introduced by Ehrenfeucht and Mycielski. We describe a pseudo-polynomial...
Combinatorial and computational aspects of multiple weighted voting games (2007)
Aziz, Haris, Paterson, Michael S., Leech, Dennis
Weighted voting games are ubiquitous mathematical models which are used in economics, political science, neuroscience, threshold logic, reliability theory and distributed systems. They model...
An Improved Overlap Argument for On-Line Multiplication. (2005)
Paterson,Michael S., Fischer,Michael J., Meyer,Albert R.
A lower bound of cNlogN is proved for the mean time complexity of an on-line multitape. Turing machine performing the multiplication of N-digit binary integers. For a more general class of machines...
Identities from Partition Involutions. (2002)
Knuth,Donald E., Paterson,Michael S.
Prepared in cooperation with Warwick Univ., Conventry (England). Dept. of Computer Science.
Comparative Schematology. (2002)
Hewitt,Carl E., Paterson,Michael S.
While we may have the intuitive idea of one programming language having greater power than another, or of some subset of a language being an adequate 'core' for that language, we find when we try to...
Impossibility of Distributed Consensus with One Fault Process. (2002)
Fischer,Michael J., Lynch,Nancy A., Paterson,Michael S.
The consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. We show that every protocol...
Storage Requirements for Fair Scheduling. (2002)
Fischer,Michael J., Paterson,Michael S.
A scheduler is strongly fair if each process which requests service infinitely often is served infinitely often, and it is weakly fair if each process which requests service all but finitely often is...
Compact Grid Layouts of Some Multi-Level Networks (1999)
Muthukrishnan Michael, Michael S. Paterson, Torsten Suel
We consider the problem of generating layouts of multi-level networks, in particular, switching, sorting, and interconnection networks, as compactly as possible, that is, with minimum area, on VLSI...
Compact Grid Layouts of Some Multi-Level Networks (1999)
S. Muthukrishnan, Michael S. Paterson, Suleyman Cenk Sahinalp, Torsten Suel
We consider the problem of generating layouts of multi-level networks, in particular, switching, sorting, and interconnection networks, as compactly as possible, that is, with minimum area, on VLSI...
String-Matching and Other Products. (1998)
Fischer,Michael J., Paterson,Michael S.
The string-matching problem considered is to find all occurrences of a given pattern as a substring of another longer string. When the pattern is simply a given string of symbols, there is an...
Impossibility of Distributed Consensus with One Faulty Process. (1998)
Fischer,Michael J., Lynch,Nancy A., Paterson,Michael S.
The consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. We show that every protocol...
Secret Bit Transmission Using a Random Deal of Cards. (1998)
Fischer, Michael J., Paterson, Michael S., Rackoff, Charles
Protocols are developed and analyzed for transmitting a secret bit between a sender and a receiver process using only the information contained in a random deal of hands of specified sizes from a...
On Nearest-Neighbor Graphs (1997)
David Eppstein, Michael S. Paterson, Frances F. Yao
The "nearest neighbor" relation, or more generally the "k nearest neighbors" relation, defined for a set of points in a metric space, has found many uses in computational geometry...
Uri Zwick, Michael S. Paterson
The memory game, or concentration, as it is sometimes called, is a popular card game played by children and adults around the world. Good memory is one of the qualities required in order to succeed...
Shrinkage of de Morgan formulae under restriction (1993)
Michael S. Paterson, Coventry Cv Al, Uri Zwick
It is shown that a random restriction leaving only a fraction " of the input variables unassigned reduces the expected de Morgan formula size of the induced function by a factor of O("...
Can A Maximum Flow be Computed in o(nm) Time? (1990)
Cheriyan, Joseph, Hagerup, Torben, Mehlhorn, Kurt, Paterson, Michael S.
Michael J. Fischer, Nancy A Lynch, Michael S. Paterson
Abstract. The consensus problem involves an asvnchronous system ofproceses, some ofwhich may be unrcliable. The problem is for thc rcliablc processes to agr€e on a bbary value. h this pap€r, it...
Comparative Schematology (1970)
Paterson, Michael S., Hewitt, Carl E.
While we may have the intuitive idea of one programming language having greater power than another, or of some subset of a language being an adequate 'core' for that language, we find when we try to...
Comparative Schematology (1970)
Paterson, Michael S., Hewitt, Carl E.
While we may have the intuitive idea of one programming language having greater power than another, or of some subset of a language being an adequate 'core' for that language, we find when we try to...