@InProceedings(pippenger,
Author= "Pippenger, N.",
Title= "On simultaneous resource bounds",
BookTitle= "Proc. of 20th FOCS",
Year= "1979",
Pages= "307-311")
@Article{pippenger.fischer,
author = {N. Pippenger and M. Fischer},
title = {Relations among complexity measures},
journal = {Journal of the Association for Computing Machinery},
year = 1979,
volume = 26,
pages = {361-381}
}
@Article{tra61,
author = {B. A. Trakhtenbrot},
title = {Finite automata and logic of monadic predicates},
journal = {Doklady Akademii Nauk SSSR},
year = 1961,
volume = 140,
pages = {326-329},
note = {In Russian.}
}
@Article{gule84,
author = {Y. Gurevich and H. Lewis},
title = {A logic for constant-depth circuits},
journal = {Information and Control},
year = 1984,
volume = 61,
pages = {65-74}
}
@InProceedings{agal96,
author = {M. Agrawal and E. Allender},
title = {An isomorphism theorem for circuit complexity},
booktitle = {Proceedings 11th Computational Complexity},
year = 1996,
publisher = {IEEE Computer Society},
pages = {2-11}
}
@InProceedings{heho90,
author = {L. A. Hemachandra and A. Hoene},
title = {On sets with efficient implicit membership tests},
booktitle = {5th Structure in Complexity Theory},
year = 1990,
publisher = {IEEE Computer Society Press},
pages = {11-19}
}
@InProceedings{agalda97,
author = {M. Agrawal and E. Allender and S. Datta},
title = {On {TC$^0$}, {AC$^0$}, and arithmetic circuits},
booktitle = {Proceedings 12th Computational Complexity},
year = 1997,
publisher = {IEEE Computer Society},
pages = {134-148y}
}
@Book{mei86,
author = {C. Meinel},
title = {Modified Branching Programs and Their Computational Power},
publisher = {Springer Verlag},
year = 1986,
volume = 370,
series = {Lecture Notes in Computer Science},
address = {Berlin Heidelberg}
}
@Article{lee59,
author = {C. Y. Lee},
title = {Representation of switching functions by binary decision programs},
journal = {Bell Systems Technical Journal},
year = 1959,
volume = 38,
pages = {985-999}
}
@InProceedings{agetal97,
author = {M. Agrawal and E. Allender and R. Impagliazzo and R. Pitassi and S. Rudich},
title = {Reducing the complexity of reductions},
booktitle = {Proceedings 29th Symposium on Theory of Computing},
year = 1997,
publisher = {ACM Press},
pages = {XXX-YYY}
}
@article{ajt83,
author = {M. Ajtai},
journal = {Annals of Pure and Applied Logic},
pages = {1-48},
title = {{$\Sigma^1_1$} formulae on finite structures},
volume = 24,
year = 1983
}
@InProceedings{albeog96,
author = {E. Allender and R. Beals and M. Ogihara},
title = {The complexity of matrix rank and feasible systems of linear equations (extended abstract)},
booktitle = {Proceedings 28th Symposium on Theory of Computing},
year = 1996,
publisher = {ACM Press},
pages = {161-167}
}
@InProceedings{algo90,
author = {E. Allender and V. Gore},
title = {On strong separations from {AC$^0$}},
booktitle = {Proceedings 8th Fundmentals of Computation Theory},
volume = 529,
series = {Lecture Notes in Computer Science},
year = 1991,
pages = {1-15},
publisher = {Springer Verlag}
}
@Article{algo91,
author = {E. Allender and V. Gore},
title = {Rudimentary reductions revisited},
journal = {Information Processing Letters},
year = 1991,
volume = 40,
pages = {89-95}
}
@Article{algo94,
author = {E. Allender and V. Gore},
title = {A uniform circuit lower bound for the permanent},
journal = {SIAM Journal on Computing},
year = 1994,
volume = 23,
pages = {1026-49}
}
@Article{alhe94,
author = {E. Allender and U. Hertrampf},
title = {Depth reduction for circuits of unbounded fan-in},
journal = {Information \& Computation},
year = 1994,
volume = 112,
pages = {217-238}
}
@article{alje93,
author = {C. \`{A}lvarez and B. Jenner},
journal = {Theoretical Computer Science},
pages = {3-30},
title = {A Very Hard Log Space Counting Class},
volume = 107,
year = 1993
}
@Article{all89,
author = {E. Allender},
title = {P-uniform circuit complexity},
journal = {Journal of the Association for Computing Machinery},
year = 1989,
volume = 36,
pages = {912-928}
}
@InProceedings{all90,
author = {E. Allender},
title = {Oracles versus proof techniques that do not relativize},
booktitle = {Proceedings 1st International Symposium on Algorithms},
volume = 450,
series = {Lecture Notes in Computer Science},
year = 1990,
publisher = {Springer Verlag},
pages = {39--52}
}
@Unpublished{all95,
author = {E. Allender},
title = {Combinatorial Methods in Complexity Theory},
note = {Lecture Notes, Rutgers University New Brunswick. Available on the internet at URL http://www.cs.rutgers.edu/$\sim$allender},
year = 1995
}
@InProceedings{all96,
author = {E. Allender},
title = {A note on uniform circuit lower bounds for the counting hierarchy},
booktitle = {Proceedings 2nd Computing and Combinatorics Conference},
volume = 1090,
series = {Lecture Notes in Computer Science},
year = 1996,
publisher = {Springer Verlag},
pages = {127-135}
}
@InProceedings{all96b,
author = {E. Allender},
title = {Circuit complexity before the dawn of the new millenium},
booktitle = {Proceedings 16th Foundations of Software Technology and Theoretical Computer Science},
volume = 1180,
series = {Lecture Notes in Computer Science},
year = 1996,
publisher = {Springer Verlag},
pages = {1--18}
}
@Article{alwa90,
author = {E. Allender and K. W. Wagner},
title = {Counting hierarchies: polynomial time and constant
depth circuits},
journal = {Bulleting of the EATCS},
year = 1990,
volume = 40,
pages = {182-194}
}
@InProceedings{amb86,
author = {K. Ambos-Spies},
title = {Randomness, relativizations, and polynomial reducibilities},
booktitle = {Proceedings 1st Structure in Complexity
Theory},
volume = 223,
series = {Lecture Notes in Computer Science},
year = 1986,
publisher = {Springer Verlag},
pages = {200-207}
}
@InProceedings{arlumo+92,
author = {S. Arora and C. Lund and R. Motwani and M. Sudan and
M. Szegedy},
title = {Proof verification and the intractability of
approximation problems},
booktitle = {Proceedings 33rd Symposium on the Foundations of
Computer Science},
year = 1992,
publisher = {IEEE Computer Society Press},
pages = {14-23}
}
@Article{sud78,
author = {I. H. Sudborough},
title = {On the tape complexity of deterministic context-free languages},
journal = {Journal of the ACM},
year = 1978,
volume = 25,
pages = {405-414}
}
@PhdThesis{vin91,
author = {V. Vinay},
title = {Semi-Unboundedness and Complexity Classes},
school = {Department of Computer Science and Automation, Indian Institute of Science},
year = 1991,
address = {Bangalore, India}
}
@InProceedings{asbefuru91,
author = {J. Aspnes and R. Beigel and M. Furst and S. Rudich},
title = {The expressive power of voting polynomials},
booktitle = {Proceedings 23rd Symposium on Theory of Computing},
year = 1991,
publisher = {ACM Press},
pages = {402-409}
}
@InProceedings{bab85,
author = {L. Babai},
title = {Trading group theory for randomness},
booktitle = {Proceedings 17th Symposium on Theory of Computing},
year = 1985,
publisher = {ACM Press},
pages = {421-429}
}
@Article{bab87,
author = {L. Babai},
title = {Random oracles separate {PSPACE} from the
polynomial-time hierarchy},
journal = {Information Processing Letters},
year = 1987,
volume = 26,
pages = {51-53}
}
@InProceedings{bab93,
author = {L. Babai},
title = {Transparent (holographic) proofs},
booktitle = {Proceedings 10th Symposium on Theoretical Aspects of Computer Science},
volume = 665,
series = {Lecture Notes in Computer Science},
year = 1993,
publisher = {Springer Verlag},
pages = {525-534}
}
@Article{baberu94,
author = {D. A. Mix Barrington and R. Beigel and S. Rudich},
title = {Representing boolean functions as polynomials modulo composite numbers},
journal = {Computational Complexity},
year = 1994,
volume = 4,
pages = {367-382}
}
@Book{badiga90,
author = {J. L. Balc\'azar and J. D{\'\i}az and J. Gabarr\'o},
publisher = {Springer Verlag},
title = {Structural Complexity II},
series = {Monographs on Theoretical Computer Science},
year = 1990,
address = {Berlin Heidelberg}
}
@Book{badiga95,
author = {J. L. Balc\'azar and J. D{\'\i}az and J. Gabarr\'o},
publisher = {Springer Verlag},
title = {Structural Complexity I},
series = {Texts in Theoretical Computer Science},
year = 1995,
edition = {2nd},
address = {Berlin Heidelberg}
}
@InProceedings{bafolesz91,
author = {L. Babai and L Fortnow and L. A. Levin and M. Szegedy},
title = {Checking computations in polylogarithmic time},
booktitle = {Proceedings 23rd Symposium on Theory of Computing},
year = 1991,
publisher = {ACM Press},
pages = {21-32}
}
@InProceedings{bafolu90,
author = {L. Babai and L. Fortnow and C. Lund},
title = {Non-deterministic exponential time has two-prover interactive protocols},
booktitle = {Proceedings 31st Symposium on Foundations of Computer Science},
year = 1990,
publisher = {IEEE Computer Society Press},
pages = {16-25}
}
@ARTICLE{bafolu91,
AUTHOR = "Babai, L. and L. Fortnow and C. Lund",
TITLE = "Non-deterministic Exponential Time has Two-Prover Interactive
Protocols",
journal = "Computational Complexity",
YEAR = "1991",
Volume = 1,
number = 1,
pages = "3-40"}
@Unpublished{bai97,
author = {H. Baier},
title = {Type-1 probabilistic bounded-error operators},
note = {Manuscript},
year = 1997
}
@InProceedings{baim94,
author = {D. A. Mix Barrington and N. Immerman},
title = {Time, hardware, and uniformity},
booktitle = {Proceedings 9th Structure in Complexity Theory},
year = 1994,
publisher = {IEEE Computer Society Press},
pages = {176-185}
}
@Article{baimst90,
author = {D. A. Mix Barrington and N. Immerman and H. Straubing},
title = {On uniformity within {NC$^1$}},
journal = {Journal of Computer and System Sciences},
year = 1990,
volume = 41,
pages = {274-306}
}
@InCollection{baloto92,
author = {J. L. Balc\'azar and A. Lozano and J. Tor\'an},
title = {The complexity of algorithmic problems on succinct instances},
booktitle = {Computer Science},
publisher = {Plenum Press},
year = 1992,
editor = {R. Baeza-Yates and U. Manber},
address = {New York}
}
@Article{bar89,
author = {D. A. Mix Barrington},
title = {Bounded-width polynomial size branching programs recognize exactly those languages in {NC$^1$}},
journal = {Journal of Computer and System Sciences},
year = 1989,
volume = 38,
pages = {150-164}
}
@InProceedings{bar92,
author = {D. A. Mix Barrington},
title = {Quasipolynomial size circuit classes},
booktitle = {Proceedings 7th Structure in Complexity Theory},
year = 1992,
publisher = {IEEE Computer Society Press},
pages = {86-93}
}
@Article{bath88,
author = {D. A. Mix Barrington and D. Th\'erien},
title = {Finite monoids and the fine structure of {NC}$^1$},
journal = {Journal of the Association of Computing Machinery},
year = 1988,
volume = 35,
pages = {941-952}
}
@TechReport{bawa96,
author = {H. Baier and K. W. Wagner},
title = {The analytic polynomial-time hierarchy},
institution = {Institut f\"ur Informatik},
year = 1996,
number = {148},
address = {Universit\"at W\"urzburg}
}
@TechReport{bawa97,
author = {H. Baier and K. W. Wagner},
title = {Bounding queries in the analytical polynomial-time hierarchy},
institution = {Institut f\"ur Informatik},
year = 1997,
number = 178,
address = {Universit\"at W\"urzburg}
}
@Article{bawa98,
author = {H. Baier and K. W. Wagner},
title = {The analytic polynomial-time hierarchy},
journal = {Mathematical Logic Quaterly},
year = 1998,
volume = 44,
pages = {529-544}
}
@Article{bawa98b,
author = {H. Baier and K. W. Wagner},
title = {Bounding queries in the analytical polynomial-time hierarchy},
journal = {Theoretical Computer Science},
year = 1998,
volume = 207,
pages = {89-104}
}
@InProceedings{bedrlemoth97,
author = {J. Berman and A. Drisko and F. Lemieux and C. Moore and D. Th\'erien},
title = {Circuits and expressions with non-associative gates},
booktitle = {Proceedings 12th Computational Complexity},
year = 1996,
publisher = {IEEE Computer Society},
pages = {193-203}
}
@Article{begi81,
author = {C. Bennett and J. Gill},
title = {Relative to a random oracle
{P$^A$ $\neq$ NP$^A$ $\neq$ coNP$^A$} with probability 1},
journal = {SIAM Journal on Computing},
year = 1981,
volume = 10,
pages = {96-113}
}
@InProceedings{begihe90,
author = {R. Beigel and J. Gill and U. Hertrampf},
title = {Counting classes: thresholds, parity, mods, and fewness},
booktitle = {Proceedings 7th Symposium on Theoretical Aspects of
Computer Science},
volume = 415,
series = {Lecture Notes in Computer Science},
year = 1990,
publisher = {Springer Verlag},
pages = {49-57}
}
@Article{begiso75,
author = {T. Baker and J. Gill and R. Solovay},
title = {Relativizations of the {P=NP} problem},
journal = {SIAM Journal on Computing},
year = 1975,
volume = 4,
pages = {431-442}
}
@Article{beha77,
author = {L. Berman and J. Hartmanis},
title = {On isomorphism and density of {NP} and other
complete sets},
journal = {SIAM Journal on Computing},
year = 1977,
volume = 6,
pages = {305-322}
}
@InProceedings{bei93,
author = {R. Beigel},
title = {The polynomial method in circuit complexity},
booktitle = {Proceedings 8th Structure in Complexity Theory},
year = 1993,
publisher = {IEEE Computer Society Press},
pages = {82-95},
note = {Revised version, 1995.}
}
@Article{bei94,
author = {R. Beigel},
title = {Perceptrons, {$\PP$}, and the polynomial hierarchy},
journal = {Computational Complexity},
year = 1994,
volume = 4,
pages = {339-349}
}
@Article{belemc93,
author = {F. B{\'e}dard and F. Lemieux and P. McKenzie},
title = {Extensions to {Barrington's} {M}-program model},
journal = {Theoretical Computer Science},
year = 1993,
volume = 107,
pages = {31-61}
}
@InProceedings{bemc92,
author = {M. Beaudry and P. McKenzie},
title = {Circuits, matrices, and nonassociative computation},
booktitle = {Proceedings 7th Structure in Complexity Theory},
year = 1992,
publisher = {IEEE Computer Society},
pages = {94-106}
}
@Book{ber79,
author = {J. Berstel},
title = {Transductions and Context-Free Languages},
publisher = {Teubner},
year = 1979,
volume = 38,
series = {Leitf\"aden der angewandten Mathematik und Mechanik LAMM}
}
@InProceedings{beresp91,
author = {R. Beigel and N. Reingold and D. Spielman},
title = {{PP} is closed under intersection},
booktitle = {Proceedings 23rd Symposium on Theory of Computing},
year = 1991,
publisher = {ACM Press},
pages = {1-9}
}
@InProceedings{beresp91b,
author = {R. Beigel and N. Reingold and D. Spielman},
title = {The perceptron strikes back},
booktitle = {Proceedings 6th Structure in Complexity Theory},
year = 1991,
publisher = {IEEE Computer Society Press},
pages = {286-291}
}
@Article{beta94,
author = {R. Beigel and J. Tarui},
title = {On {ACC}},
journal = {Computational Complexity},
year = 1994,
volume = 4,
pages = {350-366},
note = {Special issue on circuit complexity}
}
@InProceedings{beul97,
author = {C. Berg and S. Ulfberg},
title = {A lower bound for perceptrons and an oracle separation of the {$\PP^{\PH}$} hierarchy},
booktitle = {Proceedings 12th Conference on Computational Complexity},
year = 1997,
publisher = {IEEE Computer Society Press},
pages = {165-172}
}
@Article{blgu82,
author = {A. Blass and Y. Gurevich},
title = {On the unique satisfiability problem},
journal = {Information and Control},
year = 1982,
volume = 82,
pages = {80-88}
}
@Article{blgu86,
author = {A.Blass and Y. Gurevich},
title = {Henkin quantifiers and complete problems},
journal = {Annals of Pure and Applied Logic},
year = 1986,
volume = 32,
pages = {1-16}
}
@Article{blu84,
author = {N. Blum},
title = {A {B}oolean function requiring $3n$ network size},
journal = {Theoretical Computer Science},
year = 1984,
volume = 36,
pages = {59-70}
}
@Article{bocl92,
author = {M. Ben-Or and R. Cleve},
title = {Computing algebraic formulas using a constant number of registers},
journal = {SIAM Journal on Computing},
year = 1992,
volume = 21,
pages = {54-58}
}
@Book{bocr94,
author = {D. P. Bovet and P. Crescenzi},
title = {Introduction to the Theory of Complexity},
publisher = {Prentice Hall},
address = {London},
year = 1994,
series = {International Series in Computer Science},
}
@InProceedings{bocrsi91,
author = {D. P. Bovet and P. Crescenzi and R. Silvestri},
title = {Complexity classes and sparse oracles},
booktitle = {Proceedings 6th Structure in Complexity Theory},
year = 1991,
publisher = {IEEE Computer Society Press},
pages = {102-108}
}
@Article{bocrsi92,
author = {D. P. Bovet and P. Crescenzi and R. Silvestri},
title = {A uniform approach to define complexity classes},
journal = {Theoretical Computer Science},
year = 1992,
volume = 104,
pages = {263-283}
}
@article{boetal89,
author = {A. Borodin and S. A. Cook and P. W. Dymond and W. L. Ruzzo and M. Tompa},
title = {{Two} applications of inductive counting for complementation problems},
journal = {SIAM Journal on Computing},
pages = {559--578},
volume = 18,
year = 1989,
note = {See Erratum in SIAM J. Comput.~18, 1283}
}
@TechReport{bokust96,
author = {B. Borchert and D. Kuske and F. Stephan},
title = {On existentially first-order definable languages and their relation to {NP}},
institution = {Institut f\"ur Algebra, Technische Universit\"at Dresden},
year = 1996,
number = {MATH-AL-11-1996}
}
@Article{bola96,
author = {B. Borchert and A. Lozano},
title = {Succinct Circuit Representations and
Leaf Language Classes are Basically the Same Concept},
journal = {Information Processing Letters},
year = 2996,
volume = 58,
pages = {211-215}
}
@Article{bolo96,
author = {B. Borchert and A. Lozano},
title = {Succinct circuit representations and leaf language
classes are basically the same concept},
journal = {Information Processing Letters},
year = 1996,
volume = 58,
pages = {211-215}
}
@Article{bolose84,
author = {R. V. Book and T. Long and A. Selman},
title = {Quantitative relativizations of complexity classes},
journal = {SIAM Journal on Computing},
year = 1984,
volume = 13,
pages = {461-487}
}
@Article{boluma95,
author = {R. V. Book and J. Lutz and D. Martin},
title = {The global power of additional queries to random oracles},
journal = {Information and Computation},
year = 1995,
volume = 120,
pages = {49-54}
}
@InProceedings{boluta91,
author = {R. V. Book and J. Lutz and S. Tang},
title = {Additional queries to random and pseudorandom oracles},
booktitle = {Proceedings 17th International Colloquium on
Automata, Languages and Programming},
volume = 443,
series = {Lecture Notes in Computer Science},
year = 1991,
publisher = {Springer Verlag},
pages = {283-293}
}
@Article{boluwa94,
author = {R. V. Book and J. Lutz and K. W. Wagner},
title = {An observation on probability versus randomness with
applications to complexity classes},
journal = {Mathematical Systems},
year = 1994,
volume = 27,
pages = {201-209}
}
@Article{boma96,
author = {R. V. Book and E. Mayordomo},
title = {On the robustness of {Almost-{\cal R}}},
journal = {R.A.I.R.O. Informatique Th\'eoretique et Applications},
year = 1996,
note = {To appear.}
}
@Article{boo74,
author = {R. V. Book},
title = {Tally languages and complexity classes},
journal = {Information and Control},
year = 1974,
volume = 26,
pages = {186-194}
}
@Article{boo81,
author = {R. V. Book},
title = {Bounded query machines: On {NP} and {PSPACE}},
journal = {Theoretical Computer Science},
year = 1981,
volume = 15,
pages = {27-39}
}
@InCollection{boo89,
author = {R. V. Book},
title = {Restricted relativizations of complexity classes},
booktitle = {Computational Complexity Theory},
publisher = {American Mathematical Society},
year = 1989,
editor = {J. Hartmanis},
volume = 38,
series = {Proceedings Symposia in Applied Mathematics},
pages = {47-74}
}
@Article{boo91a,
author = {R. V. Book},
title = {On random oracle separations},
journal = {Information Processing Letters},
year = 1991,
volume = 39,
pages = {7-10}
}
@Article{boo91b,
author = {R. V. Book},
title = {Some observations on separating complexity classes},
journal = {SIAM Journal on Computing},
year = 1991,
volume = 20,
pages = {246-258}
}
@InProceedings{boo93,
author = {R. V. Book},
title = {Relativizing complexity classes with random oracles},
booktitle = {Proceedings 4th International Symposium on
Algorithms and Computation},
volume = {762},
series = {Springer Lecture Notes in Computer Science},
year = 1993,
pages = {250--258}
}
@Article{boo94a,
author = {R. V. Book},
title = {On languages reducible to algorithmically random languages},
journal = {SIAM Journal on Computing},
year = 1994,
volume = 23,
pages = {1275-1282}
}
@Article{boo94b,
author = {R. V. Book},
title = {On collapsing the polynomial-time hierarchy},
journal = {Information Processing Letters},
year = 1994,
volume = 52,
pages = {235-237}
}
@Article{bor77,
author = {A. B. Borodin},
title = {On relating time and space to size and depth},
journal = {SIAM Journal on Computing},
year = 1977,
volume = 6,
pages = {733-744}
}
@PhdThesis{bor94,
author = {B. Borchert},
title = {Predicate classes, promise classes, and the
acceptance power of regular languages},
school = {Naturwissenschaftlich-Mathematische Fakult\"at, Universit\"at Heidelberg},
year = 1994
}
@InProceedings{bor94b,
author = {B. Borchert},
title = {On the acceptance power of regular languages},
booktitle = {Proceedings 11th Symposium on Theoretical Aspects
of Computer Science},
volume = 775,
pages = {449-460},
series = {Lecture Notes in Computer Science},
publisher = {Springer Verlag},
year = 1994
}
@InCollection{bosi90,
author = {R. B. Boppana and M. Sipser},
title = {The complexity of finite functions},
booktitle = {Handbook of Theoretical Computer Science},
publisher = {Elsevier},
year = 1990,
editor = {J. van Leeuwen},
volume = {A},
pages = {757-804}
}
@InProceedings{bosi97,
author = {B. Borchert and R. Silvestri},
title = {The general notion of a dot operator},
booktitle = {Proceedings 12th Conference on Computational Complexity},
year = 1997,
publisher = {IEEE Computer Society Press},
pages = {26-44}
}
@InProceedings{bovowa96,
author = {R. V. Book and H. Vollmer and K. W. Wagner},
title = {On type-2 probabilistic quantifiers},
booktitle = {Proceedings 23rd International Colloquium on
Automata, Languages and Programming},
volume = {1099},
series = {Lecture Notes in Computer Science},
publisher = {Springer Verlag},
year = 1996,
pages = {369-380}
}
@Article{bovowa98,
author = {R. V. Book and H. Vollmer and K. W. Wagner},
title = {Probabilistic Type 2 operators and {ALMOST}-classes},
journal = {Computational Complexity},
year = 1998,
volume = 7,
pages = {265-289}
}
@Article{becoho86,
author = {P. W. Beame and S. A. Cook and H. J. Hoover},
title = {Log depth circuits for division and related problems},
journal = {SIAM Journal on Computing},
year = 1986,
volume = 15,
pages = {994-1003}
}
@Article{bowa96,
author = {R. V. Book and O. Watanabe},
title = {On random hard sets for {NP}},
journal = {Information and Computation},
year = 1996,
volume = 125,
pages = {70-76}
}
@Article{bowr81,
author = {R. V. Book and C. Wrathall},
title = {Bounded query machines: On {NP()} and {NPQUERY()}},
journal = {Theoretical Computer Science},
year = 1981,
volume = 15,
pages = {41-50}
}
@InProceedings{buni95,
author = {G. Buntrock and G. Niemann},
title = {On weak growing context-sensitive grammars},
booktitle = {Proceedings 2nd Latin American Symposium on
Theoretical Informatics},
volume = 911,
series = {Springer Lecture Notes in Computer Science},
year = 1995,
pages = {180-194}
}
@misc{bur89,
author = {H.-J. Burtschick},
howpublished = {Diplomarbeit},
school = {TU - Berlin},
title = {Vergleich von logarithmischer {P}latzbschr\"ankung
und polynomieller {Z}eit\-beschr\"ankung f\"ur
{K}onstruktionsprobleme und {B}elegmengen},
year = 1989
}
@misc{bur92,
author = {H.-J. Burtschick},
howpublished = {Unpublished Notes},
key = {sparta},
title = {{D}okumentation der Ergebnisse des Arbeitstreffens
Komplexit{\"a}tstheorie in Georgenthal/{T}h{\"u}r.
vom 24.2.1991-1.3.1991},
year = 1992
}
@techreport{bur94,
author = {H.-J. Burtschick},
institution = {TU Berlin},
number = {94-39},
title = {Comparing counting classes for logspace, one-way
logspace, logtime, and first-order},
type = {Forschungsberichte des Fachbereichs Informatik},
year = 1995
}
@InProceedings{bur95,
author = "H.-J. Burtschick",
title = "Comparing Counting Classes for Logspace, One-Way
Logspace, and First-Order",
booktitle = "Proceedings 20th Symposium on Mathematical
Foundations of Computer Science",
pages = "139-148",
year = "1995",
note = "Vol. 969 of {\it Lecture Notes in Computer Science},
Springer Verlag, Berlin",
}
@PhdThesis{bur96,
author = {H. J. Burtschick},
title = {Berechnungs- und Beschreibungskomplexit\"at von
Z\"ahl\-funktionen und Lindstr\"omquantoren},
school = {Fachbereich Informatik, TU-Berlin},
year = 1996
}
@inproceedings{bus87,
author = {S. R. Buss},
booktitle = {Proceedings 19th Symposium on Theory of Computing},
pages = {123-131},
title = {The {B}oolean formula value problem is in {ALOGTIME}},
publisher = {ACM Press},
year = 1987
}
@Article{bus88,
author = {J. F. Buss},
title = {Relativized Alternation and Space-Bounded Computation},
journal = {Journal of Computer and System Sciences},
year = 1988,
volume = 36,
pages = {351-278}
}
@TechReport{buvo96,
author = {H.-J. Burtschick and H. Vollmer},
title = {Lindstr\"om quantifiers and leaf language definability},
institution = {Electronic Colloquium on Computational Complexity},
year = 1996,
number = {96-005},
note = {Submitted for publication}
}
@Article{cach95,
author = {L. Cai and J. Chen},
title = {On input read-modes of alternating Turing machines},
journal = {Theoretical Computer Science},
year = 1995,
volume = 148,
pages = {33-55}
}
@Article{cafu91,
author = {J.-Y. Cai and M. Furst},
title = {{PSPACE} survives constand-width bottlenecks},
journal = {International Journal of Foundations of Computer Science},
year = 1991,
volume = 2,
pages = {67-76}
}
@Article{caguha+88,
author = {J.-Y. Cai and T. Gundermann and J. Hartmanis and
L. A. Hemachandra and V. Sewelson and K. W. Wagner
and G. Wechsung},
title = {The Boolean hierarchy {I}: Structural Properties},
journal = {SIAM Journal on Computing},
year = 1988,
volume = 17,
pages = {1232-1252}
}
@InProceedings{cahe86,
author = {J. Y. Cai and L. Hemachandra},
title = {The {B}oolean hierarchy: hardware over {NP}},
booktitle = {Proceedings 1st Structure in Complexity Theory},
volume = 223,
series = {Lecture Notes in Computer Science},
year = 1986,
publisher = {Springer Verlag},
pages = {105-124.}
}
@InProceedings{cai87,
author = {J. Y. Cai},
title = {Probability one separation of the boolean hierarchy},
booktitle = {Proceedings 4th Symposium on Theoretical
Aspects of Computer Science},
volume = 38,
series = {Lecture Notes in Computer Science},
publisher = {Springer Verlag},
year = 1987,
pages = {148-158}
}
@Article{cai89,
author = {J. Y. Cai},
title = {With probability one, a random oracle separates
{PSPACE} from the polynomial-time hierarchy},
journal = {Journal of Computer and System Sciences},
year = 1989,
volume = 38,
pages = {68-85}
}
@InProceedings{camcthvo96,
author = {H. Caussinus and P. McKenzie and D.
Th\'erien and H. Vollmer},
title = {Nondeterministic {NC$^1$} computation},
booktitle = {Proceedings 11th Computational Complexity},
year = 1996,
publisher = {IEEE Computer Society Press},
pages = {12-21}
}
@Article{chchgo+94,
author = {R. Chang and B. Chor and O. Goldreich and J. Hartmanis and
J. Hastad and D. Ranjan and P. Rohatgi},
title = {The random oracle hypothesis is false},
journal = {Journal of Computer and System Sciences},
year = 1994,
volume = 49,
pages = {24-39}
}
@Book{jac85,
author = {N. Jacobson},
title = {Basic Algebra},
publisher = {Freeman and Company},
year = 1985,
volume = {I},
address = {New York}
}
@InProceedings{chkaro91,
author = {R. Chang and J. Kadin and P. Rohatgi},
title = {Connections between the complexity of unique
satisfiability and the threshold behaviour of
randomized reductions},
booktitle = {Proceedings 6th Structure in Complexity Theory},
year = 1991,
publisher = {IEEE Computer Society Press},
pages = {255-269}
}
@Article{chkost81,
author = {A. K. Chandra and D. Kozen and L. J. Stockmeyer},
title = {Alternation},
journal = {Journal of the ACM},
year = 1981,
volume = 28,
pages = {114-133}
}
@Article{chstvi84,
author = {A. K. Chandra and L. Stockmeyer and U. Vishkin},
title = {Constant depth reducibility},
journal = {SIAM Journal on Computing},
year = 1984,
volume = 13,
pages = {423-439}
}
@Book{clkr97,
author = {P. Clote and E. Kranakis},
title = {Boolean Functions and Computation Models},
publisher = {Springer Verlag},
year = 1998,
note = {To appear}
}
@inproceedings{cogr94,
author = {Kevin J. Compton and Erich Gr{\"a}del},
booktitle = {Proceedings 9th Structure in Complexity Theory},
pages = {255-266},
title = {{L}ogical {D}efinability of {C}ounting {F}unctions},
year = {1994}
}
@Article{CondonL95,
title={Interactive Proof Systems with Polynomially Bounded
Strategies},
author={Anne Condon and Richard Ladner},
pages={506--518},
journal=jcss,
year=1995,
month=jun,
volume=50,
number=3,
source={http://theory.lcs.mit.edu/~dmjones/hbp/jcss/jcss.bib}
}
@InProceedings{coo79,
author = {S. A. Cook},
title = {Deterministic {CFL}'s are accepted simultaneously in polynomial time and log squared space},
booktitle = {Proceedings 11th Theory of Computing},
year = 1979,
publisher = {ACM Press},
pages = {338-345}
}
@Article{coo85,
author = {S. A. Cook},
title = {A taxonomy of problems with fast parallel algorithms},
journal = {Information and Control},
year = 1985,
volume = 64,
pages = {2-22}
}
@TechReport{crhevowa95,
author = {K. Cronauer and U. Hertrampf and H. Vollmer and
K. W. Wagner},
title = {The chain method to separate counting classes},
institution = {Department of Computer Science},
year = 1995,
number = {A-95-20},
address = {University L\"ubeck}
}
@Article{crhevowa97,
author = {K. Cronauer and U. Hertrampf and H. Vollmer and K. W. Wagner},
title = {The chain method to separate counting classes},
journal = {Theory of Computing Systems},
year = 1997,
note = {To appear}
}
@Unpublished{dabo96,
author = {Z. Dang and R. V. Book},
title = {On characterizations of {Almost-$R_A$}},
note = {Manuscript},
year = 1996
}
@Misc{dahoro94,
author = {C. Damm and M. Holzer and P. Rossmanith},
title = {Expressing uniformity via oracles},
howpublished = {manuscript},
year = 94
}
@InCollection{ebb85,
author = {H.-D. Ebbinghaus},
title = {Extended logics: The general framework},
booktitle = {Model-Theoretic Logics},
publisher = {Springer Verlag},
year = 1985,
editor = {J. Barwise and S. Feferman},
series = {Perspectives in Mathematical Logic},
chapter = {II},
pages = {25-76}
}
@Book{ebfl95,
author = {H.-D. Ebbinghaus and J. Flum},
title = {Finite Model Theory},
publisher = {Springer Verlag},
year = 1995,
address = {Berlin Heidelberg}
}
@Book{ebflth94,
author = {H.-D. Ebbinghaus and J. Flum and W. Thomas},
title = {Mathematical Logic},
publisher = {Springer Verlag},
year = 1994,
address = {Berlin Heidelberg},
edition = {2nd}
}
@Book{eil76,
author = {S. Eilenberg},
title = {Automata, Languages, and Machines},
publisher = {Academic Press},
year = 1976,
volume = {B},
address = {New York}
}
@inproceedings{fag74,
author = {R. Fagin},
booktitle = {Complexity of Computations},
editor = {R. Karp},
pages = {43-73},
title = {Generalized first-order spectra and polynomial
time recognizable sets},
publisher = {American Mathematical Society},
address = {Providence, RI},
year = 1974
}
@Book{trba70,
author = {B. A. Trachtenbrot and J. M. Barsdin},
title = {Finite Automata. Behaviour and Synthesis},
publisher = {Mir},
year = 1970,
address = {Moscow},
note = {In Russian.}
}
@InProceedings{bue62,
author = {J. R. B{\"u}chi},
title = {On a decision method in restricted second-order arithmetic},
booktitle = {Proceedings Logic, Methodology and Philosophy of Sciences 1960},
year = 1962,
publisher = {Stanford University Press},
address = {Stanford, CA}
}
@Article{fefoku94,
author = {S. Fenner and L. Fortnow and S. Kurtz},
title = {Gap-definable counting classes},
journal = {Journal of Computer and System Sciences},
year = 1994,
volume = 48,
pages = {116-148}
}
@InProceedings{fglss91,
author = {U. Feige and S. Goldwasser and L. Lov\'asz and S. Safra and M. Szegedy},
title = {Approximating clique is almost {NP}-complete},
booktitle = {Proceedings 32nd Symposium on Foundations of Computer Science},
year = 1991,
publisher = {IEEE Computer Society Press},
pages = {2-12}
}
@article{fglss96,
Author = "U. Feige and S. Goldwasser and L. {Lov\'{a}sz} and S. Safra
and M. Szegedy",
title = "Interactive Proofs and the Hardness of Approximating Cliques",
journal = jacm,
volume = 43,
number = 2,
month = mar,
year = 1996,
pages = {268-292}}
@Unpublished{fis74,
author = {M. J. Fischer},
title = {Lectures on Network Complexity},
note = {Universit\"at Frankfurt/Main},
year = 1974
}
@Article{for94,
author = {L. Fortnow},
title = {The role of relativization in complexity theory},
journal = {Bulletin of the EATCS},
year = 1994,
volume = 52,
pages = {229-244}
}
@InCollection{for97,
author = {L. Fortnow},
title = {Counting Complexity},
booktitle = {Complexity Theory Retrospective II},
publisher = {Springer Verlag},
year = 1997,
editor = {A. Selmand and L. A. Hemaspaandra},
address = {New York},
pages = {81-107}
}
@string{tcs = {Theoretical Computer Science}}
@Article{FortnowL1993,
title={Interactive proof systems and alternating time--space
complexity},
author={Lance Fortnow and Carsten Lund},
pages={55--73},
journal=tcs,
year=1993,
month={24~} # may,
volume=113,
number=1,
source={http://theory.lcs.mit.edu/~dmjones/hbp/tcs/tcs.bib}
}
@Article{fosi88,
author = {L. Fortnow and M. Sipser},
title = {Are there interactive protocols for {coNP} languages?},
journal = {Information Processing Letters},
year = 1988,
volume = 28,
pages = {249-251}
}
@Article{fusasi84,
author = {M. Furst and J. B. Saxe and M. Sipser},
title = {Parity, circuits, and the polynomial-time hierarchy},
journal = {Mathematical Systems Theory},
year = 1984,
volume = 17,
pages = {13-27}
}
@Book{gajo79,
author = {M. R. Garey and D. S. Johnson},
title = {Computers and Intractability, A Guide to the Theory of NP-Completeness},
publisher = {Freeman},
year = 1979,
address = {New York}
}
@Article{gakrra95,
author = {W. I. Gasarch and M. W. Krentel and K. J. Rappoport},
title = {{OptP} as the normal behaviour of {NP}-complete problems},
journal = {Mathematical Systems Theory},
year = 1995,
volume = 28,
pages = {487-514}
}
@InCollection{gat93,
author = {J. von zur Gathen},
title = {Parallel linear algebra},
booktitle = {Synthesis of Parallel Algorithms},
publisher = {Morgan Kaufmann},
year = 1993,
editor = {J. H. Reif},
pages = {573-617}
}
@Article{gil77,
author = {J. Gill},
title = {Computational complexity of probabilistic complexity
classes},
journal = {SIAM Journal on Computing},
year = 1977,
volume = 6,
pages = {675-695}
}
@Book{gisp93,
title = {Lectures on Parallel Computation},
publisher = {Cambridge University Press},
year = 1993,
editor = {A. Gibbons and P. Spirakis},
volume = 4,
series = {Cambridge International Series on Parallel Computation},
address = {Cambridge}
}
@Unpublished{glwe97,
author = {C. Gla{\ss}er and G. Wechsung},
title = {Relativizing function classes},
note = {Manuscript},
year = 1997
}
@InCollection{gol97,
author = {O. Goldreich},
title = {A taxonomy of proof systems},
booktitle = {Complexity Theory Retrospective II},
publisher = {Springer Verlag},
year = 1997,
editor = {L. A. Hemaspaandra and A. L. Selman},
pages = {109-134}
}
@Article{gopa86,
author = {L. M. Goldschlager and I. Parberry},
title = {On the construction of parallel computers from various bases of boolean functions},
journal = {Theoretical Computer Science},
year = 1986,
volume = 43,
pages = {43-58}
}
@TechReport{got95,
author = {G. Gottlob},
title = {Relativized logspace and generalized quantifiers
over finite structures},
institution = {Institut for Information Systems, Vienna University
of Technology},
year = {1995},
number = {CD-TR-95/76},
note = {An extended abstract appeared in the proceedings of
the 10th Symposium on Logic in Computer Science, 1995.}
}
@Article{got95b,
author = {G. Gottlob},
title = {{NP} trees and {Carnap's} modal logic},
journal = {Journal of the Association for Computing Machinery},
year = 1995,
volume = 42,
pages = {421-457}
}
@article{gra92,
author = {Erich Gr{\"{a}}del},
journal = {Theoretical {C}omputer {S}cience},
number = 101,
pages = {35-57},
title = {Capturing complexity classes by fragments of
second-order logic},
year = 1992
}
@Article{gre91,
author = {F. Green},
title = {An oracle separating {$\pari\P$} from {$\PP^{\PH}$}},
journal = {Information Processing Letters},
year = 1991,
volume = 37,
pages = {149-153}
}
@Article{gre93,
author = {F. Green},
title = {On the power of deterministic reductions to {C$_=$P}},
journal = {Mathematical Systems Theory},
year = 1993,
volume = 26,
pages = {215-234}
}
@Book{grhoru95,
author = {R. Greenlaw and H. J. Hoover and W. L. Ruzzo},
title = {Limits to Parallel Computation: P-Completeness Theory},
publisher = {Oxford University Press},
year = 1995,
address = {New York}
}
@Article{grkorescto95,
author = {F. Green and J. K\"obler and K. Regan and T. Schwentick and J. Tor\'an},
title = {The power of the middle bit of a \#{P} function},
journal = {Journal of Computer and System Sciences},
year = 1995,
volume = 50,
pages = {456-467}
}
@InCollection{hachch+93,
author = {J. Hartmanis and R. Chang and S. Chari and D. Ranjan
and P. Rohatgi},
title = {Relativization: a revisionistic retrospective},
booktitle = {Current Trends in Theoretical Computer Science},
publisher = {World Scientific},
year = 1993,
editor = {G. Rozenberg and A. Salomaa},
pages = {537-547}
}
@InProceedings{hachraro90,
author = {J. Hartmanis and R. Chang and D. Ranjan and P. Rohatgi},
title = {Structural complexity theory: recent surprises},
booktitle = {Proceedings 2nd Scandinavian Workshop on Algorithm Theory},
volume = 447,
series = {Lecture Notes in Computer Science},
year = 1990,
publisher = {Springer Verlag},
pages = {1-12}
}
@inproceedings{haim78,
author = {J. Hartmanis and N. Immerman and S. Mahaney},
booktitle = {Proc. 19th IEEE Symp. Foundations of Computer Science},
pages = {65 - 71},
publisher = {IEEE Computer Society Press},
title = {One-way log-tape reductions},
year = {1978}
}
@InProceedings{has86,
author = {J. H{\aa}stad},
title = {Almost optimal lower bounds for small depth circuits},
booktitle = {Procedings 18th Symposium on Theory of Computing},
year = 1986,
publisher = {IEEE Computer Society},
pages = {6-20}
}
@Book{has88,
author = {J. H{\aa}stad},
title = {Computational Limitations of Small Depth Circuits},
publisher = {MIT Press},
year = 1988,
address = {Cambridge}
}
@Book{hawr54,
author = {G. H. Hardy and E. M. Wright},
title = {An Introduction to the Theory of Numbers},
publisher = {Oxford University Press},
year = 1954,
edition = {3rd}
}
@InProceedings{helascvowa93,
author = {U. Hertrampf and C. Lautemann and T. Schwentick and
H. Vollmer and K. W. Wagner},
title = {On the power of polynomial time bit-reductions},
booktitle = {Proceedings 8th Structure in Complexity Theory},
year = 1993,
pages = {200-207}
}
@TechReport{heog94,
author = {L. Hemaspaandra and M. Ogihara},
title = {Universally serializable computation},
institution = {Department of Computer Science, University of Rochester},
year = 1994,
number = {TR-520}
}
@TechReport{her95,
author = {U. Hertrampf},
title = {Regular leaf-languages and (non-) regular tree shapes},
institution = {Institut f\"ur Mathematik und Informatik,
Medizinische Universit\"at zu L\"ubeck},
year = 1995,
number = {A-95-21}
}
@InProceedings{her95b,
author = {U. Hertrampf},
title = {Classes of bounded counting type and their inclusion
relations},
booktitle = {Proceedings 12th Symposium on Theoretical Aspects of
Computer Science},
volume = 900,
series = {Lecture Notes in Computer Science},
year = 1995,
publisher = {Springer Verlag},
pages = {60-70}
}
@TechReport{her96,
author = {U. Hertrampf},
title = {Acceptance by transformation monoids (with an
application to local self reductions)},
institution = {Fachbereich Informatik, Universit\"at Stuttgart},
year = 1996
}
@InProceedings{her97,
author = {U. Hertrampf},
title = {Acceptance by transformation monoids (with an application to local self reductions)},
booktitle = {Proceedings 12th Conference on Computational Complexity},
year = 1997,
publisher = {IEEE Computer Society Press},
pages = {213-224}
}
@InProceedings{her97b,
author = {U. Hertrampf},
title = {Polynomial Time Machines Equipped with Word Problems
over Algebraic Structures as their Acceptance Criteria},
booktitle = {Proceedings 11th Fundamentals of Computation Theory},
volume = {1279},
series = {Lecture Notes in Computer Science},
year = 1997,
publisher = {Springer Verlag},
pages = {233-244}
}
@article{hevo95,
author = {L. Hemaspaandra and H. Vollmer},
journal = {Complexity Theory Column 8, ACM SIGACT-Newsletter},
number = 1,
pages = {2-13},
title = {The satanic notations: counting classes beyond {\#}{P}
and other definitional adventures},
volume = 26,
year = 1995
}
@InProceedings{hevowa95,
author = {U. Hertrampf and H. Vollmer and K. W. Wagner},
title = {On the power of number-theoretic operations with
respect to counting},
booktitle = {Proceedings 10th Structure in Complexity Theory},
year = 1995,
pages = {299-314}
}
@Article{hevowa96,
author = {U. Hertrampf and H. Vollmer and K. W. Wagner},
title = {On balanced vs.~unbalanced computation trees},
journal = {Mathematical Systems Theory},
volume = 29,
year = 1996,
pages = {411-421}
}
@InProceedings{hewe97,
author = {H. Hempel and G. Wechsung},
title = {The operators min and max on the polynomial time hierarchy},
booktitle = {Proceedings 14th Symposium on Theoretical Aspects of Computer Science},
year = 1997,
series = {Lecture Notes in Computer Science},
volume = 1200,
publisher = {Springer Verlag},
pages = {93-104}
}
@Article{hop84,
author = {J. E. Hopcroft},
title = {Turing machines},
journal = {Scientific American},
year = 1984,
month = {May},
volume = 5,
pages = {86-98}
}
@InCollection{hoprst95,
author = {S. Hougardy and H.-J. Pr\"omel and A. Steger},
title = {Probabilistically checkable proofs and their consequences for approximation algorithms},
booktitle = {Trends in Discrete Mathematics},
publisher = {North Holland},
year = 1995,
editor = {W. Deubner and H.-J. Pr\"omel and B. Voigt},
volume = 9,
series = {Topics in Discrete Mathematics},
pages = {175-223}
}
@article{houl69,
author = {J. E. Hopcroft and J. D. Ullman},
journal = {Journal of the {ACM}},
number = {1},
pages = {168-177},
title = {{S}ome {R}esults on {T}ape-{B}ounded {T}uring {M}achines},
volume = {16},
year = {1969}
}
@Book{houl79,
author = {H. E. Hopcroft and J. D. Ullman},
title = {Introduction to Automata Theory, Languages, and Computation},
publisher = {Addison-Wesley},
address = {Reading, MA},
year = 1979
}
@Book{hro97,
author = {J. Hromkovi\v{c}},
title = {Communication Complexity and Parallel Computing},
publisher = {Springer Verlag},
year = 1997,
series = {Texts in Theoretical Computer Science},
address = {Berlin Heidelberg}
}
@Article{iba71,
author = {O. H. Ibarra},
title = {Characterizations of some tape and time classes of
Turing machines in terms of multihead and auxiliary
stack automata},
journal = {Journal of Computer and System Sciences},
year = 1971,
volume = 5,
pages = {88-117}
}
@Article{imla95,
author = {N. Immernan and S. Landau},
title = {The complexity of iterated multiplication},
journal = {Information and Computation},
year = 1995,
volume = 116,
pages = {103-116}
}
@InCollection{imm89b,
author = {N. Immerman},
title = {Descriptive and Computational Complexity},
booktitle = {Computational Complexity Theory},
publisher = {American Mathematical Society},
year = 1989,
editor = {J. Hartmanis},
volume = 38,
series = {Proceedings of Symposia in Applied Mathematics},
address = {Providence, RI},
pages = {75-91}
}
@Article{imm87,
author = {N. Immerman},
title = {Languages that capture complexity classes},
journal = {SIAM Journal on Computing},
year = 1987,
volume = 16,
pages = {760-778}
}
@InProceedings{imm88,
author = {N. Immerman},
title = {Nondeterministic space is closed under complementation},
booktitle = {3rd Ann. Conf. Structure in Complexity Theory},
year = 1988,
pages = {112-115}
}
@Article{imm89,
author = {N. Immerman},
title = {Expressibility and parallel complexity},
journal = {SIAM Journal on Computing},
year = 1989,
volume = 18,
pages = {625-638}
}
@Article{imm88b,
author = {N. Immerman},
title = {Nondeterministic space is closed under complementation},
journal = {SIAM Journal on Computing},
year = 1988,
volume = 17,
pages = {935-938}
}
@Article{jemcth96,
author = {B. Jenner and P. McKenzie and D. Th\'erien},
title = {Logspace and logtime leaf languages},
year = 1996,
journal = {Information \& Computation},
volume = 129,
pages = {21-33}
}
@Article{jeto95,
author = {B. Jenner and J. Tor{\'a}n},
title = {Computing functions with parallel queries to {NP}},
journal = {Theoretical Computer Science},
year = 1995,
volume = 141,
pages = {175-193}
}
@InCollection{joh90,
author = {D. S. Johnson},
title = {A catalog of complexity classes},
booktitle = {Handbook of Theoretical Computer Science},
publisher = {Elsevier},
year = 1990,
editor = {J. van Leeuwen},
volume = {A},
pages = {67-161}
}
@Article{jose74,
author = {N. D. Jones and A. L. Selman},
title = {Turing machines and the spectra of first-order
formulas},
journal = {Journal of Symbolic Logic},
year = 1974,
volume = 39
}
@Article{sze87,
author = {R. Szelepcs\'enyi},
title = {The method of forcing for nondeterministic automata},
journal = {Bulletin of the European Association for Theoretical Computer Science},
year = 1987,
volume = 33,
pages = {96-100}
}
@article{sze88,
author = "R. Szelepcs\'{e}nyi",
title = "The Method of Forced Enumeration for Nondeterministic Automata",
journal = "Acta Informatica",
volume = 26,
pages = "279-284",
year = 1988}
@Article{jon75,
author = {N. D. Jones},
title = {Space-bounded reducibility among combinatorial problems},
journal = {Journal of Computer and System Sciences},
year = 1975,
volume = 15,
pages = {68-85}
}
@Article{kali82,
author = {R. Karp and R. Lipton},
title = {Turing machines that take advice},
journal = {L'enseignement math\'ematique},
year = 1982,
volume = 28,
pages = {191-209}
}
@Book{hapu93,
author = {P. H{\'a}jek and P. Pudl{\'a}k},
title = {Metamathematics of First-Order Arithmetic},
publisher = {Springer Verlag},
year = 1993,
series = {Perspectives in Mathematical Logic},
address = {Berlin Heidelberg}
}
@Book{smo91,
author = {C. Smory{\'n}ski},
title = {Logical Number Theory I},
publisher = {Springer Verlag},
year = 1991
}
@InProceedings{kami94,
author = {S. M. Kautz and P. B. Miltersen},
title = {Relative to a random oracle, {NP} is not small},
booktitle = {Proceedings 9th Structure in Complexity Theory},
year = 1994,
publisher = {IEEE Computer Society Press},
pages = {162-174}
}
@PhdThesis{kau91,
author = {S. Kautz},
title = {Degrees of random sets},
school = {Cornell University},
year = 1991
}
@Book{knuI97,
author = {D. E. Knuth},
title = {The Art of Computer Programming Vol.~I: Fundamental Algorithms},
publisher = {Addison-Wesley},
year = 1997,
edition = {3rd}
}
@Article{ko89,
author = {K.-I. Ko},
title = {Relativized Polynomial Time Hierarchies Having Exactly $k$ Levels},
journal = {SIAM Journal on Computing},
year = 1989,
volume = 18,
pages = {392-408}
}
@PhdThesis{koe89,
title = {{S}trukturelle {K}omplexit\"at von {A}nzahlproblemen},
author = {J. K{\"o}bler},
school = {Universit\"at Stuttgart, Fakult\"at f\"ur Informatik},
year = 1989
}
@Unpublished{koe89-dt,
author = {J. K{\"o}bler},
title = {{S}trukturelle {K}omplexit\"at von {A}nzahlproblemen},
note = {Dissertation, Universit\"at Stuttgart, Fakult\"at f\"ur Informatik},
year = 1989
}
@MastersThesis{kos96,
author = {S. Kosub},
title = {Clustermaschinen},
school = {Fakult\"at f\"ur Mathematik und Informatik},
year = 1996,
address = {Friedrich-Schiller-Universit\"at Jena}
}
@TechReport{kos97,
author = {S. Kosub},
title = {On cluster machines and function classes},
institution = {Institut f\"ur Informatik, Universit\"at W\"urzburg},
year = 1997,
number = 172
}
@Article{koscto89,
author = {J. K\"obler and U. Sch\"oning and J. Tor\'an},
title = {On counting and approximation},
journal = {Acta Informatica},
year = 1989,
volume = 26,
pages = {363-379}
}
@TechReport{koscvo97,
author = {S. Kosub and H. Schmitz and H. Vollmer},
title = {Uniformly defining complexity classes of functions},
institution = {Institut f\"ur Informatik, Universit\"at W\"urzburg},
number = 183,
year = 1997
}
@Article{kre88,
author = {M. W. Krentel},
title = {The complexity of optimization functions},
journal = {Journal of Computer and System Sciences},
year = 1988,
volume = 36,
pages = {490-509}
}
@Article{kre92,
author = {M. W. Krentel},
title = {Generalizations of {OptP} to the polynomial hierarchy},
journal = {Theoretical Computer Science},
year = 1992,
volume = 97,
pages = {183-198}
}
@Article{kumaro95,
author = {S. A. Kurtz and S. R. Mahaney and J. S. Royer},
title = {The isomorphism conjecture fails relative to a
random oracle},
journal = {Journal of the ACM},
year = 1995,
volume = 42,
pages = {401-420}
}
@Article{kur83,
author = {S. Kurtz},
title = {On the random oracle hypothesis},
journal = {Information and Control},
year = 1983,
volume = 57,
pages = {40-47}
}
@inproceedings{lan86,
author = {K. J. Lange},
booktitle = {Proceedings 12th Symposium on Mathematical Foundations
of Computer Science},
pages = {518-526},
publisher = {Springer Verlag},
series = {Lecture Notes in Computer Science},
title = {Two characterizations of the logarithmic
alternation hierarchy},
volume = 233,
year = 1986
}
@InProceedings{lascth94,
author = {C. Lautemann and T. Schwentick and D. Th\'erien},
title = {Logics for context-free languages},
booktitle = {8th Computer Science Logic, Selected Papers},
editor = {L. Pacholski and J. Tiuryn},
volume = 933,
series = {Lecture Notes in Computer Science},
year = 1994,
publisher = {Springer Verlag},
pages = {205-216}
}
@article{lau83,
author = {C. Lautemann},
journal = {Information Processing Letters},
pages = {215-217},
title = {{BPP} and the polynomial hierarchy},
volume = 17,
year = 1983
}
@article{lei89,
author = {Daniel Leivant},
journal = {Journal of Computer and System Sciences},
pages = {51-83},
title = {Descriptive {C}haracterizations of {C}omputational
{C}omplexity},
volume = 39,
year = 1989
}
@Article{lin66,
author = "P. Lindstr{\"o}m",
title = "First order predicate logic with generalized quantifiers",
journal = "Theoria",
year = 1966,
volume = 32,
pages = "186-195"
}
@InProceedings{lin92,
author = {S. Lindell},
title = {A purely logical characterization of circuit uniformity},
booktitle = {Proceedings 7th Structure in Complexity Theory},
year = 1992,
pages = {185-192}
}
@Misc{lin94,
author = {S. Lindell},
howpublished = {manuscript},
year = 1994,
note = {e-mail communication by Kenneth W. Regan}
}
@Book{livi93,
author = {M. Li and P. Vit\'anyi},
title = {An Introduction to Kolmogorov Complexity and its
Applications},
publisher = {Springer Verlag},
year = 1993,
series = {Texts and Monographs in Computer Science},
address = {New York}
}
@Article{lup58,
author = {O. B. Lupanov},
title = {A method of circuit synthesis},
journal = {Izvestia V.U.Z. Radiofizika},
year = 1958,
volume = 1,
pages = {120-140}
}
@Article{lut92,
author = {J. Lutz},
title = {On independent random oracles},
journal = {Theoretical Computer Science},
year = 1992,
volume = 92,
pages = {301-307}
}
@Article{lut93a,
author = {J. Lutz},
title = {A pseudorandom oracle characterization of {BPP}},
journal = {SIAM Journal on Computing},
year = 1992,
volume = 22,
pages = {???}
}
@InProceedings{lut93b,
author = {J. Lutz},
title = {The quantitative structure of exponential time},
booktitle = {Proceedings 8th Structure in Complexity Theory},
year = 1993,
publisher = {IEEE Computer Society Press},
pages = {158-175}
}
@inproceedings{lyn90,
author = {J. F. Lynch},
booktitle = {5th Ann. Conf. Structure in Complexity Theory},
journal = {Proc. 5th Structure in Complexity Conf.},
pages = {210-222},
title = {The {Q}uantifier {S}tructure of {S}entences that
{C}haracterize {N}ondeterministic {T}ime {C}omplexity},
year = 1990
}
@InProceedings{mapn93,
author = {J. A. Makowsky and Y. B. Pnueli},
title = {Oracles and quantifiers},
booktitle = {Computer Science Logic},
volume = 832,
series = {Lecture Notes in Computer Science},
year = 1993,
publisher = {Springer Verlag},
pages = {189-222}
}
@InProceedings{mapn94,
author = {J. A. Makowsky and Y. B. Pnueli},
title = {Logics capturing relativized complexity classes uniform},
booktitle = {Logic and Computational Complexity},
editor = {D. Leivant},
volume = 1995,
series = {Lecture Notes in Computer Science},
year = 1994,
publisher = {Springer Verlag}
}
@Article{mar66,
author = {P. Martin-L\"of},
title = {The definition of random sequences},
journal = {Information and Control},
year = 1966,
volume = 9,
pages = {602-619}
}
@InProceedings{math93,
author = {A. Maciel and T. Th\'erien},
title = {Threshold circuits for iterated multiplication: using {$\ACn$} for free},
booktitle = {Proceedings 10th Symposium on Theoretical Aspects of Computer Science},
volume = 665,
series = {Lecture Notes in Computer Science},
year = 1993,
publisher = {Springer Verlag},
pages = {545-554}
}
@Book{mcpa71,
author = {R. McNaughton and S. Papert},
title = {Counter-Free Automata},
publisher = {MIT Press},
year = 1971
}
@Book{meco81,
author = {C. Mead and L. Conway},
title = {Introduction to VLSI Systems},
publisher = {Addison-Wesley},
year = 1981,
address = {Reading, MA}
}
@inproceedings{meh82,
author = {K. Mehlhorn and E. M. Schmidt},
booktitle = {Proceedings 14th Symposium on Theory of Computing},
pages = {330-337},
title = {Las Vegas is better than Determinism in VLSI and
Distributed Computing},
year = 1982
}
@InProceedings{mest72,
author = {A. R. Meyer and L. J. Stockmeyer},
title = {The equivalence problem for regular expressions with
squaring requires exponential time},
booktitle = {Proceedings 13th Symposium on Switching and Automata
Theory},
year = 1972,
publisher = {IEEE Computer Society Press},
pages = {125-129}
}
@InProceedings{mewa95,
author = {W. Merkle and Y. Wang},
title = {Separations by random oracles and ``{A}lmost''
classes for generalized reducibilities},
booktitle = {Proceedings 20th Symposium on Mathematical
Foundations of Computer Science},
volume = 969,
series = {Lecture Notes in Computer Science},
publisher = {Springer Verlag},
year = 1995,
pages = {179-190}
}
@Article{mil92,
author = {P. B. Miltersen},
title = {Circuit depth relative to a random oracle},
journal = {Information Processing Letters},
year = 1992,
volume = 42,
pages = {???}
}
@Book{mipa88,
author = {M. Minsky and S. A. Papert},
title = {Perceptrons},
publisher = {MIT Press},
year = 1988,
address = {Cambridge, MA},
note = {Expanded edition. Originally published in 1969}
}
@Article{muve96,
author = {A. A. Muchnik and N. K. Vereshchagin},
title = {A general method to construct oracles realizing given relationships between complexity classes},
journal = {Theoretical Computer Science},
year = 1996,
volume = 157,
pages = {227-258}
}
@Article{nis93,
author = {N. Nisan},
title = {On read-once vs. multiple access to randomness in logspace},
journal = {Theoretical Computer Science},
year = 1993,
volume = 107,
pages = {135-144}
}
@Article{niwi94,
author = {N. Nisan and A. Wigderson},
title = {Hardness vs. randomness},
journal = {Journal of Computer and System Sciences},
year = 1994,
volume = 49,
pages = {149-167}
}
@Article{oghe93,
author = {M. Ogiwara and L. Hemachandra},
title = {A complexity theory of feasible closure properties},
journal = {Journal of Computer and System Sciences},
year = 1993,
volume = 46,
pages = {295-325}
}
@Article{ogi94,
author = {M. Ogihara},
title = {On serializable languages},
journal = {International Journal of Foundations of Computer Science},
year = 1994,
volume = 5,
pages = {303-318}
}
@InProceedings{orp83,
author = {P. Orponen},
title = {Complexity classes of alternating machines with oracles},
booktitle = {Proceedings 10th International Colloquium on
Automata, Languages and Programming},
volume = 154,
series = {Lecture Notes in Computer Science},
year = 1983,
publisher = {Springer Verlag},
pages = {573-584}
}
@book{pap94,
author = {C. H. Papadimitriou},
publisher = {Addison-Wesley},
address = {Reading, MA},
title = {Computational Complexity},
year = 1994
}
@InProceedings{paza83,
author = {C. H. Papadimitriou and S. Zachos},
title = {Two remarks on the power of counting},
booktitle = {Proceedings 6th GI Conference on Theoretical
Computer Science},
volume = 145,
series = {Lecture Notes in Computer Science},
year = 1983,
publisher = {Springer Verlag},
pages = {269-275}
}
@InProceedings{pip79,
author = {N. Pippenger},
title = {On simultaneous resource bounds},
booktitle = {Proceedings 20th Symposium on Foundations of Computer Science},
year = 1979,
publisher = {IEEE Computer Society Press},
pages = {307-311}
}
@TechReport{rasa95,
author = {J. Radhakrishnan and S. Saluja},
title = {Interactive Proof Systems},
institution = {Tata Institute of Fundamental Research},
year = 1995,
number = {TCS-95/4},
address = {Bombay},
note = {Lecture Notes}
}
@Article{raz85,
author = {A. A. Razborov},
title = {Lower bounds on the monotone complexity of some boolean functions},
journal = {Doklady Akademii Nauk SSSR},
year = 1985,
volume = 281,
pages = {798-801},
note = {English translation in Soviet Math. Doklady 31 (1985), 354--357}
}
@Article{raz87,
author = {A. A. Razborov},
title = {Lower bounds on the size of bounded depth networks over a complete basis with logical addition},
journal = {Matematicheskie Zametki},
year = 1987,
volume = 41,
pages = {598-607},
note = {In Russian. English translation in {\em Mathematical Notes of the Academy of Sciences of the USSR\/} 41:333--338, 1987}
}
@InCollection{reg97,
author = {K. Regan},
title = {Polynomials and combinatorial definitions of languages},
booktitle = {Complexity Theory Retrospective II},
publisher = {Springer Verlag},
year = 1997,
editor = {L. A. Hemaspaandra and A. L. Selman},
pages = {261-293}
}
@Unpublished{reg93,
author = {K. Regan},
title = {Log-time {ATMs} and first-order logic},
note = {Unpublished manuscript},
year = 1993
}
@Article{rero95,
author = {K. W. Regan and J. S. Royer},
title = {On closure properties of bounded two-sided error
complexity classes},
journal = {Mathematical Systems Theory},
year = 1995,
volume = 28,
pages = {229-243}
}
@Article{revo97,
author = {K. Regan and H. Vollmer},
title = {Gap-languages and log-time complexity classes},
journal = {Theoretical Computer Science},
year = 1997,
volume = 188,
pages = {101-116}
}
@Book{rog67,
author = {H. {Rogers Jr.}},
title = {Theory of Recursive Functions and Effective Computability},
publisher = {McGraw-Hill},
year = 1967,
address = {New York}
}
@Book{rosaI97,
title = {Handbook of Formal Languages},
publisher = {Springer Verlag},
year = 1997,
editor = {R. Rozenberg and A. Salomaa},
volume = {I}
}
@Article{ruz80,
author = {W. L. Ruzzo},
title = {Tree-size bounded alternation},
journal = {Journal of Computer and System Sciences},
year = 1980,
volume = 21,
pages = {218-235}
}
@Article{ruz81,
author = {W. L. Ruzzo},
title = {On uniform circuit complexity},
journal = {Journal of Computer and Systems Sciences},
year = 1981,
volume = 21,
pages = {365-383}
}
@inproceedings{sasuth92,
author = {S. Saluja and K. V. Subrahmanyam and M. N. Thakur},
booktitle = {Proceedings 7th Structure in Complexity Theory},
title = {Descriptive Complexity of \#{P} Functions},
year = 1992
}
@Book{sav76,
author = {J. E. Savage},
title = {The Complexity of Computing},
publisher = {John Wily},
year = 1976,
address = {New York}
}
@Article{sch74,
author = {C. P. Schnorr},
title = {Zwei lineare untere {S}chranken f\"ur die {K}omplexit\"at {B}oolescher {F}unktionen},
journal = {Computing},
year = 1974,
volume = 13,
pages = {155-171}
}
@Article{sch76,
author = {C. P. Schnorr},
title = {The network complexity and the Turing machine complexity of finite functions},
journal = {Acta Informatica},
year = 1976,
volume = 7,
pages = {95-107}
}
@Book{sch86,
author = {U. Sch{\"o}ning},
title = {Complexity and Structure},
publisher = {Springer Verlag},
address = {Berlin Heidelberg},
year = 1986,
volume = 211,
series = {Lecture Notes in Computer Science}
}
@Article{sch89,
author = {U. Sch\"oning},
title = {Probabilistic complexity classes and lowness},
journal = {Journal of Computer and System Sciences},
year = 1989,
volume = 39,
pages = {84-100}
}
@book{sch92,
author = {U. {Sch}{\"o}ning},
publisher = {{BI} {W}issenschaftsverlag},
title = {{T}heoretische {I}nformatik kurz gefasst},
year = {1992}
}
@Book{sch95,
author = {U. Sch{\"o}ning},
title = {Perlen der {T}heoretischen {I}nformatik},
publisher = {BI-Wis\-sen\-schafts\-ver\-lag},
year = 1995,
address = {Mannheim}
}
@MastersThesis{sch96,
author = {H. Schmitz},
title = {Nichtdeterministische {P}olynomialzeit-{B}erechnung von {F}unktionen},
school = {Institut f\"ur Informatik, Universit\"at W\"urzburg},
year = 1996
}
@Unpublished{scvo97,
author = {T. Schwentick and H. Vollmer},
title = {Logical characterizations of classes between {CFL} and
{LOGCFL}},
year = 1996,
note = {Manuscript}
}
@TechReport{scwa97,
author = {H. Schmitz and K. Wagner},
title = {A note on parallel vs.~adaptive queries when computing functions},
institution = {Institut f\"ur Informatik, Universit\"at W\"urzburg},
year = 1997,
number = 999
}
@Article{sel94,
author = {A. Selman},
title = {A taxonomy on complexity classes of functions},
journal = {Journal of Computer and System Sciences},
year = 1994,
volume = 48,
pages = {357-381}
}
@Article{sexubo83,
author = {A. L. Selman and M.-R. Xu and R. V. Book},
title = {Positive relativizations of complexity classes},
journal = {SIAM Journal on Computing},
year = 1983,
volume = 12,
pages = {565-579}
}
@Article{sha49,
author = {C. Shannon},
title = {The synthesis of two-terminal switching circuits},
journal = {Bell Systems Technical Journal},
year = 1949,
volume = 28,
pages = {59-98}
}
@Article{sha92,
author = {A. Shamir},
title = {{IP = PSPACE}},
journal = {Journal of the ACM},
year = 1992,
volume = 39,
pages = {869-877}
}
@InProceedings{sham90,
author = {A. Shamir},
title = {{IP = PSPACE}},
booktitle = {Proceedings 31st Symposium on Foundations of Computer Science},
year = 1990,
publisher = {IEEE Computer Society Press},
pages = {11-15}
}
@PhdThesis{sim75,
author = {J. Simon},
title = {On Some Central Problems in Computational Complexity},
school = {Cornell University},
year = 1975
}
@InProceedings{sip83,
author = {M. Sipser},
title = {A complexity theoretic approach to randomness},
booktitle = {Proceedings of the 15th Symposium on Theory of Computing},
year = 1983,
pages = {330-335}
}
@InProceedings{sip83b,
author = {M. Sipser},
title = {Borel sets and circuit complexity},
booktitle = {Proceedings of the 15th Symposium on Theory of Computing},
year = 1983,
publisher = {ACM Press},
pages = {61-69}
}
@InProceedings{smo87,
author = {R. Smolensky},
title = {Algebraic methods in the theory of lower bounds for {Boolean} circuit complexity},
booktitle = {Proceedings 19th Symposium on Theory of Computing},
year = 1987,
publisher = {ACM Press},
pages = {77-82}
}
@Article{ste91,
author = {I. A. Stewart},
title = {Comparing the expressibility of languages formed
using {NP}-complete operators},
journal = {Journal of Logic and Computation},
year = 1991,
volume = 1,
pages = {305-330}
}
@Article{ste92,
author = {I. A. Stewart},
title = {Using the {H}amilton path operator to capture {NP}},
journal = {Journal of Computer and System Sciences},
year = 1992,
volume = 45,
pages = {127-151}
}
@InProceedings{stme73,
author = "L. J. Stockmeyer and A. R. Meyer",
title = "Word Problems Requiring Exponential Time",
pages = {1-9},
booktitle = "Proceedings 5th ACM Symposium on the Theory of Computing",
year = 1973
}
@Article{sto77,
author = {L. Stockmeyer},
title = {The polynomial-time hierarchy},
journal = {Theoretical Computer Science},
year = 197,
volume = 3,
pages = {1-22}
}
@book{str94,
author = {H. Straubing},
publisher = {Birkh{\"a}user},
address = {Boston},
title = {Finite Automata, Formal Logic, and Circuit Complexity},
year = 1994
}
@Article{stvi84,
author = {L. Stockmeyer and U. Vishkin},
title = {Simulation of parallel random access machines by circuits},
journal = {SIAM Journal on Computing},
year = 1984,
volume = 13,
pages = {409-422}
}
@Book{sud95,
author = {M. Sudan},
title = {Efficient Checking of Polynomials and Proofs and the
Hardness of Approximation Problems},
publisher = {Springer Verlag},
year = 1995,
volume = 1001,
series = {Lecture Notes in Computer Science}
}
@Article{tabo91,
author = {S. Tang and R. V. Book},
title = {Polynomial-time reducibilities and almost all oracle
sets},
journal = {Theoretical Computer Science},
year = 1991,
volume = 81,
pages = {201-209}
}
@Article{tar93,
author = {J. Tarui},
title = {Probabilistic polynomials, {AC$^0$} functions, and the polynomial hierarchy},
journal = {Theoretical Computer Science},
year = 1993,
volume = 113,
pages = {167-183}
}
@Article{tawa89,
author = {S. Tang and O. Watanabe},
title = {On tally relativizations of {BP}-complexity classes},
journal = {SIAM Journal on Computing},
year = 1989,
volume = 18,
pages = {449-462}
}
@Article{the81,
author = {D. Th{\'e}rien},
title = {Classification of finite monoids: the language approach},
journal = {Theoretical Computer Science},
year = 1981,
volume = 14,
pages = {195-208}
}
@InCollection{tho90,
author = {W. Thomas},
title = {Automata on infinite objects},
booktitle = {Handbook of Theoretical Computer Science},
publisher = {Elesevier},
year = 1990,
editor = {J. van Leeuwen},
volume = {B},
address = {Amsterdam},
pages = {133-191}
}
@InProceedings{tod90,
author = {S. Toda},
title = {The complexity of finding medians},
booktitle = {Proceedings 31st Symposium on Foundations of Computer Science},
year = 1990,
publisher = {IEEE Computer Society Press},
pages = {778-787}
}
@Article{tod91,
author = {S. Toda},
title = {{PP} is as hard as the polynomial time hierarchy},
journal = {SIAM Journal on Computing},
year = 1991,
volume = 20,
pages = {865-877}
}
@Article{toog92,
author = {S. Toda and M. Ogiwara},
title = {Counting classes are at least as hard as the
polynomial time hierarchy},
journal = {SIAM Journal on Computing},
year = 1992,
volume = 21,
pages = {315-328}
}
@Article{tor91,
author = {J. Toran},
title = {Complexity classes defined by counting quantifiers},
journal = {Journal of the ACM},
year = 1991,
volume = 38,
pages = {753-774}
}
@InCollection{tor93,
author = {J. Tor\'an},
title = {{P}-completeness},
pages = {177-196},
booktitle = {Lectures on Parallel Computation},
publisher = {Cambridge University Press},
year = 1993,
editor = {A. Gibbons and P. Spirakis},
volume = 4,
series = {Cambridge International Series on Parallel Computation},
address = {Cambridge}
}
@Article{towa92,
author = {S. Toda and O. Watanabe},
title = {Polynomial time 1-{T}uring reductions from {\#PH} to {\#P}},
journal = {Theoretical Computer Science},
year = 1992,
volume = 100,
pages = {205-221}
}
@Unpublished{vaa94,
author = {J. V{\"a}{\"a}n\"anen},
title = {A short course on finite model theory},
year = 1994,
note = {Lecture Notes}
}
@Article{val76,
author = {L. G. Valiant},
title = {Relative complexity of checking and evaluation},
journal = {Information Processing Letters},
year = 1976,
volume = 5,
pages = {20-23}
}
@article{val79,
author = {L. G. Valiant},
journal = {{SIAM} Journal of Computing},
number = 3,
pages = {411-421},
title = {The Complexity of enumeration and reliabilty Problems},
volume = 8,
year = 1979
}
@article{vava86,
author = {L. G. Valiant and V. V. Vazirani},
journal = {Theoretical Computer Science},
volume = 47,
pages = {85-93},
title = {{NP} is as easy as detecting unique solutions},
year = 1986
}
@InProceedings{vei96,
author = {H. Veith},
title = {Succinct representation, leaf languages, and
projection reductions},
booktitle = {Proceedings 10th Structure in Complexity Theory},
year = 1996,
publisher = {IEEE Computer Society Press},
pages = {118-126}
}
@PhdThesis{ven86,
author = {H. Venkateswaran},
title = {Characterizations of Parallel Complexity Classes},
school = {Department of Computer Science, University of Washington},
year = 1986
}
@Article{ven91,
author = {H. Venkateswaran},
title = {Properties that characterize {LOGCFL}},
journal = {Journal of Computer and System Sciences},
year = 1991,
volume = 43,
pages = {380-404}
}
@article{ver93a,
author = {N. K. Vereshchagin},
title = {Relativizable and non-relativizable theorems in the
polynomial theory of algorithms},
journal = {Izvestija Rossijskoj Akademii Nauk},
pages = {51-90},
volume = 57,
year = 1993,
note = {In Russian.}
}
@InProceedings{ver93b,
author = {N. K. Vereshchagin},
title = {Relationships between {NP}-sets, {Co-NP}-sets, and
{P}-sets relative to random oracles},
booktitle = {Proceedings 8th Structure in Complexity Theory},
year = 1993,
publisher = {IEEE Computer Society Press},
pages = {132-138}
}
@InProceedings{vol90,
author = {H. Vollmer},
title = {The gap-language technique revisited},
booktitle = {4th Computer Science Logic, Selected Papers},
volume = 533,
series = {Lecture Notes in Computer Science},
year = 1990,
publisher = {Springer Verlag},
pages = {389-399}
}
@phdthesis{vol94a,
author = {H. Vollmer},
address = {{I}nstitut f{\"u}r {I}nformatik, {G}ermany},
school = {{U}niversit{\"a}t {W}{\"u}rzburg},
title = {{K}omplexit{\"a}tsklassen von {F}unktionen},
year = 1994
}
@Unpublished{vol94a-dt,
author = {H. Vollmer},
title = {{K}omplexit{\"a}tsklassen von {F}unktionen},
year = 1994,
note = {{D}issertation, {U}niversit{\"a}t {W}{\"u}rzburg,
{I}nstitut f{\"u}r {I}nformatik},
}
@InProceedings{vol94b,
author = {H. Vollmer},
booktitle = {Proceedings 11th Symposium on Theoretical Aspects
of Computer Science},
volume = 775,
pages = {449-460},
title = {On different reducibility notions for function classes},
series = {Lecture Notes in Computer Science},
publisher = {Springer Verlag},
year = 1994
}
@InProceedings{vol96,
author = {H. Vollmer},
title = {Relations among parallel and sequential computation models},
booktitle = {Proceedings 2nd Asian Computing Science Conference},
volume = {1179},
series = {Lecture Notes in Computer Science},
year = 1996,
publisher = {Springer Verlag},
pages = {23-32}
}
@TechReport{vol96b,
author = {H. Vollmer},
title = {Succinct inputs, {L}indstr\"om quantifiers, and a general complexity theoretic operator concept},
institution = {Institut f\"ur Informatik, Universit\"at W\"urzburg},
year = 1996,
number = 158
}
@Article{vol97,
author = {H. Vollmer},
title = {Relating polynomial time to constant depth},
journal = {Theoretical Computer Science},
year = 1998,
note = {To appear.}
}
@TechReport{vol97b,
author = {H. Vollmer},
title = {A generalized quantifier concept in computational complexity theory},
institution = {Institut f\"ur Informatik, Universit\"at W\"urzburg},
year = 1997
}
@Article{vowa93,
author = {H. Vollmer and K. W. Wagner},
title = {The complexity of finding middle elements},
journal = {International Journal of Foundations of Computer Science},
year = 1993,
volume = 4,
pages = {293-307}
}
@Article{vowa95,
author = {H. Vollmer and K. W. Wagner},
title = {Complexity classes of optimization functions},
journal = {Information and Computation},
year = 1995,
volume = 120,
pages = {198-219}
}
@InCollection{vowa97,
author = {H. Vollmer and K. W. Wagner},
title = {Measure one results in computational complexity theory},
booktitle = {Advances in Algorithms, Languages, and Complexity},
publisher = {Kluwer Academic Publishers},
year = 1997,
editor = {D.-Z. Du and K.-I. Ko}
}
@InProceedings{vowa97b,
author = {H. Vollmer and K. W. Wagner},
title = {On operators of higher types},
booktitle = {Proceedings 12th Conference on Computational Complexity},
year = {1997},
publisher = {IEEE Computer Society Press},
pages = {174-184}
}
@Book{vol99,
author = {H. Vollmer},
title = {Introduction to Circuit Complexity -- A Uniform Approach},
publisher = {Springer Verlag},
year = 1999,
series = {Texts in Theoretical Computer Science},
address = {Berlin Heidelberg}
}
@Article{wag86,
author = {K. W. Wagner},
title = {Some observations on the connection between counting
and recursion},
journal = {Theoretical Computer Science},
year = 1986,
volume = 47,
pages = {131-147}
}
@Article{wag86b,
author = {K. W. Wagner},
title = {The complexity of combinatorial problems with
succinct input representation},
journal = {Acta Informatica},
year = 1986,
volume = 23,
pages = {325-356}
}
@Article{wag87,
author = {K. W. Wagner},
title = {More complicated questions about maxima and minima, and some closures of {NP}},
journal = {Theoretical Computer Science},
year = 1987,
volume = 51,
pages = {53-80}
}
@Article{wag90,
author = {K. W. Wagner},
title = {Bounded query classes},
journal = {SIAM Journal on Computing},
year = 1990,
volume = 19,
pages = {833-846}
}
@Book{wag94,
author = {K. W. Wagner},
title = {Einf\"uhrung in die Theoretische Informatik -- Grundlagen und Modelle},
publisher = {Springer Verlag},
year = 1994,
address = {Berlin Heidelberg}
}
@Book{wawe86,
author = {K. W. Wagner and G. Wechsung},
title = {Computational Complexity},
publisher = {VEB Verlag der Wissenschaften},
year = 1986,
address = {Berlin}
}
@Book{weg87,
author = {I. Wegener},
title = {The Complexity of Boolean Functions},
publisher = {B. G. Teubner \& John Wiley},
year = 1987,
series = {Wiley-Teubner series in computer science},
address = {Stuttgart}
}
@Article{wil87,
author = {C. Wilson},
title = {Relativized {NC}},
journal = {Mathematical Systems Theory},
year = 1987,
volume = 20,
pages = {13-29}
}
@Article{wil90,
author = {C. Wilson},
title = {On the decomposability of {NC} and {AC}},
journal = {SIAM Journal on Computing},
year = 1990,
volume = 19,
pages = {384-396}
}
@Article{wra77,
author = {C. Wrathall},
title = {Complete sets and the polynomial-time hierarchy},
journal = {Theoretical Computer Science},
year = 1977,
volume = 3,
pages = {23-33}
}
@InProceedings{yao85,
author = {A. C. C. Yao},
title = {Separating the polynomial-time hierarchy by oracles},
booktitle = {Proceedings 26th Foundations of Computer Science},
year = 1985,
publisher = {IEEE Computer Society Press},
pages = {1-10}
}
@InProceedings{yao90,
author = {A. C. C. Yao},
title = {On {ACC} and threshold circuits},
booktitle = {Proceedings 31th Foundations of Computer Science},
year = 1990,
publisher = {IEEE Computer Society Press},
pages = {619-627}
}
@Unpublished{zwi95,
author = {U. Zwick},
title = {Boolean Circuit Complexity},
note = {Scribe Notes, Tel-Aviv University},
year = 1995
}
@string{jacm={Journal of the ACM}}
@Article{AroraS1998,
title={Probabilistic Checking of Proofs: A New Characterization
of~{NP}},
author={Sanjeev Arora and Shmuel Safra},
area={Formal Languages and Complexity Theory},
journal=jacm,
pages={70--122},
month=jan,
year=1998,
volume=45,
number=1,
keywords={Approximation algorithms, complexity hierarchies,
computations on polynomials and finite fields, error-correcting codes,
hardness of approximations, interactive computation, NP-completeness,
probabilistic computation, proof checking, reducibility and
completeness, trade-offs/relations among complexity measures},
general-terms={Algorithms, Theory, Verification},
cr-categories={F.1.2; F.1.3; F.2.1; F.2.2; F.4.1},
preliminary={focs::AroraS1992},
source={http://theory.lcs.mit.edu/~jacm/jacm.bib}
}
@string{tcs = {Theoretical Computer Science}}
@Article{FortnowRS1994,
title={On the power of multi-prover interactive protocols},
author={Lance Fortnow and John Rompel and Michael Sipser},
journal=tcs,
pages={545--557},
month={21~} # nov,
year=1994,
volume=134,
number=2,
source={http://theory.lcs.mit.edu/~dmjones/hbp/tcs/tcs.bib}
}
@string{jacm={Journal of the ACM}}
@Article{LundFKN92,
title={Algebraic Methods for Interactive Proof Systems},
author={Carsten Lund and Lance Fortnow and Howard Karloff and Noam
Nisan},
area={Complexity Theory},
pages={859--868},
journal=jacm,
month=oct,
year=1992,
volume=39,
number=4,
source={http://theory.lcs.mit.edu/~jacm/jacm.bib}
}
@InProceedings{coli89,
author = {A. Condon and R. Lipton},
title = {On the complexity of space bounded interactive proofs},
booktitle = {Proceedings 30th Symposium on Foundations of Computer Science},
pages = {462-467},
year = 1989,
publisher = {IEEE Computer Society Press}
}