Introduction

ABSTRACT

Warmest thanks to Salil Vadhan for this issue's wonderful guest column on pseudorandomness. (His column begins in a few pages.) Future columns include Arnaud Durand, Clemens Lautemann, and Malika More on A Simple Proof of Polylog Counting Ability of First-Order Logic, Jonathan Buss and Tarique Islam on Complexity of Fixed-Parameter Problems, and Jin-Yi Cai on holographic algorithms.

REFERENCES

• 1: V. Arvind , Y. Han , L. Hemachandra , J. Köbler , A. Lozano , M. Mundhenk , M. Ogiwara , U. Schöning , R. Silvestri , T. Thierauf, Reductions to sets of low information content, Complexity theory: current research, Cambridge University Press, New York, NY, 1993
• 2: Vikraman Arvind , Johannes Köbler , Martin Mundhenk, On Bounded Truth-Table, Conjunctive, and Randomized Reductions to Sparse Sets, Proceedings of the 12th Conference on Foundations of Software Technology and Theoretical Computer Science, p.140-151, December 18-20, 1992
• 3: Daniel Pierre Bovet , Pierluigi Crescenzi, Introduction to the theory of complexity, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1994
• 4: {Ber76} L. Berman. On the structure of complete sets. In Proceedings of the 17th IEEE Symposium on Foundations of Computer Science, pages 76--80. IEEE Computer Society, October 1976.
• 5: {CNS95} J. Cai, A. Naik, and D. Sivakumar. On the existence of hard sparse sets under weak reductions. Technical Report 95--31, Department of Computer Science, State University of New York at Buffalo, Buffalo, NY, July 1995.
• 6: Jin-Yi Cai , D. Sivakumar, Sparse hard sets for P: resolution of a conjecture of Hartmanis, Journal of Computer and System Sciences, v.58 n.2, p.280-296, April 1999 [doi>10.1006/jcss.1998.1615]
• 7: Jin-Yi Cai , D. Sivakumar, Resolution of Hartmanis' conjecture for NL-hard sparse sets, Theoretical Computer Science, v.240 n.2, p.257-269, June 17, 2000 [doi>10.1016/S0304-3975(99)00234-0]
• 8: Christian Glaßer , Lane A. Hemaspaandra, A moment of perfect clarity II: consequences of sparse sets hard for NP with respect to weak reductions, ACM SIGACT News, v.31 n.4, p.39-51, Dec. 2000 [doi>10.1145/369836.369838]
• 9: {Gla00} C. Glaßer. Consequences of the existence of sparse sets hard for NP under a subclass of truth-table reductions. Technical Report TR 245, Institut für Informatik, Universität Würzburg, Würzburg, Germany, January 2000.
• 10: Juris Hartmanis , Stephen R. Mahaney, An Eassay about Research on Sparse NP Complete Sets, Proceedings of the 9th Symposium on Mathematical Foundations of Computer Science, p.40-57, September 01-05, 1980
• 11: {Koz06} D. Kozen. Theory of Computation. Springer-Verlag, 2006.
• 12: {Mah82} S. Mahaney. Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis. Journal of Computer and System Sciences, 25(2):130--143, 1982.
• 13: {Mah86} S. Mahaney. Sparse sets and reducibilities. In R. Book, editor, Studies in Complexity Theory, pages 63--118. John Wiley and Sons, 1986.
• 14: {Mah89} S. Mahaney. The Isomorphism Conjecture and sparse sets. In J. Hartmanis, editor, Computational Complexity Theory, pages 18--46. American Mathematical Society, 1989. Proceedings of Symposia in Applied Mathematics #38.
• 15: Mitsunori Ogiwara , Osamu Watanabe, On polynomial-time bounded truth-table reducibility of NP sets to sparse sets, SIAM Journal on Computing, v.20 n.3, p.471-483, June 1991 [doi>10.1137/0220030]
• 16: {RR92} D. Ranjan and P. Rohatgi. On randomized reductions to sparse sets. In Proceedings of the 7th Structure in Complexity Theory Conference, pages 239--242. IEEE Computer Society Press, June 1992.
• 17: Paul Young, How reductions to sparse sets collapse the polynomial-time hierarchy: a primer: Part II restricted polynomial-time reductions, ACM SIGACT News, v.23 n.4, p.83-94, Fall 1992 [doi>10.1145/148080.148084]

INDEX TERMS

Primary Classification:
  A. General Literature
  A.m MISCELLANEOUS