% The Chicago Journal of Theoretical Computer Science, Volume 1999, Article 4
% Bibliography

@Article{cj99-04-01,
  author =       "M. Abadi and J. Feigenbaum and J. Kilian",
  title =        "On hiding information from an oracle",
  journal =      "Journal of Computer and System Sciences",
  year =         "1989",
  volume =       "39",
  pages =        "21--30",
}

@InProceedings{cj99-04-02,
  author =       "L. Adleman and M. Huang",
  title =        "Recognizing primes in random polynomial time",
  booktitle =    "Proceedings of the 19th ACM Symposium on Theory of Computing",
  publisher =    "ACM Press",
  address =      "New York",
  year =         "1987",
  pages =        "462--469",
}

@Article{cj99-04-03,
  author =       "S. Ben{-D}avid and B. Chor and O. Goldreich and M. Luby",
  title =        "On the theory of average case complexity",
  journal =      "Journal of Computer and System Sciences",
  year =         "1992",
  volume =       "44",
  pages =        "193--219",
}

@TechReport{cj99-04-04,
  author =       "A. Borodin and A. Demers",
  title =        "Some comments on functional self-reducibility and the {NP} hierarchy",
  year =         "1976",
  number =       "76-284",
  institution =  "Department of Computer Science, Cornell University",
}

@Book{cj99-04-05,
  author =       "J. L. Balc{\'a}zar and J. D{\'\i}az and J.  Gabarr{\'o}",
  title =        "Structural Complexity {II}",
  year =         "1990",
  series =       "EATCS Monographs on Theoretical Computer Science",
  publisher =    "Springer-Verlag",
  address =      "Berlin",
}

@Book{cj99-04-06,
  author =       "J. L. Balc{\'a}zar and J. D{\'\i}az and J.  Gabarr{\'o}",
  title =        "Structural Complexity {I}",
  edition =      "Second",
  year =         "1995",
  series =       "EATCS Monographs on Theoretical Computer Science",
  publisher =    "Springer-Verlag",
  address =      "Berlin",
}

@Article{cj99-04-07,
  author =       "A. Blass and Y. Gurevich",
  title =        "Randomized reductions of search problems",
  journal =      "SIAM Journal of Computing",
  year =         "1993",
  volume =       "22",
  pages =        "949--975",
  keyword =      "random reduction, search problem",
}

@Article{cj99-04-08,
  author =       "A. Blass and Y. Gurevich",
  title =        "Matrix transformation is complete for the average case",
  journal =      "SIAM Journal on Computing",
  year =         "1995",
  volume =       "24",
  number =       "1",
  pages =        "3--29",
}

@Article{cj99-04-09,
  author =       "R. Boppana and J. Hastad and S. Zachos",
  title =        "Does co-{NP} have short interactive proofs?",
  journal =      "Information Processing Letters",
  year =         "1987",
  volume =       "25",
  pages =        "27--32",
}

@Article{cj99-04-10,
  author =       "M. Blum and S. Kannan",
  title =        "Designing programs to check their work",
  journal =      "Journal of the ACM",
  year =         "1995",
  volume =       "42",
  number =       "1",
  pages =        "269--291",
}

@Article{cj99-04-11,
  author =       "L. Babai and S. Moran",
  title =        "Arthur-Merlin games: a randomized proof system and a hierarchy of complexity classes",
  journal =      "Journal of Computer and System Sciences",
  year =         "1988",
  volume =       "36",
  pages =        "254--276",
}

@InCollection{cj99-04-12,
  author =       "J. L. Balc{\'a}zar",
  title =        "Self-reducibility structures and solutions of {NP} problems",
  booktitle =    "Revista Matematica",
  year =         "1989",
  volume =       "2, No.~2/3",
  pages =        "175--184",
  publisher =    "Universidad Complutense de Madrid",
  address =      "Madrid",
}

@Article{cj99-04-13,
  author =       "R. Book",
  title =        "Tally languages and complexity classes",
  journal =      "Information and Control",
  year =         "1974",
  volume =       "26",
  pages =        "186--193",
}

@Article{cj99-04-14,
  author =       "J. L. Carter and M. N. Wegman",
  title =        "Universal classes of hash functions",
  journal =      "Journal of Computer and System Sciences",
  year =         "1979",
  volume =       "18",
  pages =        "143--154",
}

@InCollection{cj99-04-15,
  author =       "P. J. Cameron",
  title =        "Permutation Groups",
  booktitle =    "Handbook Of Combinatorics",
  chapter =      "12",
  editor =       "R. Graham and M. Gr{\"o}tschel and L. Lov{\'a}sz",
  year =         "1995",
  pages =        "611--645",
  publisher =    "Elsevier",
  address =      "Amsterdam",
  keyword =      "permutation groups",
}

@Article{cj99-04-16,
  author =       "Y. Gurevich",
  title =        "Average case completeness",
  journal =      "Journal of Computer and System Sciences",
  year =         "1991",
  volume =       "42",
  number =       "3",
  pages =        "346--398",
}

@Book{cj99-04-17,
  author =       "C. M. Hoffmann",
  title =        "Group-Theoretic Algorithms and Graph Isomorphism",
  year =         "1982",
  series =       "Lecture Notes in Computer Science",
  volume =       "136",
  publisher =    "Springer-Verlag",
  address =      "Berlin",
}

@Book{cj99-04-18,
  author =       "J. F. Humphreys",
  title =        "A Course in Group Theory",
  year =         "1996",
  publisher =    "Oxford Science Publications",
  address =      "Oxford",
}

