## Proceedings of the ... Annual Structure in Complexity Theory Conference, Volume 2 |

### What people are saying - Write a review

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

### Contents

On Hiding Information from an Oracle | 9 |

Polynomial Terse Sets Extended Abstract | 22 |

The Probabilistic Communication Complexity of Set Intersection Preliminary | 41 |

Copyright | |

11 other sections not shown

### Common terms and phrases

accepting path algorithm attribute grammar auxiliary input binary boolean class of sets co-NP collapses complete sets complexity classes complexity theory Computer Science configuration confined acceptor conjecture construction Corollary define Definition denote deterministic deterministic Turing machine elements exists exponential EXPTIME formula given global relation graph Hartmanis Hence hierarchy IEEE implies infinite dimensional integer isomorphism Kolmogorov complexity L(Ma L(Mb L(Mi languages Lemma logspace membership Neil Immerman nondeterministic notion NP-complete one-way functions oracle machine oracle set oracle Turing machine output p-close p-isomorphic P-rankable p-selective P/poly polynomial hierarchy polynomial time computable polynomial-time predicate probabilistic problem Proposition prove PSPACE quantifier queries question r.e. sets recursive sets reducible relation over finite relativized robust self-reducible Selman sets in NP simulation sise small ranking circuits space sparse oracles sparse set stage strings of length structure subset subspace tape Threshold Circuits tion Turing machine