## Advances in Computational Complexity Theory* Recent papers on computational complexity theory * Contributions by some of the leading experts in the field This book will prove to be of lasting value in this fast-moving field as it provides expositions not found elsewhere. The book touches on some of the major topics in complexity theory and thus sheds light on this burgeoning area of research. |

### What people are saying - Write a review

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

### Contents

On Strong Separations from | 21 |

Parallel Matching Complexity of Ramseys Theorem | 39 |

On Algorithms for Simple Stochastic Games | 51 |

Locally Random Reductions in Interactive Complexity Theory | 73 |

An Application of GameTheoretic Techniques to Cryptography | 99 |

Composition of the Universal Relation | 119 |

Practical Perfect Cryptographic Security | 135 |

Fair Games against an AilPowerful Adversary | 155 |

Factoring Integers and Computing Discrete Logarithms | 171 |

A New Lower Bound Theorem for ReadOnlyOnce Branching | 183 |

On the EIsomorphism Problem | 195 |

### Common terms and phrases

adversary matches algorithm Alice and Bob approximation assume assumption binary branching programs chooser pile circuit complexity class Complexity Theory Computer Science conjecture consider construction cryptographic definition denote edges error probability exist expander graphs exponential feasible Feigenbaum first-order definable Fortnow function f game G graph Hence immune to AC implies induction inequality input instance-hiding integer interactive proof systems iteration key set protocol lattice vectors leaf least Lemma length linear programming lower bound Mathematics Subject Classification matrices max nodes monochromatic nonadaptive nontrivial oblivious transfer one-one one-way function oracle output p-completely p-invertible p-paddable pair polynomial polynomial-time computable prime probabilistic problem Proc prove PSPACE queries random variable reduction secret key sequence set in NP sink nodes size(C stick game stochastic games strategy strategy-stealing argument string subset team player Theorem Turing machines vertex winning zero-knowledge zero-knowledge proof