% The Chicago Journal of Theoretical Computer Science, Volume 1999, Article 1
% Bibliography
@InProceedings{cj99-01-01,
author = "A. Amir and R. Beigel and W. I. Gasarch",
title = "Some Connections between Bounded Query Classes and Non-uniform Complexity",
booktitle = "Proceedings of the 5th Structure in Complexity Theory Conference",
year = "1990",
pages = "232--243",
publisher = "IEEE Computer Society Press",
note = "A much expanded version has been submitted to {\em
Information and Computation} and is available via
http://www.eecs.lehigh.edu/$\tilde{~}\,$beigel/",
}
@InProceedings{cj99-01-02,
author = "L. Babai and D. Yu and Y. Grigoryev and D. Mount",
title = {Isomorphism of Graphs with Bounded Eigenvalue Multiplicity},
booktitle = "ACM Symposium on Theory of Computing",
year = "1982",
pages = "310--324",
}
@InProceedings{cj99-01-03,
author = "L. Babai and W. M. Kantor and E. M. Luks",
title = "Computational Complexity and the Classification of Finite Simple Groups",
booktitle = "Proceedings of the IEEE Symposium Foundations of Computer Science",
publisher = "IEEE Computer Society Press",
pages = "162--171",
year = "1983",
}
@Book{cj99-01-04,
author = "J. L. Balc\'{a}zar and J. D\'{\i}az and J. Gabarr\'{o}",
title = "Structural Complexity {I}",
year = "1988",
volume = "11",
series = "EATCS Monographs on Theoretical Computer Science",
publisher = "Springer-Verlag",
address = "Berlin",
}
@Book{cj99-01-05,
author = "J. L. Balc\'{a}zar and J. D\'{\i}az and J. Gabarr\'{o}",
title = "Structural Complexity {II}",
year = "1990",
volume = "22",
series = "EATCS Monographs on Theoretical Computer Science",
publisher = "Springer-Verlag",
address = "Berlin",
}
@PhdThesis{cj99-01-06,
author = "R. Beigel",
title = "Query-Limited Reducibilities",
school = "Stanford University",
year = "1987",
note = "Also available as Report No. STAN-CS-88-1221",
}
@InProceedings{cj99-01-07,
author = "R. Beigel",
title = "A Structural Theorem that Depends Quantitatively on the Complexity of {SAT}",
booktitle = "Proceedings of the 2nd Structure in Complexity Theory Conference",
year = "1987",
month = jun,
pages = "28--32",
publisher = "IEEE Computer Society Press",
}
@Article{cj99-01-08,
author = "R. Beigel",
title = "Bounded Queries to {SAT} and the {B}oolean Hierarchy",
journal = tcs,
volume = "84",
number = "2",
year = "1991",
month = jul,
pages = "199--223",
}
@Article{cj99-01-09,
author = "J. Cai and L. A. Hemachandra",
title = "Enumerative Counting Is Hard",
journal = "Information and Computation",
volume = "82",
number = "1",
pages = "34--44",
month = jul,
year = "1989",
}
@Article{cj99-01-10,
author = "J. Cai and L. A. Hemachandra",
title = "A note on enumerative counting",
journal = "Information Processing Letters",
volume = "38",
number = "4",
pages = "212--219",
year = "1991",
}
@Article{cj99-01-11,
author = "P. J. Cameron",
title = "Finite Permutation Groups and Finite Simple Groups",
journal = "Bulletin of the London Mathematical Society",
volume = "13",
pages = "1--22",
year = "1981",
}
@Article{cj99-01-12,
author = "R. Chang",
title = "On the Query Complexity of Clique Size and Maximum Satisfiability",
journal = jcss,
volume = "53",
number = "2",
month = oct,
year = "1996",
pages = "298--313",
}
@Article{cj99-01-13,
author = "R. Chang and W. I. Gasarch and C. Lund",
title = "On Bounded Queries and Approximation",
journal = sicomp,
volume = "26",
number = "1",
month = feb,
year = "1997",
pages = "188--209",
}
@InProceedings{cj99-01-14,
author = "I. S. Filotti and J. N. Mayer",
title = "A Polynomial-Time Algorithm for Determining the Isomorphism of Graphs of Fixed Genus",
booktitle = "ACM Symposium on Theory of Computing",
year = "1980",
pages = "236--243",
}
@Article{cj99-01-15,
author = "S. Goldwasser and S. Micali and C. Rackoff",
title = "The Knowledge Complexity of Interactive Proof Systems",
journal = "{SIAM} Journal on Computing",
volume = "18",
number = "1",
year = "1989",
pages = "186--208",
}
@Book{cj99-01-16,
author = "G. Hardy and E. Wright",
title = "An Introduction to the Theory of Numbers",
publisher = "Clarendon Press",
address = "Oxford",
year = "1979",
edition = "5th",
}
@Book{cj99-01-17,
author = "C. M. Hoffman",
title = "Group-Theoretic Algorithms and Graph Isomorphism",
series = "Lecture Notes in Computer Science",
publisher = "Springer-Verlag",
address = "Berlin",
volume = "136",
year = "1979",
}
@Article{cj99-01-18,
author = "J. E. Hopcroft and R. E. Tarjan",
title = "A {$V^{2}$} Algorithm for Determining Isomorphism of Planar Graphs",
journal = ipl,
year = "1971",
volume = "1",
number = "1",
pages = "32--34",
}
@InProceedings{cj99-01-19,
author = "J. E. Hopcroft and J. K. Wong",
title = "A Linear Time Algorithm for Isomorphism of Planar Graphs",
booktitle = "ACM Symposium on Theory of Computing",
year = "1974",
pages = "172--184",
}
@Book{cj99-01-20,
author = "J. K{\"o}bler and U. Sch{\"o}ning and J. Tor{\'a}n",
title = "The Graph Isomorphism Problem: Its Structural Complexity",
series = "Progress in Theoretical Computer Science",
publisher = "Birkhauser",
address = "Boston",
year = "1993",
}
@Article{cj99-01-21,
author = "M. W. Krentel",
title = "The Complexity of Optimization Problems",
journal = "Journal of Computer and System Sciences",
pages = "490--509",
year = "1988",
volume = "36",
number = "3",
}
@InCollection{cj99-01-22,
author = "A. Lozano and J. Tor{\'a}n",
title = "On the Nonuniform Complexity of the Graph Isomorphism Problem",
booktitle = "Complexity Theory: Current Research",
pages = "245--273",
year = "1993",
editor = "K. Ambos-Spies and S. Homer and U. Sch{\"o}ning",
publisher = "Cambridge University Press",
address = "Cambridge",
note = "Shorter version in {\em Proceedings of the 7th
Structure in Complexity Theory Conference}, pages
118--129, June 1992",
}
@Article{cj99-01-23,
author = "E. Luks",
title = "Isomorphism of Bounded Valence can be Tested in Polynomial Time",
journal = jcss,
volume = "25",
pages = "42--65",
year = "1982",
}
@Article{cj99-01-24,
author = "R. Mathon",
title = "A Note on the Graph Isomorphism Counting Problem",
journal = "Information Processing Letters",
volume = "8",
pages = "131--132",
year = "1979",
}
@InProceedings{cj99-01-25,
author = "G. L. Miller",
title = "Isomorphism Testing for Graphs of Bounded Genus",
booktitle = "ACM Symposium on Theory of Computing",
year = "1980",
pages = "225--235",
}
@Article{cj99-01-26,
author = "J. C. {Owings, Jr.}",
title = "A Cardinality Version of {B}eigel's Nonspeedup Theorem",
journal = "Journal of Symbolic Logic",
volume = "54",
number = "3",
pages = "761--767",
month = sep,
year = "1989",
}
@Article{cj99-01-27,
author = "J. B. Rosser and L. Schoenfeld",
title = "Approximate Formulas for some Functions of Prime Numbers",
journal = "Illinois Journal of Mathematics",
volume = "6",
year = "1962",
pages = "64--94",
}
@InProceedings{cj99-01-28,
author = "C. P. Schnorr",
title = "Optimal Algorithms for Self-Reducible Problems",
booktitle = "Proceedings of the 3rd International Colloquium on Automata, Language, and Programming (ICALP)",
pages = "322--337",
publisher = "Edinburgh University Press",
address = "Edinburgh",
year = "1976",
}
@Book{cj99-01-29,
author = "U. Sch{\"o}ning",
title = "Complexity and Structure",
series = "Lecture Notes in Computer Science",
publisher = "Springer-Verlag",
address = "Berlin",
volume = "211",
year = "1985",
}
@Article{cj99-01-30,
author = "U. Sch{\"o}ning",
title = "Probabilistic Complexity Classes and Lowness",
journal = jcss,
year = "1989",
month = dec,
volume = "39",
number = "1",
pages = "84--100",
}
@Article{cj99-01-31,
author = "S. Toda",
title = "{PP} Is as Hard as the Polynomial-Time Hierarchy",
journal = "{SIAM} Journal on Computing",
volume = "20",
number = "5",
pages = "865--877",
month = oct,
year = "1991",
}
@Article{cj99-01-32,
author = "L. G. Valiant",
title = "The Complexity of Computing the Permanent",
journal = "Theoretical Computer Science",
year = "1979",
volume = "8",
pages = "189--201",
}