% cj99-02--done

@Article{cj99-02-01,
  author =       "L. Babai and P. Erdos and M. Selkow",
  title =        "Random graph isomorphism",
  journal =      "SIAM Journal on Computing",
  volume =       "9",
  pages =        "628--635",
  year =         "1980",
}

@InProceedings{cj99-02-02,
  author =       "J. Belanger and J. Wang",
  title =        "Isomorphisms of {NP}-complete problems on random instances",
  booktitle =    "Proceedings of the 8th Annual Conference on Structure in Complexity Theory",
  publisher =    "IEEE Computer Society Press",
  address =      "Los Alamitos, CA",
  pages =        "65--74",
  year =         "1993",
}

@Article{cj99-02-03,
  author =       "J. Belanger and J. Wang",
  title =        "No {NP} problems over ranking of distributions are harder",
  journal =      "Theoretical Computer Science",
  volume =       "181",
  pages =        "229--245",
  year =         "1997",
}

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

@Article{cj99-02-05,
  author =       "L. Berman and J. Hartmanis",
  title =        "On isomorphisms and density of {NP} and other complete sets",
  journal =      "SIAM Journal on Computing",
  volume =       "2",
  pages =        "305--322",
  year =         "1977",
}

@Article{cj99-02-06,
  author =       "A. Blass and Y. Gurevich",
  title =        "Randomizing reductions of search problems",
  journal =      "SIAM Journal on Computing",
  volume =       "22",
  pages =        "949--975",
  year =         "1993",
}

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

@InProceedings{cj99-02-08,
  author =       "Y. Gurevich",
  title =        "Complete and incomplete randomized {NP} problems",
  booktitle =    "Proceedings of the 28th Annual Symposium on Foundations of Computer Science",
  publisher =    "IEEE Computer Society Press",
  address =      "Los Alamitos, CA",
  pages =        "111--117",
  year =         "1987",
}

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

@Article{cj99-02-10,
  author =       "Y. Gurevich and S. Shelah",
  title =        "Expected computation time for Hamiltonian path problem",
  journal =      "SIAM Journal on Computing",
  volume =       "16",
  pages =        "486--502",
  year =         "1987",
}

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

@Article{cj99-02-12,
  author =       "D. Johnson",
  title =        "The {NP}-completeness column: an ongoing guide",
  journal =      "Journal of Algorithms",
  volume =       "5",
  pages =        "284--299",
  year =         "1984",
}

@Article{cj99-02-13,
  author =       "K.~Ko",
  title =        "On the definition of some complexity classes of real numbers",
  journal =      "Mathematical Systems Theory",
  volume =       "16",
  pages =        "95--109",
  year =         "1983",
}

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

@Book{cj99-02-15,
  author =       "C. L. Liu",
  title =        "Introduction to Combinatorial Mathematics",
  publisher =    "McGraw-Hill",
  address =      "New York",
  year =         "1968",
}

@PhdThesis{cj99-02-16,
  author =       "R. Venkatesan",
  title =        "Average-Case Intractability",
  school =       "Boston University",
  year =         "1991",
}

@InProceedings{cj99-02-17,
  author =       "R. Venkatesan and L. Levin",
  title =        "Random instances of a graph coloring problem are hard",
  booktitle =    "Proceedings of the 20th Annual Symposium on Theory of Computing",
  publisher =    "ACM Press",
  address =      "New York",
  pages =        "217--222",
  year =         "1988",
}

@InProceedings{cj99-02-18,
  author =       "R. Venkatesan and S. Rajagopalan",
  title =        "Average case intractability of Diophantine and matrix problems",
  booktitle =    "Proceedings of the 24th Annual Symposium on Theory of Computing",
  publisher =    "ACM Press",
  address =      "New York",
  pages =        "632--642",
  year =         "1992",
}

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

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

@Article{cj99-02-21,
  author =       "J. Wang and J. Belanger",
  title =        "On the {NP}-isomorphism problem with respect to random instances",
  journal =      "Journal of Computer and System Sciences",
  volume =       "50",
  pages =        "151--164",
  year =         "1995",
}