AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
Advances in Computational Complexity Theory
About this Title
Jin-yi Cai, Editor
Publication: DIMACS Series in Discrete Mathematics and Theoretical Computer Science
Publication Year:
1993; Volume 13
ISBNs: 978-0-8218-6597-2 (print); 978-1-4704-3971-2 (online)
DOI: https://doi.org/10.1090/dimacs/013
MathSciNet review: MR1255324
MSC: Primary 68-06
ReadershipTable of Contents
Front/Back Matter
Chapters
- Approximate counting with uniform constant depth circuits
- On strong separations from $AC^0$
- Parallel matching complexity of Ramsey’s theorem
- On algorithms for simple stochastic games
- Locally random reductions in interactive complexity theory
- An application of game theoretic techniques to cryptography
- Composition of the universal relation
- Practical perfect cryptographic security
- Fair games against an all-powerful adversary
- Factoring integers and computing discrete logarithms via diophantine approximation
- A new lower bound theorem for read only once branching programs and its applications
- On the E-isomorphism problem