Proceedings: Structure in Complexity Theory Third Annual Conference (Cat. No.88CH2542-9)

fYear

1988

fDate

14-17 June 1988

Abstract

The following topics are dealt with: counting; tally relativization of BP-complexity classes; relationships between communication complexity classes; downward closures; logspace self-reducibility; uniformity within NC¹; automata prediction problems; alternation; Kolmogorov complexity; complementation; retrospectives on Juris Harmanis; multipower interactive protocols; probabilistic game automata; pseudorandom sources for BPP; bounded reducibilities; complexity of ranking; truth-table reducibility; polynomial and generalized complexity cores; polynomial-query computations; and reducibilities in NP. Abstracts of individual papers can be found under the relevant classification codes in this or other issues.

Keywords

automata theory; computational complexity; BP-complexity classes; Kolmogorov complexity; NP; alternation; automata prediction problems; bounded reducibilities; communication complexity classes; complementation; complexity of ranking; counting; downward closures; logspace self-reducibility; multipower interactive protocols; polynomial-query computations; probabilistic game automata; pseudorandom sources; tally relativization; truth-table reducibility; uniformity;

fLanguage

English

Publisher

ieee

Conference_Titel

Structure in Complexity Theory Conference, 1988. Proceedings., Third Annual

Conference_Location

Washington, DC, USA

Print_ISBN

0-8186-0866-8

Type

conf

DOI

10.1109/SCT.1988.5266

Filename

5266