Proceedings: 31st Annual Symposium on Foundations of Computer Science : October 22-24, 1990, St. Louis, Missouri, Volume 2 |
Contents
Competitive kServer Algorithms | 454 |
Randomized Online Graph Coloring | 463 |
Online Algorithms for Finger Searching | 480 |
Copyright | |
47 other sections not shown
Common terms and phrases
assume augmentation automata automaton bits block Boolean functions C₁ chordal graph color communication complexity Computer Science configuration consider constant construct corresponding cost decomposition defined Definition denote depth deterministic distribution down-tree edge-connectivity elements encoding equation exists finite formula func gates given graph G h₁ IEEE input integer iterations k-server algorithm Lemma linear logic logn lower bound machine matrix minimal minimum multiple nested radical node NP-complete number of edges O(log obtained on-line one-way function optimal output P₁ pair Paley Graph path phase polynomial PRAM prob probability problem Proc processors Proposition protocol prove PSPACE-complete random ratio rational function reduction result rithm root S₁ satisfies sequence servers simulation solution solve step string subset synchronization t-sparse TFNP Theory threshold circuit tion tree Turing machine undirected graph variables vector vertex vertices