## Proceedings of the ...ACM Symposium on Theory of Computing, Volume 25Association for Computing Machinery, 1993 - Sequential machine theory |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Sunday May 16 1993 | 1 |

Quantum Complexity Theory | 11 |

Thermodynamics of Computation and Information Distance | 21 |

Copyright | |

58 other sections not shown

### Other editions - View all

### Common terms and phrases

algorithm antichain approximation assignment assume asynchronous Blum integers Boolean coloring column competitive ratio complexity Computer Science consider constant constraints construction convex copy cost data structure define definition denote depth deterministic distribution edges execution exists faults finite fixed function gate given Graph Coloring graph G Hence honest player hypergraph input integer iteration label least Lemma length linear linear program logn lower bound machine mapping Markov chain matching matrix maximum node NP-complete O(logn on-line optimal oracle output p-suffix parameter parties path phase planar planar graph polynomial polynomial-time prediction prob probability problem Proc processor proof protocol prove PSPACE queries randomized algorithm recursive rithm satisfies schedule sequence shared simulate space step STOC string subset subtree task Theorem Theory tion total number tree treewidth tuple upper bound variables VC dimension vector vertex vertices weights