Proceedings, Volume 14, Part 1999IEEE Computer Society Press, 1999 - Computational complexity |
From inside the book
Try this search over all volumes: LBSP
Results 1-0 of 0
Contents
Session | 3 |
Pseudorandom Generators without the XOR Lemma | 4 |
A Lower Bound for Primality | 10 |
Copyright | |
13 other sections not shown
Other editions - View all
Common terms and phrases
A₁ AC°-Frege ACM Symposium Ajtai algorithm assume b₁ bits Boolean functions complexity classes Computer Science constant construction defined Definition denote deterministic distribution encoding equations erasure code factor finite given Goldreich graph grid points h₁ h₂ hierarchy HVSZK IEEE induction input integer interactive proof systems isomorphism Kolmogorov complexity lattice point lattice vector least Lemma length linear linear span lower bound m-tt matrix monotone planar circuits nodes NP-complete NP-hard O(log obtain oracle orthogonal output pair parity pebbles polynomial polynomial hierarchy polynomial-time predicate prime prob probabilistic probability Proc promise problem proof of Theorem proof system protocol prove public-coin quantum computation queries random random-self-reducible reduction result Sample satisfying assignment Section sequence shortest vector simulator string subset subset sum problem subspace Theory of Computing tion Turing machine upper bound variables verifier zero-knowledge zero-knowledge proof