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