Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Vikraman Arvind , Y. Han , Lane A. Hemachandra , Johannes Köbler , Antoni Lozano , Martin Mundhenk , Mitsunori Ogiwara , Uwe Schöning , Riccardo Silvestri , Thomas Thierauf, Reductions to Sets of Low Information Content, Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.162-173, July 13-17, 1992
	2	José Luis Balcazar , Jose Diaz , Joaquim Gabarro, Structural complexity 1, Springer-Verlag New York, Inc., New York, NY, 1988
	3	~BALCAZAR, J. L., AND SCnON~NG, U. 1985. Bi-immune sets for complexity classes. Math. 5?st. ~Theory 18, 1-10.
	4	Leonard Charles Berman, Polynomial reducibilities and complete sets., 1977
	5	~BooK, R. V. 1974. Tally languages and complexity classes. Inf. Contr. 26, 186-i93.
	6	~BOOK, R., Du, D -Z., AND RUSSO, D. A. 1988. On polynomial and generalized complexity cores. ~In Proceedings of the 3rd Annual Symposium on Stn~cture in Complexity Theory (Washington, ~D.C., June). IEEE, New York, pp. 236-250.
	7	Gregory J. Chaitin, On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers, Journal of the ACM (JACM), v.16 n.3, p.407-422, July 1969  [doi>10.1145/321526.321530]
	8	Shimon Even , Alan L. Selmen , Yacov Yacobi, Hard-core theorems for complexity classes, Journal of the ACM (JACM), v.32 n.1, p.205-217, Jan. 1985  [doi>10.1145/2455.214111]
	9	Philippe Flajolet , Jean-Marc Steyaert, On Sets Having Only Hard Subsets, Proceedings of the 2nd Colloquium on Automata, Languages and Programming, p.446-457, July 29-August 02, 1974
	10	~HARTMANIS, J. 1983. Generahzed Kolmogorov complexity and the structure of feasible computa- ~tions. In Proceedings of the 24th Annual Symposium on the Foundations of Computer Science ~(Tucson, Az., Nov.). IEEE, New York, pp. 439-445.
	11	HARTM,XNIS, J. 1983. On sparse sets in NP. hTf. Proc. Lett. 16, 55-60.
	12	John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	13	Mehdi Jazayeri , William F. Ogden , William C. Rounds, The intrinsically exponential complexity of the circularity problem for attribute grammars, Communications of the ACM, v.18 n.12, p.697-706, Dec. 1975  [doi>10.1145/361227.361231]
	14	Richard M. Karp , Richard J. Lipton, Some connections between nonuniform and uniform complexity classes, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.302-309, April 28-30, 1980, Los Angeles, California, United States  [doi>10.1145/800141.804678]
	15	~Ko, K.-I. 1985. Non-levelable and immune sets in the accepting density hierarchy for NP. Math. ~Systems Theory 18, 189-205.
	16	K.-I. Ko, On the notion of infinite pseudorandom sequences, Theoretical Computer Science, v.48 n.1, p.9-33, Dec., 1986
	17	~Ko, K.-I. 1992. A note on the instance complexity of pseudorandom sets. In Proceedings of the ~7th Annual Symposiitm on Structure in Complexity TheoO, (Boston, Mass., June). IEEE, New ~York, pp. 327-337.
	18	~KOLMOGOROV, A. N. 1965. Three approaches to the quantitative definition of information. Prob. ~bif. Trans. 1, 1-7.
	19	Ming Li , Paul M. B. Vitányi, Kolmogorov complexity and its applications, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	20	~LOVELAND, D. W. 1969. A variant of the Kolmogorov concept of complexity. Inf. Cont. 15, ~510-526.
	21	Nancy Lynch, On Reducibility to Complex or Sparse Sets, Journal of the ACM (JACM), v.22 n.3, p.341-345, July 1975  [doi>10.1145/321892.321895]
	22	~MEYER, A. M., AND MCCREIGHT, E. M. 1971. Computationally complex and pseudorandom ~zero-one valued functions. In Theory of Machines and Computations (Haifa, Israel, Aug.), Z. ~Kohavi and A. Paz, eds. Academic Press, Orlando, Fla., pp. 19-42.
	23	~MEYER, A. g., AND PATERSON, g. P. 1979. With what frequency are apparently intractable
	24	~problems difficult? Tech. Rep. TM-126, Lab. Comput. Sci., MIT, Cambridge, Mass.
	25	P Orponen, A classification of complexity core lattices, Theoretical Computer Science, v.47 n.2, p.121-130, Nov. 1986
	26	Pekka Orponen , David A Russo , Uwe Schöning, Optimal approximations and polynomially levelable sets, SIAM Journal on Computing, v.15 n.2, p.399-408, May 1986  [doi>10.1137/0215027]
	27	Pekka Orponen , Uwe Schöning, The density and complexity of polynomial cores for intractable sets, Information and Control, v.70 n.1, p.54-68, July 1986  [doi>10.1016/S0019-9958(86)80024-9]
	28	Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
	29	~SCHNORR, C. P. 1976. Optimal algorithms for self-reducible problems. In Proceedings of the 3rd ~International Colloquium on Automata, Languages, and Programming (Edinburgh, Scotland, ~July). Edinburgh Univ. Press, Edinburgh, Scotland, pp. 322-337.
	30	Michael Sipser, A complexity theoretic approach to randomness, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.330-335, December 1983  [doi>10.1145/800061.808762]
	31	~WATAnABE, O. 1985. On one-one polynomial time equivalence relations. Theoret. Comput. Sci. ~38 157-165.
	32	~WILBER, R. E. 1983. Randomness and the density of hard problems. In Proceedings of the 24th ~Annual Symposium on the Foundations of Computer Science (Tucson, Az., Nov.). IEEE, New ~York, pp. 335-342.

• Data structures for quadtree approximation and compression Communications of the ACM   28, 9
  Hanan Samet
  
  
• A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
  Kim S. Lee ,  Huizhu Lu ,  D. D. Fisher
  
  
• The GemStone object database management system Communications of the ACM   34, 10
  Paul Butterworth ,  Allen Otis ,  Jacob Stein
  
  
• Putting innovation to work: adoption strategies for multimedia communication systems Communications of the ACM   34, 12
  Ellen Francik ,  Susan Ehrlich Rudman ,  Donna Cooper ,  Stephen Levine
  
  
• An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE conference on Design automation
  Gwo-Dong Chen ,  Daniel D. Gajski