@incollection{Cai/86,
AUTHOR = {Cai, J.},
TITLE = {With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {104},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=10},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Ko-Long-Du/86,
AUTHOR = {Ko, K. and Long, T. and Du, D.},
TITLE = {A note on one-way functions and polynomial time isomorphisms},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {196},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=19},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Krentel/86,
AUTHOR = {Krentel, M.},
TITLE = {The complexity of optimization problems},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {218},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=21},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Allender/86a,
AUTHOR = {Allender, E.},
TITLE = {The complexity of sparse sets in P},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {1-11},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=1},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Allender/86,
AUTHOR = {Allender, E.},
TITLE = {Isomorphisms and $1-L$ reductions},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {12-22},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=12},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Ambos-Spies/86c,
AUTHOR = {Ambos-Spies, K.},
TITLE = {Randomness, relativizations, and polynomial reducibilties},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {23-34},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=23},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Balcazar-Diaz-Gabarro/86,
AUTHOR = {Balc{\'a}zar, J. and D{\'i}az, J. and Gabarr{\'o}, J.},
TITLE = {On non-uniform polynomial space},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {35-50},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=35},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Boppana-Lagarias/86,
AUTHOR = {Boppana, R. and Lagarias, J.},
TITLE = {One-way functions and circuit complexity},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {51-65},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=51},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Buss/86,
AUTHOR = {Buss, J.},
TITLE = {Relativized alternation},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {66-76},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=66},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Buss/86a,
AUTHOR = {Buss, S.},
TITLE = {The polynomial hierarchy and intuitionistic bounded arithmetic},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {77-103},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=77},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Cai-Hemachandra/86,
AUTHOR = {Cai, J. and Hemachandra, L.},
TITLE = {The Booelan hierarchy},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {105-124},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=105},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Clote-Takeutei/86,
AUTHOR = {Clote, P. and Takeutei, G.},
TITLE = {Exponential time and bounded arithmetic},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {125-143},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=125},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Condon-Ladner/86,
AUTHOR = {Condon, A. and Ladner, R.},
TITLE = {Probabilistic game automata},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {144-162},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=144},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Dietzfelbinger-Maass/86,
AUTHOR = {Dietzfelbinger, M. and Maass, W.},
TITLE = {Two lower bound arguments with ``inaccessible'' numbers},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {163-183},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=163},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Huynh/86,
AUTHOR = {Huynh, D.},
TITLE = {Resource-bounded Kolmogorov complexity of hard languages},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {184-195},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=184},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Li-Longpre-Vitanyi/86,
AUTHOR = {Li, M. and Longpr{\'e}, L. and Vit{\'a}nyi, P.},
TITLE = {The power of the queue},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {219-233},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=219},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Lynch/86,
AUTHOR = {Lynch, J.},
TITLE = {A depth-size tradeoff for Boolean circuits with unbounded fan-in},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {234-248},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=234},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Maass-Schnitger/86,
AUTHOR = {Maass, W. and Schnitger, G.},
TITLE = {An optimal lower bound for Turing machines with one work tape and a two-way input tape},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {249-264},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=249},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{McAloon/86,
AUTHOR = {McAloon, K.},
TITLE = {Separation results for bounded alternation},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {265-271},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=265},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Parberry-Schnitger/86,
AUTHOR = {Parberry, I. and Schnitger, G.},
TITLE = {Parallel computation with threshold functions},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {272-290},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=272},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Regan/86,
AUTHOR = {Regan, K.},
TITLE = {The topology of provability in complexity theory},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {291-310},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=291},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Russo/86,
AUTHOR = {Russo, D.},
TITLE = {Optimal approximations of complete sets},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {311-324},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=311},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Sipser/86,
AUTHOR = {Sipser, M.},
TITLE = {Expanders, randomness, or time versus space},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {325-329},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=325},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Torenvliet-Boas/86,
AUTHOR = {Torenvliet, L. and Boas, P. van Emde},
TITLE = {Diagonalisation methods in a polynomial setting},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {330-346},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=330},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Tretkoff/86,
AUTHOR = {Tretkoff, C.},
TITLE = {Bounded oracles and complexity classes inside linear space},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {347-361},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=347},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Wilson/86,
AUTHOR = {Wilson, C.},
TITLE = {Parallel computation and the NC hierarchy relativized},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {362-382},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=362},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}
@incollection{Zachos/86,
AUTHOR = {Zachos, S.},
TITLE = {Probabilistic quantifiers, adversaries, and complexity classes},
BOOKTITLE = {Proceedings of the 1st Annual Conference on Structure in Complexity Theory, CSCT'86 (Berkeley, California, June 1986)},
SERIES = {LNCS},
VOLUME = {223},
PAGES = {383-400},
YEAR = {1986},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=223&spage=383},
PUBLISHER = {Springer-Verlag},
ORGANIZATION = {ACM SIGACT and IEEE Computer Society},
ADDRESS = {Berlin-Heidelberg-New York-London-Paris-Tokyo-Hong Kong},
}