%A Uwe Schoning
%T Lowness and probabilistic complexity classes
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Martin Abadi
%A Joan Feigenbaum
%A Joe Kilian
%T On hiding information from an oracle
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Sophocles Ephremidis
%A Christos Papadimitriou
%A Martha Sideris
%T Complexity characterizations of attribute grammar languages
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Jian-er Chen
%A Chee-Keng Yap
%T Reversal complexity
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Amihood Amir
%A William I. Gasarch
%T Polynomial terse sets
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Richard Beigel
%T A structural theorem that depends quantitatively on the complexity of SAT
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Jim Kadin
%T P^NP[log n] and sparse turing complete sets for NP
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Georg Schnitger
%A Balasubramanian Kalyanasundaram
%T The probabilistic communication complexity of set intersection
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Judy Goldsmith
%A Deborah Joseph
%A Paul Young
%T Near-testable, P-cheatable, and P-terse sets
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Klaus Ambos-Spies
%T Honest polynomial reducibilities, recursively enumerable sets,
and the P=?NP problem
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Kenneth W. Regan
%T Unprovably intractable languages
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Jack H. Lutz
%T Resource bounded baire category and small circuits in exponential space
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Jin-Yi Cai
%A Merrick L. Furst
%T PSPACE survives three-bit bottlenecks
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Lane A. Hemachandra
%T On ranking
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A John Reif
%T On threshold circuits and polynomial computation
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Juris Hartmanis
%A Lane Hemachandra
%T One-way functions, robustness, and the non-isomorphism of NP-complete sets
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Moon Jung Chung
%A B. Ravikumar
%T Strong nondeterministic reduction - a technique for proving intractability
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Osamu Watanabe
%T Polynomial time reducibility to a set of small density
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Ronald V. Book
%A Ker-I Ko
%T On sets reducible to sparse sets
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Lance Fortnow
%T The complexity of perfect zero-knowledge
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Eric W. Allender
%T Some consequences of the existence of pseudorandom generators
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Stuart Kurtz
%A Stephen Mahaney
%A James Royer
%T Progress on collapsing degrees
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Jonathan F. Buss
%T A theory of oracle machines
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Ker-I Ko
%T On helping by robust oracle machines
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Lane A. Hemachandra
%T The strong exponential hierarchy collapses
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Neil Immerman
%T Expressibility as a complexity measure: results and directions
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Daniel Leivant
%T Characterization of complexity classes in higher-order logic
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2

%A Anil Nerode
%A J.B. Remmel
%T Complexity theoretic algebra I - vector spaces over finite fields
%J Proceedings of the Second Annual Conference on Structure in Complexity Theory
%C Cornell, Ithaca, New York
%D June 1987
%K sict sict2