## Proceedings |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Session | 3 |

Pseudorandom Generators without the XOR Lemma | 4 |

A Lower Bound for Primality | 10 |

Copyright | |

16 other sections not shown

### Other editions - View all

### Common terms and phrases

ACM Symposium Ajtai algorithm assume basis block Boolean functions complexity classes Computational Complexity Computer Science consider constant construction Corollary defined Definition denote deterministic dimension distribution encoding equations erasure code exists exponential factor fan-in finite Frege given Goldreich graph grid points hierarchy HVSZK IEEE induction input integer interactive proof systems intervals isomorphism Kolmogorov complexity lattice point least Lemma linear linear span lower bound matrix monotone planar circuits multiplication gates nodes NP-complete NP-hard 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-self-reducible reduction result Sample satisfying assignment Section semilattice sequence shortest vector simulator solution subset subset sum problem subspace tape Theory of Computing tion Turing machine upper bound variables verifier Wigderson zero zero-knowledge zero-knowledge proof