What people are saying - Write a review
We haven't found any reviews in the usual places.
Inequalities for Shannon Entropies and Kolmogorov Complexities
Circuits Over PP and PL
The General Notion of a DotOperator
26 other sections not shown
Other editions - View all
Alice and Bob alternating Turing machine approximation assignment assume Beigel binary bits Boolean circuits Boolean function bottom fan-in checker clauses complexity classes Complexity Theory consider constant constraint Corollary database datalog defined Definition denote depth deterministic distribution dot-operators elements equivalent exists exponential fan-in finite FPNP function f gates given graph Group Intersection groupoid hierarchy IEEE inequality input instance integer Johnson's Algorithm Kolmogorov complexities language leaf Lemma length linear logic programming lower bound mapping Max-Sat mixed strategy MODm NEXPTIME node nondeterministic Note NP-complete obtain online algorithms oracle output perceptron permutation player polyabelian polynomial polynomial hierarchy polynomial-time probabilistic Proc proof of Theorem protocol prove PSPACE queries random reducibility resp satisfied Section sequence simulation solvable space strategy string subset Symposium Theoretical Computer Science tion Turing machine uniform upper bound variables vector WEIGHT