@InProceedings{adl78,
author = {L. Adleman},
title = {Two theorems on random polynomial time},
booktitle = {Proceedings 19th Symposium on Foundations of Computer Science},
year = 1978,
publisher = {IEEE Computer Society Press},
pages = {75-83}
}
@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 Press},
pages = {2-11}
}
@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 Press},
pages = {134-148}
}
@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}
}
@Book{ahhoul74,
author = {A. Aho and J. E. Hopcroft and J. D. Ullman},
title = {The Design and Analysis of Computer Algorithms},
series = {Series in Computer Science and Information Processing},
publisher = {Addison-Wesley},
year = 1974,
address = {Reading, MA}
}
@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},
series = {Lecture Notes in Computer Science 529},
year = 1991,
pages = {1-15},
address = {Berlin},
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-1049}
}
@Article{alhe94,
author = {E. Allender and U. Hertrampf},
title = {Depth reduction for circuits of unbounded fan-in},
journal = {Information and 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{aljimavi98,
author = {E. Allender and J. Jiao and M. Mahajan and V. Vinay},
title = {Non-com\-mu\-ta\-tive arithmetic circuits: depth reduction and size lower bounds},
journal = {Theoretical Computer Science},
year = 1998,
volume = 209,
pages = {47-86}
}
@Article{all89,
author = {E. Allender},
title = {P-uniform circuit complexity},
journal = {Journal of the ACM},
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},
series = {Lecture Notes in Computer Science 450},
year = 1990,
publisher = {Springer-Verlag},
address = {Berlin},
pages = {39--52}
}
@Unpublished{all95,
author = {E. Allender},
title = {Combinatorial Methods in Complexity Theory},
note = {Lecture Notes, Rutgers University, New Brunswick},
year = 1995
}
@Article{all96,
author = {E. Allender},
title = {The permanent requires large uniform circuits},
journal = {Chicago Journal of Theoretical Computer Science},
note = {To appear. A preliminary version appeared as:
A note on uniform circuit lower bounds for the counting hierarchy,
in {\em Proceedings 2nd Computing and Combinatorics Conference},
Lecture Notes in Computer Science 1090,
pages 127--135, Springer-Verlag, Berlin, 1996},
year = 1999,
}
@InProceedings{all96b,
author = {E. Allender},
title = {Circuit complexity before the dawn of the new millennium},
booktitle = {Proceedings 16th Foundations of Software Technology and Theoretical Computer Science},
series = {Lecture Notes in Computer Science 1180},
year = 1996,
address = {Berlin},
publisher = {Springer-Verlag},
pages = {1--18}
}
@Article{all98,
author = {E. Allender},
title = {Making computation count: arithmetic circuits in the nineties},
journal = {SIGACT News},
year = 1998,
volume = 28,
number = 4,
pages = {2-15}
}
@Article{alog96,
author = {E. Allender and M. Ogihara},
title = {Relationships among {PL}, \#{L}, and the determinant},
journal = {RAIRO -- Theoretical Informatics and Applications},
year = 1996,
volume = 30,
pages = {1-21}
}
@InProceedings{alre97,
author = {E. Allender and K. Reinhardt},
title = {Making nondeterminism unambiguous},
booktitle = {Proceedings 37th Symposium on Foundations of Computer Science},
year = 1997,
publisher = {IEEE Computer Society Press},
pages = {244-253}
}
@Article{alwa90,
author = {E. Allender and K. W. Wagner},
title = {Counting hierarchies: polynomial time and constant
depth circuits},
journal = {Bulletin of the EATCS},
year = 1990,
volume = 40,
pages = {182-194}
}
@InProceedings{ambale98,
author = {A. Ambainis and D. A. {Mix Barrington} and H. L{\^e}Thanh},
title = {On counting {$\ACn$} circuits with negative constants},
booktitle = {Proceedings 23rd Mathematical Foundations of Computer Science},
series = {Lecture Notes in Computer Science 1450},
year = 1998,
publisher = {Springer-Verlag},
address = {Berlin},
pages = {409-417}
}
@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}
}
@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}
}
@Article{babosc86,
author = {J. L. Balc\'azar and R. V. Book and U. Sch\"oning},
title = {Sparse sets, lowness, and highness},
journal = {SIAM Journal on Computing},
year = 1986,
volume = 15,
pages = {739-747}
}
@Article{babosc86b,
author = {J. L. Balc\'azar and R. V. Book and U. Sch\"oning},
title = {The polynomial-time hierarchy and sparse oracles},
journal = {Journal of the ACM},
year = 1986,
volume = 33,
pages = {603-617}
}
@Article{bacostth92,
author = {D. A. Mix Barrington and K. Compton and H. Straubing and D. Th\'erien},
title = {Regular languages in {${\rm NC}^1$}},
journal = {Journal of Computer and System Sciences},
year = 1992,
volume = 44,
pages = {478-499}
}
@Book{badiga90,
author = {J. L. Balc\'azar and J. D{\'\i}az and J. Gabarr\'o},
publisher = {Springer-Verlag},
title = {Structural Complexity II},
series = {EATCS Monographs on Theoretical Computer Science},
year = 1990,
address = {Berlin}
}
@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 -- An EATCS series},
year = 1995,
edition = {2nd},
address = {Berlin}
}
@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}
}
@TechReport{bar86,
author = {D. A. Barrington},
title = {A Note on a Theorem of {R}azborov},
institution = {University of Massachusetts},
year = 1986
}
@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 ACM},
year = 1988,
volume = 35,
pages = {941-952}
}
@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}
}
@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 = 1997,
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},
series = {Lecture Notes in Computer Science 415},
year = 1990,
publisher = {Springer-Verlag},
address = {Berlin},
pages = {49-57}
}
@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}
}
@Article{bemcpeth97,
author = {M. Beaudry and P. McKenzie and P. P\'eladeau and D. Th\'erien},
title = {Finite monoids: from word to circuit evaluation},
journal = {SIAM Journal on Computing},
year = 1997,
volume = 26,
pages = {138-152}
}
@Article{ber84,
author = {S. J. Berkowitz},
title = {On computing the determinant in small parallel time using a small number of processors},
journal = {Information Processing Letters},
year = 1984,
volume = 18,
pages = {147-150}
}
@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{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},
}
@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. B. 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 {\em SIAM Journal on Computing}~18:1283}
}
@Book{boje89,
author = {G. S. Boolos and R. C. Jeffrey},
title = {Computability and Logic},
publisher = {Cambridge University Press},
year = 1989
}
@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}
}
@Article{bor82,
author = {A. B. Borodin},
title = {Structured versus general models in computational
complexity},
journal = {L'Enseignement Math\'ematique},
year = 1982,
volume = 30,
pages = {47-65},
note = {Special Issue {\em Logic and Algorithms}, Symposium in honour of Ernst Specker}
}
@InCollection{bosi90,
author = {R. B. Boppana and M. Sipser},
title = {The complexity of finite functions},
booktitle = {Handbook of Theoretical Computer Science},
publisher = {Elsevier},
address = {Amsterdam},
year = 1990,
editor = {J. van Leeuwen},
volume = {A},
pages = {757-804}
}
@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}
}
@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{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 {T}uring machines},
journal = {Theoretical Computer Science},
year = 1995,
volume = 148,
pages = {33-55}
}
@InProceedings{cachha97,
author = {L. Cai and J. Chen and J. H{\aa}stad},
title = {Circuit bottom fan-in and computational power},
booktitle = {Proceedings 12th Computational Complexity},
year = 1997,
publisher = {IEEE Computer Society Press},
pages = {158-164}
}
@InProceedings{cahe89,
author = {J.-Y. Cai and L. Hemachandra},
title = {On the power of parity polynomial time},
booktitle = {Proceedings 6th Symposium on Theoretical Aspects of Computer Science},
series = {Lecture Notes in Computer Science 349},
year = 1989,
publisher = {Springer-Verlag},
address = {Berlin},
pages = {229-239}
}
@InProceedings{cai87,
author = {J. Y. Cai},
title = {Probability one separation of the boolean hierarchy},
booktitle = {Proceedings 4th Symposium on Theoretical
Aspects of Computer Science},
series = {Lecture Notes in Computer Science 38},
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}
}
@Article{camcthvo96,
author = {H. Caussinus and P. McKenzie and D.
Th\'erien and H. Vollmer},
title = {Nondeterministic {NC$^1$} computation},
journal = {Journal of Computer and System Sciences},
year = 1998,
volume = 57,
pages = {200-212}
}
@PhdThesis{cau96,
author = {H. Caussinus},
title = {Contributions {\`a} l'{\'e}tude du non-d{\'e}terminisme res\-treint},
school = {D{\'e}p.\ d'informatique et recherche op{\'e}\-ra\-tion\-nelle, Universit{\'e} de Montr{\'e}al},
year = 1996
}
@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{clkr99,
author = {P. Clote and E. Kranakis},
title = {Boolean Functions and Computation Models},
publisher = {Springer-Verlag},
address = {Berlin},
year = 1999,
note = {To appear}
}
@Article{col88,
author = {R. Cole},
title = {Parallel merge sort},
journal = {SIAM Journal on Computing},
year = 1988,
volume = 17,
pages = {770-785}
}
@Article{coo71,
author = {S. A. Cook},
title = {Characterizations of pushdown machines in terms of time-bounded computers},
journal = {Journal of the ACM},
year = 1971,
volume = 18,
pages = {4-18}
}
@InProceedings{coo71a,
author = {S. A. Cook},
title = {The complexity of theorem proving procedures},
booktitle = {Proceedings 3rd Symposium on Theory of Computing},
year = 1971,
publisher = {ACM Press},
pages = {151-158}
}
@InProceedings{coo79,
author = {S. A. Cook},
title = {Deterministic {CFL}'s are accepted simultaneously in polynomial time and log squared space},
booktitle = {Proceedings 11th Symposium on 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}
}
@Misc{dahoro94,
author = {C. Damm and M. Holzer and P. Rossmanith},
title = {Expressing uniformity via oracles},
howpublished = {manuscript},
year = 94
}
@Book{dev93,
author = {K. Devlin},
title = {The Joy of Sets, Fundamentals of Contemporary Set Theory},
publisher = {Springer-Verlag},
year = 1993,
address = {New York},
series = {Undergraduate Texts in Mathematics},
edition = {2nd}
}
@Article{dolire79,
author = {D. P. Dobkin and R. J. Lipton and S. P. Reiss},
title = {Linear Programming is log-space hard for {P}},
journal = {Information Processing Letters},
year = 1979,
volume = 8,
pages = {96-97}
}
@Book{dun88,
author = {P. E. Dunne},
title = {The Complexity of {B}oolean Networks},
publisher = {Academic Press},
year = 1988,
volume = 29,
series = {A.\,P.\,I.\,C. Studies in Data Processing},
address = {London}
}
@InCollection{ebb85,
author = {H.-D. Ebbinghaus},
title = {Extended logics: The general framework},
booktitle = {Model-Theoretic Logics},
publisher = {Springer-Verlag},
address = {New York},
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,
series = {Perspectives in Mathematical Logic},
address = {Berlin}
}
@Book{ebflth94,
author = {H.-D. Ebbinghaus and J. Flum and W. Thomas},
title = {Mathematical Logic},
publisher = {Springer-Verlag},
year = 1994,
address = {Berlin},
edition = {2nd}
}
@Book{eil76,
author = {S. Eilenberg},
title = {Automata, Languages, and Machines},
publisher = {Academic Press},
year = 1976,
volume = {B},
address = {New York}
}
@Book{eve79,
author = {S. Even},
title = {Graph Algorithms},
publisher = {Computer Science Press},
address = {Rockville, MD},
year = 1979
}
@incollection{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},
series = {SIAM--AMS Proceedings},
volume = 7,
year = 1974
}
@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}
}
@InCollection{fic93,
author = {F. Fich},
title = {The complexity of computation on the parallel random access machine},
booktitle = {Synthesis of Parallel Algorithms},
publisher = {Morgan Kaufmann},
address = {San Mateo, CA},
year = 1993,
editor = {J. H. Reif},
pages = {843-899}
}
@Article{firawi88,
author = {F. Fich and R. Ragde and A. Wigderson},
title = {Relations between concurrent-write models of parallel computation},
journal = {SIAM Journal on Computing},
year = 1988,
volume = 17,
pages = {606-627}
}
@Unpublished{fis74,
author = {M. J. Fischer},
title = {Lectures on Network Complexity},
note = {Universit\"at Frankfurt/Main},
year = 1974
}
@InProceedings{fowy78,
author = {S. Fortune and J. Wyllie},
title = {Parallelism in random access machines},
booktitle = {Proceedings 10th Symposium on Theory of Computing},
year = 1978,
publisher = {ACM Press},
pages = {114-118}
}
@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}
}
@InCollection{gat93,
author = {J. von zur Gathen},
title = {Parallel linear algebra},
booktitle = {Synthesis of Parallel Algorithms},
publisher = {Morgan Kaufmann},
address = {San Mateo, CA},
year = 1993,
editor = {J. H. Reif},
pages = {573-617}
}
@Article{gil77,
author = {J. Gill},
title = {Computational complexity of probabilistic {Turing} machines},
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}
}
@Article{gol82,
author = {Goldschlager, L. M.},
title = {A universal interconnection pattern for parallel computers},
journal = {Journal of the ACM},
year = 1982,
volume = 29,
pages = {1073-1086}
}
@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 = {Institute for Information Systems, Vienna University
of Technology},
year = 1995,
number = {CD-TR-95/76},
note = {An extended abstract appeared in {\em Proceedings
10th Symposium on Logic in Computer Science},
pages 65--78, IEEE Computer Society Press, 1995.}
}
@Article{got95b,
author = {G. Gottlob},
title = {{NP} trees and {Carnap's} modal logic},
journal = {Journal of the ACM},
year = 1995,
volume = 42,
pages = {421-457}
}
@Article{got97,
author = {G. Gottlob},
title = {Relativized logspace and generalized quantifiers
over ordered finite structures},
journal = {Journal of Symbolic Logic},
year = 1997,
volume = 62,
pages = {545-574}
}
@Article{gre73,
author = {S. Greibach},
title = {The hardest context-free language},
journal = {SIAM Journal on Computing},
year = 1973,
volume = 2,
pages = {304-310}
}
@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}
}
@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{halest65,
author = {J. Hartmanis and P. M. {Lewis II} and R. E. Stearns},
title = {Hierarchies of memory limited computations},
booktitle = {Proceedings 6th Symposium on Switching Circuit Theory and Logical Design},
year = 1965,
publisher = {IEEE Computer Society Press},
pages = {179-190}
}
@InProceedings{hamapusztu87,
author = {A. Hajnal and W. Maass and P. Pudl{\'a}k and M. Szegedy and G. Tur{\'a}n},
title = {Threshold circuits of bounded depth},
booktitle = {Proceedings 18th Symposium on Foundations of Computer Science},
year = 1987,
publisher = {IEEE Computer Society Press},
pages = {99-110}
}
@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}
}
@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 Press},
pages = {6-20}
}
@Book{has88,
author = {J. H{\aa}stad},
title = {Computational Limitations of Small Depth Circuits},
publisher = {MIT Press},
year = 1988,
address = {Cambridge, MA}
}
@Article{hast65,
author = {J. Hartmanis and R. E. Stearns},
title = {On the computational complexity of algorithms},
journal = {Transactions of the American Mathematical Society},
year = 1965,
volume = 117,
pages = {285-306}
}
@Book{hawr54,
author = {G. H. Hardy and E. M. Wright},
title = {An Introduction to the Theory of Numbers},
publisher = {Oxford University Press},
address = {Oxford},
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},
publisher = {IEEE Computer Society Press},
year = 1993,
pages = {200-207}
}
@Article{hest66,
author = {F. C. Hennie and R. E. Stearns},
title = {Two-tape simulation of multitape {Turing} machines},
journal = {Journal of the ACM},
year = 1966,
volume = 13,
pages = {533-546}
}
@Book{houl79,
author = {J. E. Hopcroft and J. D. Ullman},
title = {Introduction to Automata Theory, Languages, and Computation},
publisher = {Addison-Wesley},
series = {Series in Computer Science},
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 -- An EATCS Series},
address = {Berlin}
}
@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}
}
@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{imm88b,
author = {N. Immerman},
title = {Nondeterministic space is closed under complementation},
journal = {SIAM Journal on Computing},
year = 1988,
volume = 17,
pages = {935-938}
}
@Article{imm89,
author = {N. Immerman},
title = {Expressibility and parallel complexity},
journal = {SIAM Journal on Computing},
year = 1989,
volume = 18,
pages = {625-638}
}
@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}
}
@Book{imm99,
author = {N. Immerman},
title = {Descriptive Complexity},
publisher = {Springer-Verlag},
series = {Graduate Texts in Computer Science},
year = 1999,
address = {New York}
}
@Book{ito87,
title = {Encyclopedic Dictionary of Mathematics},
publisher = {MIT Press},
year = 1987,
editor = {K. It{\^o}},
address = {Cambridge, MA},
note = {English translation of the third Japanese edition}
}
@Book{jac85,
author = {N. Jacobson},
title = {Basic Algebra},
publisher = {Freeman \& Co.},
year = 1985,
volume = {I},
address = {New York}
}
@Article{jemcth96,
author = {B. Jenner and P. McKenzie and D. Th\'erien},
title = {Logspace and logtime leaf languages},
year = 1996,
journal = {Information and Computation},
volume = 129,
pages = {21-33}
}
@Unpublished{jia92,
author = {J. Jiao},
title = {Some questions concerning circuit counting classes and other low-level complexity classes},
note = {Master's essay, Department of Computer Science, Rutgers University, New Brunswick},
year = 1992
}
@InCollection{joh90,
author = {D. S. Johnson},
title = {A catalog of complexity classes},
booktitle = {Handbook of Theoretical Computer Science},
publisher = {Elsevier},
address = {Amsterdam},
year = 1990,
editor = {J. van Leeuwen},
volume = {A},
pages = {67-161}
}
@Article{jola76,
author = {N. D. Jones and W. T. Laaser},
title = {Complete problems for deterministic polynomial time},
journal = {Theoretical Computer Science},
year = 1976,
volume = 3,
pages = {105-117}
}
@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}
}
@InProceedings{jun85,
author = {H. Jung},
title = {Depth efficient transformations of arithmetic circuits into {Boolean} circuits},
booktitle = {Proceedings Fundamentals of Computation Theory},
series = {Lecture Notes in Computer Science 199},
year = 1985,
address = {Berlin},
publisher = {Springer-Verlag},
pages = {167-173}
}
@Article{kali82,
author = {R. Karp and R. J. Lipton},
title = {Turing machines that take advice},
journal = {L'enseignement math\'ematique},
year = 1982,
volume = 28,
pages = {191-209}
}
@Article{kan82,
author = {R. Kannan},
title = {Circuit-size lower bounds and non-reducibility to sparse sets},
journal = {Information and Control},
year = 1982,
volume = 55,
pages = {40-56}
}
@InCollection{kara90,
author = {R. Karp and V. Ramachandran},
title = {Parallel algorithms for shared-memory machines},
booktitle = {Handbook of Theoretical Computer Science},
publisher = {Elsevier},
address = {Amsterdam},
year = 1990,
editor = {J. van Leeuwen},
volume = {A},
pages = {869-941}
}
@Article{kawi85,
author = {R. Karp and A. Wigderson},
title = {A fast parallel algorithm for the maximal independent set problem},
journal = {Journal of the ACM},
volume = {32},
year = {1985},
pages = {762-773},
}
@Article{kha79,
author = {L. G. Khachian},
title = {A polynomial time algorithm for linear programming},
journal = {Doklady Akademii Nauk SSSR},
year = 1979,
volume = 244,
pages = {1093-1096},
note = {In Russian.}
}
@Book{knuI97,
author = {D. E. Knuth},
title = {The Art of Computer Programming Vol.~I: Fundamental Algorithms},
publisher = {Addison-Wesley},
address = {Reading, MA},
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}
}
@Article{kuc82,
author = {L. Ku{\v{c}}era},
title = {Parallel computation and conflicts in memory access},
journal = {Information Processing Letters},
year = 1982,
volume = 14,
pages = {93-96}
}
@Article{lad75,
author = {R. E. Ladner},
title = {The circuit value problem is log space complete for {P}},
journal = {SIGACT News},
year = 1975,
volume = 7,
number = 1,
pages = {12-20}
}
@Article{lafi80,
author = {R. E. Ladner and M. J. Fischer},
title = {Parallel prefix computation},
journal = {Journal of the ACM},
year = 1980,
volume = 27,
pages = {831-838}
}
@InProceedings{lamcscvo99,
author = {C. Lautemann and P. McKenzie and T. Schwentick and H. Vollmer},
title = {The descriptive complexity approach to {LOGCFL}},
booktitle = {Proceedings 16th Symposium on Theoretical Aspects of Computer Science},
series = {Lecture Notes in Computer Science 1563},
year = 1999,
publisher = {Springer-Verlag},
address = {Berlin},
pages = {444-454}
}
@Book{lan93,
author = {S. Lang},
title = {Algebra},
publisher = {Addison-Wesley},
year = 1993,
address = {Reading, MA},
edition = {3rd}
}
@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}
}
@PhdThesis{lev80,
author = {G. Lev},
title = {Size Bounds and Parallel Algorithms for Networks},
school = {Department of Computer Science, University of Edinburgh},
year = 1980
}
@Article{lewa90,
author = {T. Lengauer and K. W. Wagner},
title = {The binary network flow problem is logspace complete for {P}},
journal = {Theoretical Computer Science},
year = 1990,
volume = 75,
pages = {357-363}
}
@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},
publisher = {IEEE Computer Society Press},
year = 1992,
pages = {185-192}
}
@Misc{lin94,
author = {S. Lindell},
howpublished = {manuscript},
year = 1994,
note = {e-mail communication by Kenneth W. Regan}
}
@Article{liza77,
author = {R. J. Lipton and Y. Zalcstein},
title = {Word problems solvable in logspace},
journal = {Journal of the ACM},
year = 1977,
volume = 24,
pages = {522-526}
}
@Article{lup58,
author = {O. B. Lupanov},
title = {A method of circuit synthesis},
journal = {Izvestia VUZ Radiofizika},
year = 1958,
volume = 1,
pages = {120-140}
}
@Article{mac98,
author = {I. Macarie},
title = {Space-efficient deterministic simulation of probabilistic automata},
journal = {SIAM Journal on Computing},
year = 1998,
volume = 27,
pages = {448-465}
}
@InCollection{masa97,
author = {A. Mateescu and A. Salomaa},
title = {Aspects of classical language theory},
booktitle = {Handbook of Formal Languages},
publisher = {Springer-Verlag},
year = 1997,
editor = {R. Rozenberg and A. Salomaa},
volume = {I},
chapter = 4,
address = {Berlin}
}
@Article{masu92,
author = {E. W. Mayr and A. Subramanian},
title = {The complexity of circuit value and network stability},
journal = {Journal of Computer and System Sciences},
year = 1992,
volume = 44,
pages = {302-323}
}
@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},
series = {Lecture Notes in Computer Science 655},
year = 1993,
publisher = {Springer-Verlag},
pages = {545-554}
}
@Article{may90,
author = {E. W. Mayr},
title = {Basic parallel graph algorithms},
journal = {Computing Supplementum},
year = 1990,
volume = 7,
pages = {69-91}
}
@Book{mcpa71,
author = {R. McNaughton and S. A. Papert},
title = {Counter-Free Automata},
publisher = {MIT Press},
address = {Cambridge, MA},
year = 1971
}
@Article{mcpeth91,
author = {P. McKenzie, P. P\'eladeau and D. Th\'erien},
title = {{NC$^1$}: The Automata-Theoretic Viewpoint},
journal = {Computational Complexity},
year = 1991,
volume = 1,
pages = {330-359}
}
@Book{mcth94,
editor = {P. McKenzie and D. Th\'erien},
title = {Special Issue on Circuit Complexity},
series = {Computational Complexity},
volume = {4(4)},
publisher = {Birkh\"auser},
address = {Basel},
year = 1994
}
@TechReport{mcvowa99,
author = {P. McKenzie and H. Vollmer and K. W. Wagner},
title = {Arithmetic Circuits and Polynomial replacement systems},
institution = {Fachbereich Mathematik und Informatik, Universit\"at W\"urzburg},
year = 1999
}
@Book{meco81,
author = {C. Mead and L. Conway},
title = {Introduction to VLSI Systems},
publisher = {Addison-Wesley},
year = 1981,
address = {Reading, MA}
}
@Book{mei86,
author = {C. Meinel},
title = {Modified Branching Programs and Their Computational Power},
publisher = {Springer-Verlag},
year = 1986,
series = {Lecture Notes in Computer Science 370},
address = {Berlin}
}
@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}
}
@Book{mipa88,
author = {M. L. Minsky and S. A. Papert},
title = {Perceptrons},
publisher = {MIT Press},
year = 1988,
address = {Cambridge, MA},
note = {Expanded edition. Originally published in 1969}
}
@book{pap94,
author = {C. H. Papadimitriou},
publisher = {Addison-Wesley},
address = {Reading, MA},
title = {Computational Complexity},
year = 1994
}
@Book{par94,
author = {I. Parberry},
title = {Circuit Complexity and Neural Networks},
publisher = {MIT Press},
year = 1994,
series = {Foundations of Computing},
address = {Cambridge, MA}
}
@Article{pasc88,
author = {I. Parberry and G. Schnitger},
title = {Parallel computation with threshold functions},
journal = {Journal of Computer and System Sciences},
year = 1988,
volume = 36,
pages = {287-302}
}
@Article{pifi79,
author = {N. J. Pippenger and M. J. Fischer},
title = {Relations among complexity measures},
journal = {Journal of the ACM},
year = 1979,
volume = 26,
pages = {361-381}
}
@Book{pin86,
author = {J. E. Pin},
title = {Varieties of Formal Languages},
publisher = {Plenum Press},
year = 1986,
address = {New York}
}
@InProceedings{pip79,
author = {N. J. 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}
}
@InCollection{rab76,
author = {M. O. Rabin},
title = {Probabilistic algorithms},
booktitle = {Algorithms and Complexity: New Directions and Results},
publisher = {Academic Press},
year = 1976,
editor = {J. Traub},
address = {London},
pages = {21-39}
}
@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 = {In Russian. English translation in {\em Soviet Mathematics Doklady}, 31:354--357, 1985}
}
@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}
}
@Unpublished{reg93,
author = {K. Regan},
title = {Log-time {ATMs} and first-order logic},
note = {Unpublished manuscript},
year = 1993
}
@InCollection{reg97,
author = {K. Regan},
title = {Polynomials and combinatorial definitions of languages},
booktitle = {Complexity Theory Retrospective II},
publisher = {Springer-Verlag},
address = {New York},
year = 1997,
editor = {L. A. Hemaspaandra and A. L. Selman},
pages = {261-293}
}
@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}
}
@Article{rish42,
author = {J. Riordan and C. Shannon},
title = {The number of two-terminal series-parallel networks},
journal = {Journal of Mathematics and Physics},
year = 1942,
volume = 21,
pages = {83-93}
}
@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 System Sciences},
year = 1981,
volume = 21,
pages = {365-383}
}
@Article{sav70,
author = {W. J. Savitch},
title = {Relationships between nondeterministic and deterministic tape complexities},
journal = {Journal of Computer and Systems Sciences},
year = 1970,
volume = 4,
pages = {177-192}
}
@Book{sav76,
author = {J. E. Savage},
title = {The Complexity of Computing},
publisher = {John Wiley \& Sons},
year = 1976,
address = {New York}
}
@Book{sav98,
author = {J. E. Savage},
title = {Models of Computation -- Exploring the Power of Computing},
publisher = {Addison-Wesley},
year = 1998,
address = {Reading, MA}
}
@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},
year = 1986,
series = {Lecture Notes in Computer Science 211}
}
@Book{sch89,
author = {U. Sch{\"o}ning},
title = {Logic for Computer Scientists},
publisher = {Birkh\"auser},
address = {Boston, MA},
year = 1989,
volume = 8,
series = {Progress in Computer Science and Applied Logic}
}
@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}
}
@Book{scpr98,
author = {U. Sch{\"o}ning and R. Pruim},
title = {Gems of Theoretical Computer Science},
publisher = {Springer-Verlag},
year = 1998,
address = {Berlin}
}
@PhdThesis{ser90,
author = {M. J. Serna},
title = {The parallel approximability of {P}-complete problems},
school = {Universitat Polit\`ecnica de Catalunya},
year = 1990
}
@Article{sha38,
author = {C. Shannon},
title = {A symbolic analysis of relay and switching circuits},
journal = {Transactions AIEE},
year = 1938,
volume = 57,
pages = {59-98}
}
@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}
}
@Book{sho67,
author = {J. R. Shoenfield},
title = {Mathematical Logic},
publisher = {Addison-Wesley},
year = 1967,
series = {Series in Logic},
address = {Reading, MA}
}
@Article{shvi81,
author = {Y. Shiloach and U. Vishkin},
title = {Finding the maximum, merging and sorting in a parallel computation model},
journal = {Journal of Algorithms},
year = 1981,
volume = 2,
pages = {88-102}
}
@PhdThesis{sim75,
author = {J. Simon},
title = {On Some Central Problems in Computational Complexity},
school = {Cornell University},
year = 1975
}
@InProceedings{sip83b,
author = {M. Sipser},
title = {Borel sets and circuit complexity},
booktitle = {Proceedings 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}
}
@Book{smo91,
author = {C. Smory{\'n}ski},
title = {Logical Number Theory I},
publisher = {Springer-Verlag},
address = {Berlin},
year = 1991
}
@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. J. Stockmeyer},
title = {The polynomial-time hierarchy},
journal = {Theoretical Computer Science},
year = 1977,
volume = 3,
pages = {1-22}
}
@book{str94,
author = {H. Straubing},
publisher = {Birkh{\"a}user},
address = {Boston, MA},
title = {Finite Automata, Formal Logic, and Circuit Complexity},
year = 1994
}
@Article{stvi84,
author = {L. J. 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}
}
@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}
}
@Article{sze87,
author = {R. Szelepcs\'enyi},
title = {The method of forcing for nondeterministic automata},
journal = {Bulletin of the EATCS},
year = 1987,
volume = 33,
pages = {96-100}
}
@PhdThesis{tan94,
author = {S. Tan},
title = {Calcul et v{\'e}rification parall{\`e}les des probl{\`e}mes d'alg{\`e}bre lin{\'e}aire},
school = {Universit{\'e} de Paris-Sud, U.F.R. Scientifique d'Orsay},
year = 1994
}
@Book{tar83,
author = {R. E. Tarjan},
title = {Data Structures and Network Algorithms},
publisher = {Society for Industrial and Applied Mathematics},
year = 1983,
volume = 44,
series = {CBMS-NSF Regional Conference Series in Applied Mathematics}
}
@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{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}
}
@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{tod92,
author = {S. Toda},
title = {Classes of arithmetic circuits capturing the complexity of computing the determinant},
journal = {IEICE Transactions on Communications/Electronics/Information and Systems},
year = 1992,
volume = {E75-D},
pages = {116-124}
}
@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{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.}
}
@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.}
}
@Unpublished{vaa94,
author = {J. V{\"a}{\"a}n\"anen},
title = {A short course on finite model theory},
year = 1994,
note = {Lecture Notes}
}
@Article{val79b,
author = {L. G. Valiant},
title = {The complexity of computing the permanent},
journal = {Theoretical Computer Science},
year = 1979,
volume = 8,
pages = {189-201}
}
@Article{vaskbera83,
author = {L. Valiant and S. Skyum and S. Berkowitz and C. Rackoff},
title = {Fast parallel computation of polynomials using few processors},
journal = {SIAM Journal on Computing},
year = 1983,
volume = 12,
pages = {641-644}
}
@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
}
@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{ven92,
author = {H. Venkateswaran},
title = {Circuit definitions of non-deterministic complexity classes},
journal = {SIAM Journal on Computing},
year = 1992,
volume = 21,
pages = {655-670}
}
@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}
}
@InProceedings{vin91a,
author = {V. Vinay},
title = {Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits},
booktitle = {Proceedings 6th Structure in Complexity Theory},
year = 1991,
publisher = {IEEE Computer Society Press},
pages = {270-284}
}
@TechReport{vis83,
author = {U. Vishkin},
title = {Synchronous parallel computation -- a survey},
institution = {Courant Institute, New York University},
year = 1983
}
@Article{vis83b,
author = {U. Vishkin},
title = {Implementation of simultaneous memory access in models that forbid it},
journal = {Journal of Algorithms},
year = 1983,
volume = 4,
pages = {45-50}
}
@InProceedings{vol91,
author = {H. Vollmer},
title = {The gap-language technique revisited},
booktitle = {4th Computer Science Logic, Selected Papers},
series = {Lecture Notes in Computer Science 533},
year = 1991,
publisher = {Springer-Verlag},
address = {Berlin},
pages = {389-399}
}
@InProceedings{vol96,
author = {H. Vollmer},
title = {Relations among parallel and sequential computation models},
booktitle = {Proceedings 2nd Asian Computing Science Conference},
series = {Lecture Notes in Computer Science 1179},
year = 1996,
publisher = {Springer-Verlag},
address = {Berlin},
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,
volume = 207,
pages = {159-170}
}
@TechReport{vol97b,
author = {H. Vollmer},
title = {A generalized quantifier concept in computational complexity theory},
institution = {Institut f\"ur Informatik, Universit\"at W\"urzburg},
year = 1998
}
@Article{vol99,
author = {H. Vollmer},
title = {Uniform Characterizations of Complexity Classes},
journal = {SIGACT News},
year = 1999,
volume = 30,
number = 1,
pages = {17-27}
}
@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}
}
@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}
}
@Book{weg89,
author = {I. Wegener},
title = {Effiziente {A}lgorithmen f{\"u}r grundlegende {F}unktionen},
publisher = {B. G. Teubner},
address = {Stuttgart},
year = 1989,
series = {Leitf{\"a}den und Monographien der Informatik}
}
@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. 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. Yao},
title = {On {ACC} and threshold circuits},
booktitle = {Proceedings 31st Foundations of Computer Science},
year = 1990,
publisher = {IEEE Computer Society Press},
pages = {619-627}
}
@Article{zac82,
author = {S. Zachos},
title = {Robustness of probabilistic computational complexity classes under definitional perturbations},
journal = {Information and Control},
year = 1982,
volume = 54,
pages = {143-154}
}
@Article{zan91,
author = {V. Zank\'o},
title = {{\#P}-completeness via many-one reductions},
journal = {International Journal of Foundations of Computer Science},
year = 1991,
volume = 2,
pages = {77-82}
}
@Unpublished{zwi95,
author = {U. Zwick},
title = {Boolean Circuit Complexity},
note = {Scribe Notes, Tel-Aviv University},
year = 1995
}@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.}
}