What people are saying - Write a review
We haven't found any reviews in the usual places.
Towards Uniform ACIsomorphisms
Comparing Notions of Full Derandomization
Space Complexity of Random Formulae in Resolution
19 other sections not shown
Other editions - View all
accepts access structure algorithm approximate binary bits block Boolean circuit Boolean function circuit complexity classical clause codewords communication complexity complexity classes Computer Science concept class constant construction contains Corollary decision tree define Definition denote depth derandomization deterministic dimension edges element encoder exists exponential finite formula Fortnow gates given Hence hypothesis IEEE implies independent set induced input integer Kolmogorov complexity least Lemma length linear lower bounds matrix modulo monomials monotone NEXP node nondeterministic oracle output P/poly plexity polynomial polynomial-time probabilistic probability problem proof of Theorem protocol prove pseudorandom quadratic residue quadratic residuosity quantum quantum computer qubit queries query complexity random reducible resolution proof restriction result satisfies secret-sharing scheme sequence simulation space span program string subset Switching Lemma symmetric tion Turing machine upper bound variables VC dimension vector vertex vertices Wigderson