Advances in Computational Complexity Theory

Front Cover
Jin-yi Cai
American Mathematical Soc., Jan 1, 1993 - Mathematics - 209 pages
0 Reviews
* 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
Copyright

Common terms and phrases