Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing: San Diego, California, May 16-18, 1993, Volume 25 |
Contents
Sunday May 16 | 1 |
Quantum Complexity Theory | 11 |
Thermodynamics of Computation and Information Distance | 21 |
Copyright | |
69 other sections not shown
Common terms and phrases
algorithm antichain approximation assignment assume asynchronous Blum integers Boolean coloring column competitive ratio complexity Computer Science consider constant constraints construction copy cost data structure defined definition denote depth deterministic distribution edges execution exists faults finite fixed function gate given Graph Coloring graph G honest player hypergraph input integer iteration k-cut label learning least Lemma length linear linear program lower bound machine mapping matching matrix maximum node NP-complete NP-hard O(log on-line optimal oracle output parameter parties path phase planar planar graph polynomial polynomial-time prediction 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 Turing machine upper bound variables VC dimension vector vertex vertices weights