% 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",
}