@InProceedings{cj99-04-19,
  author =       "R. Impagliazzo and L. A. Levin",
  title =        "No better ways to generate hard {NP}-instances than picking uniformly at random",
  booktitle =    "Proceedings of the 31st IEEE Symposium on the Foundations of Computer Science",
  year =         "1990",
  pages =        "812--821",
  publisher =    "IEEE Computer Society Press",
  address =      "Los Alamitos, CA",
}

@InProceedings{cj99-04-20,
  author =       "M. Jerrum",
  title =        "A compact representation for permutation groups",
  booktitle =    "Proceedings of the 23rd IEEE Symposium on the Foundations of Computer Science",
  year =         "1982",
  pages =        "126--133",
  publisher =    "IEEE Computer Society Press",
  address =      "Los Alamitos, CA",
}

@Article{cj99-04-21,
  author =       "K.-I. Ko and H. Friedman",
  title =        "Computational complexity of real functions",
  journal =      "Theoretical Computer Science",
  year =         "1982",
  volume =       "20",
  pages =        "323--352",
}

@Book{cj99-04-22,
  author =       "J. K{\"o}bler and U. Sch{\"o}ning and J. Tor{\'a}n",
  title =        "The Graph Isomorphism Problem: Its Structural Complexity",
  year =         "1993",
  publisher =    "Birkh{\"a}user",
  address =      "Boston",
}

@InProceedings{cj99-04-23,
  author =       "C. Karg",
  title =        "{LR($k$)} Testing is Average-Case Complete",
  booktitle =    "Proceedings of the 12th Annual IEEE Conference on Computational Complexity",
  year =         "1997",
  pages =        "74--80",
  publisher =    "IEEE Computer Society Press",
  address =      "Los Alamitos, CA",
}

@InCollection{cj99-04-24,
  author =       "A. Lozano and J. Tor{\'a}n",
  title =        "On the Nonuniform Complexity of the Graph Isomorphism Problem",
  booktitle =    "Complexity Theory, Current Research",
  editor =       "K. Ambos-Spies and S. Homer and U. Sch{\"o}ning",
  year =         "1993",
  pages =        "1--45",
  publisher =    "Cambridge University Press",
  address =      "Cambridge",
}

@Article{cj99-04-25,
  author =       "L. Levin",
  title =        "Average case complete problems",
  journal =      "SIAM Journal on Computing",
  year =         "1986",
  volume =       "15",
  pages =        "285--286",
}

@Book{cj99-04-26,
  author =       "C. Papadimitriou",
  title =        "Computational Complexity",
  year =         "1994",
  publisher =    "Addison-Wesley",
  address =      "Reading, MA",
}

@InProceedings{cj99-04-27,
  author =       "C. Schnorr",
  title =        "Optimal algorithms for self-transformable problems",
  booktitle =    "Proceedings of the 3rd International Colloquium on Automata, Languages, and Programming",
  year =         "1976",
  pages =        "322--337",
  publisher =    "Edinburgh University Press",
  address =      "Edinburgh",
}

@Article{cj99-04-28,
  author =       "U. Sch{\"o}ning",
  title =        "Graph isomorphism is in the low hierarchy",
  journal =      "Journal of Computer and System Sciences",
  year =         "1988",
  volume =       "37",
  pages =        "312--323",
}

@InProceedings{cj99-04-29,
  author =       "M. Sipser",
  title =        "A complexity theoretic approach to randomness",
  booktitle =    "Proceedings of the 15th ACM Symposium on Theory of Computing",
  year =         "1983",
  pages =        "330--335",
  publisher =    "ACM Press",
  address =      "New York",
}

@InProceedings{cj99-04-30,
  author =       "W. Tompa and H. Woll",
  title =        "Random self-reducibility and zero-knowledge interactive proofs of possession of information",
  booktitle =    "Proceedings of the 28th IEEE Symposium on the Foundations of Computer Science",
  year =         "1987",
  pages =        "472--482",
  publisher =    "IEEE Computer Society Press",
  address =      "Los Alamitos, CA",
}

@Article{cj99-04-31,
  author =       "L. Valiant and V. Vazirani",
  title =        "{NP} is as easy as detecting unique solutions",
  journal =      "Theoretical Computer Science",
  year =         "1986",
  volume =       "47",
  pages =        "85--93",
}

@Article{cj99-04-32,
  author =       "J. Wang and J. Belanger",
  title =        "On the {NP}-Isomorphism Problem with Respect to Random Instances",
  journal =      "Journal of Computer and System Sciences",
  year =         "1995",
  volume =       "50",
  pages =        "151--164",
}

@InProceedings{cj99-04-33,
  author =       "J. Wang",
  title =        "Average-Case completeness of a word problem for groups",
  booktitle =    "Proceedings of the 27th ACM Symposium on Theory of Computing",
  year =         "1995",
  pages =        "325--334",
  publisher =    "ACM Press",
  address =      "New York",
}

@InCollection{cj99-04-34,
  author =       "J. Wang",
  title =        "Average-Case computational complexity theory",
  booktitle =    "Complexity Theory Retrospective 2",
  editor =       "L. A. Hemaspaandra and A. L. Selman",
  year =         "1997",
  pages =        "295--328",
  publisher =    "Springer-Verlag",
  address =      "Berlin",
}

@InProceedings{cj99-04-35,
  author =       "O. Watanabe",
  title =        "Test Instance Generation for Promised {NP} Search Problems",
  booktitle =    "Proceedings of the 9th Structure in Complexity Theory Conference",
  year =         "1994",
  pages =        "205--216",
  publisher =    "IEEE Computer Society Press",
  address =      "Los Alamitos, CA",
  keyword =      "test instance generation, search problem, average case complexity",
}