Resource-Bounded Measure Bibliography

Maintained by John Hitchcock. Also available in PostScript and PDF.
See also the Effective Fractal Dimension Bibliography.

[1] E. Allender.
Circuit complexity before the dawn of the new millennium.
In Proceedings of the 16th Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 1-18.
Springer-Verlag, 1996.
[ PDF ]

[2] E. Allender.
When worlds collide: Derandomization, lower bounds, and Kolmogorov complexity.
In Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science, pages 1-15.
Springer-Verlag, 2001.
[ PDF ]

[3] E. Allender and M. Strauss.
Measure on small complexity classes with applications for BPP.
In Proceedings of the 35th Symposium on Foundations of Computer Science, pages 807-818.
IEEE Computer Society, 1994.
[ PDF ]

[4] E. Allender and M. Strauss.
Measure on P : Robustness of the notion.
In Proceedings of the 20th International Symposium on Mathematical Foundations of Computer Science, pages 129-138.
Springer-Verlag, 1995.
[ PDF ]

[5] K. Ambos-Spies.
Measure theoretic completeness notions for the exponential time classes.
In Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science, pages 152-161.
Springer-Verlag, 2000.

[6] K. Ambos-Spies and L. Bentzien.
Separating NP-completeness notions under strong hypotheses.
Journal of Computer and System Sciences, 61(3):335-361, 2000.

[7] K. Ambos-Spies, S. Lempp, and G. Mainhardt.
Randomness vs. completeness: On the diagonalization strength of resource-bounded random sets.
In Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science, pages 465-473.
Springer-Verlag, 1998.

[8] K. Ambos-Spies and E. Mayordomo.
Resource-bounded measure and randomness.
In A. Sorbi, editor, Complexity, Logic and Recursion Theory, Lecture Notes in Pure and Applied Mathematics, pages 1-47.
Marcel Dekker, New York, N.Y., 1997.
[ PostScript (gzipped) ]

[9] K. Ambos-Spies, E. Mayordomo, Y. Wang, and X. Zheng.
Resource-bounded balanced genericity, stochasticity, and weak randomness.
In Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science, pages 63-74.
Springer-Verlag, 1996.
[ PostScript (gzipped) ]

[10] K. Ambos-Spies, E. Mayordomo, and X. Zheng.
A comparison of weak completeness notions.
In Proceedings of the Eleventh IEEE Conference on Computational Complexity, pages 171-178.
IEEE Computer Society, 1996.
[ PostScript (gzipped) ]

[11] K. Ambos-Spies, W. Merkle, J. Reimann, and S. A. Terwijn.
Almost complete sets.
Theoretical Computer Science, 306(1-3):177-194, 2003.
[ PostScript | PDF ]

[12] K. Ambos-Spies, H.-C. Neis, and S. A. Terwijn.
Genericity and measure for exponential time.
Theoretical Computer Science, 168(1):3-19, 1996.
[ PostScript ]

[13] K. Ambos-Spies, S. A. Terwijn, and X. Zheng.
Resource bounded randomness and weakly complete problems.
Theoretical Computer Science, 172(1-2):195-207, 1997.
[ PostScript | PostScript ]

[14] V. Arvind and J. Köbler.
On pseudorandomness and resource-bounded measure.
Theoretical Computer Science, 255(1-2):205-221, 2001.

[15] R. V. Book and J. H. Lutz.
On languages with very high space-bounded Kolmogorov complexity.
SIAM Journal on Computing, 22(2):395-402, 1993.

[16] R. V. Book and E. Mayordomo.
On the robustness of ALMOST-R.
Rairo Informatique Théorique et Applications, 30(2):123-133, 1996.
[ PostScript (gzipped) ]

[17] J. M. Breutzmann and J. H. Lutz.
Equivalence of measures of complexity classes.
SIAM Journal on Computing, 29(1):302-326, 2000.
[ PostScript ]

[18] H. Buhrman, S. Fenner, and L. Fortnow.
Results on resource-bounded measure.
In Proceedings of the 24th International Colloquium on Automata, Languages and Programming, pages 188-194.
Springer-Verlag, 1997.
[ DOI | PostScript ]

[19] H. Buhrman and L. Fortnow.
Two queries.
Journal of Computer and System Sciences, 59(2):182-194, 1999.
[ DOI | PostScript ]

[20] H. Buhrman, B. Hescott, S. Homer, and L. Torenvliet.
Non-uniform reductions.
Theory of Computing Systems. To appear.
[ DOI | Abstract | PostScript | PDF ]

[21] H. Buhrman and L. Longpré.
Compressibility and resource bounded measure.
SIAM Journal on Computing, 31(3):876-886, 2002.

[22] H. Buhrman and E. Mayordomo.
An excursion to the Kolmogorov random strings.
Journal of Computer and System Sciences, 54(3):393-399, 1997.
[ PostScript (gzipped) ]

[23] H. Buhrman and L. Torenvliet.
On the structure of complete sets.
In Proceedings of the Ninth Annual Structure in Complexity Theory Conference, pages 118-133.
IEEE Computer Society, 1994.

[24] H. Buhrman and L. Torenvliet.
Complete sets and structure in subrecursive classes.
In Logic Colloquium '96, volume 12 of Lecture Notes in Logic, pages 45-78.
Association for Symbolic Logic, 1998.

[25] H. Buhrman and D. van Melkebeek.
Hard sets are hard to find.
Journal of Computer and System Sciences, 59(2):327-345, 1999.
[ Abstract | PostScript ]

[26] H. Buhrman, D. van Melkebeek, K. W. Regan, D. Sivakumar, and M. Strauss.
A generalization of resource-bounded measure, with application to the BPP vs. EXP problem.
SIAM Journal on Computing, 30(2):576-601, 2001.
[ Abstract | PostScript ]

[27] J. Cai and A. L. Selman.
Fine separation of average time complexity classes.
SIAM Journal on Computing, 28(4):1310-1325, 1999.

[28] J. Cai, D. Sivakumar, and M. Strauss.
Constant-depth circuits and the Lutz hypothesis.
In Proceedings of the 38th Symposium on Foundations of Computer Science, pages 595-604.
IEEE Computer Society, 1997.

[29] C. Calude and M. Zimand.
Effective category and measure in abstract complexity theory.
Theoretical Computer Science, 154(2):307-327, 1996.
[ PostScript ]

[30] R. Chang and S. Purini.
Bounded queries and the NP machine hypothesis.
In Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, pages 52-59.
IEEE Computer Society, 2007.

[31] J. J. Dai.
A stronger Kolmogorov zero-one law for resource-bounded measure.
Theoretical Computer Science, 292(3):723-732, 2003.

[32] J. J. Dai.
An outer-measure approach for resource-bounded measure.
Theory of Computing Systems, 45(1):64-73, 2009.
[ DOI ]

[33] J. J. Dai and J. H. Lutz.
Query order and NP-completeness.
In Proceedings of the 14th IEEE Conference on Computational Complexity, pages 142-148.
IEEE Computer Society, 1999.
[ PostScript ]

[34] D. Doty and P. Moser.
Feasible depth.
In Proceedings of the 3rd Conference on Computability in Europe.
Springer-Verlag, 2007. To appear.
[ DOI | Abstract | PostScript | PDF ]

[35] T. Ebert, W. Merkle, and H. Vollmer.
On the autoreducibility of random sequences.
SIAM Journal on Computing, 32(6):1542-1569, 2003.
[ PostScript | PDF ]

[36] S. A. Fenner, J. H. Lutz, E. Mayordomo, and P. Reardon.
Weakly useful sequences.
Information and Computation, 197(1-2):41-54, 2005.
[ PostScript ]

[37] L. Fortnow.
Relativized worlds with an infinite hierarchy.
Information Processing Letters, 69(6):309-313, 1999.
[ DOI | PostScript ]

[38] L. Fortnow and M. Kummer.
On resource-bounded instance complexity.
Theoretical Computer Science, 161(1-2):123-140, 1996.
[ DOI | PostScript ]

[39] L. Fortnow, J. H. Lutz, and E. Mayordomo.
Inseparability and strong hypotheses for disjoint np pairs.
Technical Report TR09-022, Electronic Colloquium on Computational Complexity, 2009.
[ Abstract | Abstract ]

[40] L. Fortnow, A. Pavan, and A. L. Selman.
Distributionally hard languages.
Theory of Computing Systems, 34(3):245-261, 2001.
[ DOI | Abstract | PostScript | PDF ]

[41] E. Grädel and A. Malmström.
0-1 laws for recursive structures.
Archive for Mathematical Logic, 38(4):205-215, 1999.
[ Abstract | PostScript ]

[42] R. C. Harkins and J. M. Hitchcock.
Upward separations and weaker hypotheses in resource-bounded measure.
Theoretical Computer Science, 389(1-2), 2007.
[ DOI | Abstract | PostScript | PDF ]

[43] R. C. Harkins, J. M. Hitchcock, and A. Pavan.
Stronger reductions and isomorphism of complete sets.
In Proceedings of the 27th International Conference on Foundations of Software Technology and Theoretical Computer Science, pages 168-178.
Springer-Verlag, 2007.
[ DOI | Abstract | PostScript | PDF ]

[44] M. Hauptmann.
The measure hypothesis and efficiency of polynomial time approximation schemes.
In Proceedings of the Tenth Italian Conference on Theoretical Computer Science, pages 151-163. World Scientific, 2007.
[ Abstract | PostScript (gzipped) ]

[45] L. A. Hemachandra, M. Ogiwara, and O. Watanabe.
How hard are sparse sets?
In Proceedings of the Seventh Annual Structure in Complexity Theory Conference, pages 222-238.
IEEE Computer Society Press, 1992.

[46] J. M. Hitchcock.
The size of SPP.
Theoretical Computer Science, 320(2-3):495-503, 2004.
[ DOI | Abstract | PostScript | PDF ]

[47] J. M. Hitchcock and J. H. Lutz.
Why computational complexity requires stricter martingales.
Theory of Computing Systems, 39(2):277-296, 2006.
[ DOI | Abstract | PostScript | PDF ]

[48] J. M. Hitchcock and A. Pavan.
Comparing reductions to NP-complete sets.
Information and Computation, 205(5):694-706, 2007.
[ DOI | Abstract | PostScript | PDF ]

[49] R. Impagliazzo and P. Moser.
A zero-one law for RP and derandomization of AM if NP is not small.
Information and Computation, 207(7):787 - 792, 2009.
[ DOI ]

[50] G. Istrate.
Resource-bounded measure and autoreducibility.
Technical Report 644, Department of Computer Science, University of Rochester, December 1996.

[51] D. W. Juedes.
The Complexity and Distribution of Computationally Useful Problems.
PhD thesis, Iowa State University, 1994.

[52] D. W. Juedes.
Weakly complete problems are not rare.
Computational Complexity, 5(3/4):267-283, 1995.

[53] D. W. Juedes, J. I. Lathrop, and J. H. Lutz.
Computational depth and reducibility.
Theoretical Computer Science, 132(1-2):37-70, 1994.
[ PostScript ]

[54] D. W. Juedes and J. H. Lutz.
Kolmogorov complexity, complexity cores, and the distribution of hardness.
In O. Watanabe, editor, Kolmogorov Complexity and Computational Complexity, pages 43-65.
Springer-Verlag, 1992.
[ PostScript ]

[55] D. W. Juedes and J. H. Lutz.
The complexity and distribution of hard problems.
SIAM Journal on Computing, 24(2):279-295, 1995.
[ PostScript ]

[56] D. W. Juedes and J. H. Lutz.
Weak completeness in E and E2.
Theoretical Computer Science, 143(1):149-158, 1995.
[ PostScript ]

[57] D. W. Juedes and J. H. Lutz.
Completeness and weak completeness under polynomial-size circuits.
Information and Computation, 125(1):13-31, 1996.
[ PostScript ]

[58] S. M. Kautz.
Resource-bounded randomness and compressibility with respect to nonuniform measures.
In Proceedings of the International Workshop on Randomization and Approximation Techniques in Computer Science, pages 197-211.
Springer-Verlag, 1997.
[ PDF ]

[59] S. M. Kautz and P. B. Miltersen.
Relative to a random oracle, NP is not small.
Journal of Computer and System Sciences, 53(2):235-250, 1996.
[ PDF ]

[60] J. Köbler and W. Lindner.
On the resource bounded measure of P/poly.
In Proceedings of the 13th IEEE Conference on Computational Complexity, pages 182-185.
IEEE Computer Society, 1998.

[61] J. Köbler and W. Lindner.
On distribution-specific learning with membership queries versus pseudorandom generation.
In Proceedings of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science, pages 336-347.
Springer-Verlag, 2000.

[62] J. Köbler, W. Lindner, and R. Schuler.
Derandomizing RP if Boolean circuits are not learnable.
Technical Report UIB-1999-05, Universität Ulm, 1999.
[ Abstract | PostScript | PDF ]

[63] J. Köbler and R. Schuler.
Average-case intractability vs. worst-case intractability.
In Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science, pages 493-502.
Springer-Verlag, 1998.

[64] J. I. Lathrop and J. H. Lutz.
Recursive computational depth.
Information and Computation, 153(2):139-172, 1999.
[ PostScript ]

[65] W. Lindner.
On the polynomial time bounded measure of one-truth-table degrees and p-selectivity.
Diplomarbeit, Technische Universität Berlin, 1993.

[66] W. Lindner and R. Schuler.
A small span theorem within P.
Technical Report UIB-1997-02, Universität Ulm, 1997.
[ Abstract | PostScript | PDF ]

[67] W. Lindner, R. Schuler, and O. Watanabe.
Resource-bounded measure and learnability.
Theory of Computing Systems, 33(2):151-170, 2000.

[68] A. K. Lorentz and J. H. Lutz.
Genericity and randomness over feasible probability measures.
Theoretical Computer Science, 207(1):245-259, 1998.
[ PostScript ]

[69] J. H. Lutz.
One-way functions and balanced NP.
Theoretical Computer Science. To appear.
[ PostScript ]

[70] J. H. Lutz.
Resource-Bounded Category and Measure in Exponential Complexity Classes.
PhD thesis, California Institute of Technology, 1987.
[ Abstract | PostScript | PDF ]

[71] J. H. Lutz.
Category and measure in complexity classes.
SIAM Journal on Computing, 19(6):1100-1131, 1990.

[72] J. H. Lutz.
Pseudorandom sources for BPP.
Journal of Computer and System Sciences, 41(3):307-320, 1990.

[73] J. H. Lutz.
An upward measure separation theorem.
Theoretical Computer Science, 81(1):127-135, 1991.
[ PostScript ]

[74] J. H. Lutz.
Almost everywhere high nonuniform complexity.
Journal of Computer and System Sciences, 44(2):220-258, 1992.
[ PostScript ]

[75] J. H. Lutz.
On independent random oracles.
Theoretical Computer Science, 92:301-307, 1992.
[ PostScript ]

[76] J. H. Lutz.
A pseudorandom oracle characterization of BPP.
SIAM Journal on Computing, 22(5):1075-1086, 1993.
[ PostScript ]

[77] J. H. Lutz.
A small span theorem for P/Poly-Turing reductions.
In Proceedings of the Tenth Annual Structure in Complexity Theory Conference, pages 324-330.
IEEE Computer Society, 1995.
[ PostScript ]

[78] J. H. Lutz.
Weakly hard problems.
SIAM Journal on Computing, 24(6):1170-1189, 1995.
[ PostScript ]

[79] J. H. Lutz.
Observations on measure and lowness for ΔP2.
Theory of Computing Systems, 30(4):429-442, 1997.
[ PostScript ]

[80] J. H. Lutz.
The quantitative structure of exponential time.
In L. A. Hemaspaandra and A. L. Selman, editors, Complexity Theory Retrospective II, pages 225-254.
Springer-Verlag, 1997.
[ PostScript ]

[81] J. H. Lutz.
Resource-bounded measure.
In Proceedings of the 13th IEEE Conference on Computational Complexity, pages 236-248.
IEEE Computer Society, 1998.

[82] J. H. Lutz.
Computability versus exact computability of martingales.
Information Processing Letters, 92(5):235-237, 2004.
[ PostScript ]

[83] J. H. Lutz and E. Mayordomo.
Measure, stochasticity, and the density of hard languages.
SIAM Journal on Computing, 23(4):762-779, 1994.
[ PostScript ]

[84] J. H. Lutz and E. Mayordomo.
Cook versus Karp-Levin: Separating completeness notions if NP is not small.
Theoretical Computer Science, 164(1-2):141-163, 1996.
[ PostScript ]

[85] J. H. Lutz and E. Mayordomo.
Twelve problems in resource-bounded measure.
Bulletin of the European Association for Theoretical Computer Science, 68:64-80, 1999.
Also in Current Trends in Theoretical Computer Science: Entering the 21st Century, pages 83-101, World Scientific Publishing, 2001.
[ PostScript ]

[86] J. H. Lutz, V. Mhetre, and S. Srinivasan.
Hard instances of hard problems.
In Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, pages 324-333.
Springer-Verlag, 2000.
[ PostScript ]

[87] J. H. Lutz and W. J. Schmidt.
Circuit size relative to pseudorandom oracles.
Theoretical Computer Science, 107(1):95-120, March 1993.
[ PostScript ]

[88] J. H. Lutz and D. L. Schweizer.
Feasible reductions to kolmogorov-loveland stochastic sequences.
Theoretical Computer Science, 225(1-2):185-194, 1999.
[ PostScript ]

[89] J. H. Lutz and M. Strauss.
Bias invariance of small upper spans.
In Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, pages 74-86.
Springer-Verlag, 2000.
[ PostScript ]

[90] J. H. Lutz and Y. Zhao.
The density of weakly complete problems under adaptive reductions.
SIAM Journal on Computing, 30(4):1197-1210, 2000.
[ PostScript ]

[91] E. Mayordomo.
Almost every set in exponential time is P-bi-immune.
Theoretical Computer Science, 136(2):487-506, 1994.
[ DOI | PostScript (gzipped) ]

[92] E. Mayordomo.
Contributions to the study of resource-bounded measure.
PhD thesis, Universitat Politècnica de Catalunya, 1994.
[ PostScript (gzipped) ]

[93] E. Mayordomo.
Measuring in PSPACE.
In Proceedings of the 7th International Meeting of Young Computer Scientists, volume 6 of Topics in Computer Science, pages 93-100.
Gordon and Breach, 1994.
[ PostScript (gzipped) ]

[94] W. Merkle.
The global power of additional queries to p-random oracles.
SIAM Journal on Computing, 31(2):483-495, 2001.
[ PostScript | PDF ]

[95] W. Merkle and N. Mihailovíc.
On the construction of effective random sets.
Journal of Symbolic Logic, 69(3):862-878, 2004.
[ PostScript ]

[96] W. Merkle, N. Mihailovíc, and T. A. Slaman.
Some results on effective randomness.
Theory of Computing Systems, 39(5):707-721, 2006.
[ PostScript ]

[97] P. Moser.
A generalization of Lutz's measure to probabilistic classes.
Technical Report TR02-058, Electronic Colloquium on Computational Complexity, 2002.

[98] P. Moser.
ZPP is hard unless RP is small.
Technical Report TR02-015, Electronic Colloquium on Computational Complexity, 2002.

[99] P. Moser.
RP is small in SUBEXP else ZPP equals PSPACE and NP equals EXP.
Technical Report TR03-040, Electronic Colloquium on Computational Complexity, 2003.

[100] P. Moser.
Baire categories on small complexity classes and meager-comeager laws.
Information and Computation, 206(1):15-33, 2008.
[ DOI | PDF ]

[101] P. Moser.
Resource-bounded measure on probabilistic classes.
Information Processing Letters, 106(6):241-245, 2008.
[ DOI | PDF ]

[102] A. V. Naik, K. W. Regan, and D. Sivakumar.
On quasilinear-time complexity theory.
Theoretical Computer Science, 148(2):325-349, 1995.
[ PostScript | PDF ]

[103] A. Pavan.
Comparison of reductions and completeness notions.
SIGACT News, 34(2):27-41, June 2003.
[ Abstract | PostScript | PDF ]

[104] A. Pavan and A. L. Selman.
Complete distributional problems, hard languages, and resource-bounded measure.
Theoretical Computer Science, 234(1-2):273-286, 2000.
[ Abstract | PostScript | PDF ]

[105] O. Powell.
Measure on P revisited.
Technical Report TR02-065, Electronic Colloquium on Computational Complexity, 2002.

[106] O. Powell.
PSPACE contains almost complete problems.
Technical Report TR03-028, Electronic Colloquium on Computational Complexity, 2003.

[107] O. Powell.
A note on measuring in P.
Theoretical Computer Science, 320(2-3):229-246, 2004.

[108] O. Powell.
Almost completeness in small complexity classes.
Technical Report TR05-010, Electronic Colloquium on Computational Complexity, 2005.

[109] K. W. Regan and D. Sivakumar.
Improved resource-bounded Borel-Cantelli and stochasticity theorems.
Technical Report UB-CS-TR 95-08, Computer Science Department, University at Buffalo, 1995.

[110] K. W. Regan and D. Sivakumar.
Probabilistic martingales and BPTIME classes.
In Proceedings of the 13th Annual IEEE Conference on Computational Complexity, pages 186-200.
IEEE Computer Society, 1998.
[ PostScript | PDF ]

[111] K. W. Regan, D. Sivakumar, and J. Cai.
Pseudorandom generators, measure theory, and natural proofs.
In Proceedings of the 36th Symposium on Foundations of Computer Science, pages 26-35.
IEEE Computer Society, 1995.
[ PostScript | PDF ]

[112] D. Ronneberger.
Kolmogorov Complexity and Derandomization.
PhD thesis, Rutgers University, 2004.
[ PDF ]

[113] M. Schaefer and F. Stephan.
Strong reductions and immunity for exponential time.
In Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, pages 559-570.
Springer-Verlag, 2003.

[114] R. Schuler.
Truth-table closure and turing closure of average polynomial time have different measures in EXP.
In Proceedings of the Eleventh Annual IEEE Conference on Computational Complexity, pages 190-197.
IEEE Computer Society, 1996.
[ Abstract | PostScript (gzipped) ]

[115] R. Schuler and T. Yamakami.
Sets computable in polynomial time on average.
In Proceedings of the 1st Annual International Computing and Combinatorics Conference, pages 400-409.
Springer-Verlag, 1995.

[116] D. Sivakumar.
Probabilistic Techniques in Structural Complexity Theory.
PhD thesis, SUNY at Buffalo, 1996.

[117] M. Strauss.
Measure on P: Strength of the notion.
Information and Computation, 136(1):1-23, 1997.

[118] M. Strauss.
Normal numbers and sources for BPP.
Theoretical Computer Science, 178(1-2):155-169, 1997.

[119] S. A. Terwijn.
Computability and Measure.
PhD thesis, University of Amsterdam, 1998.
[ PostScript | PDF ]

[120] S. A. Terwijn.
On the quantitative structure of Δ02.
In U. Berger, H. Osswald, and P. Schuster, editors, Reuniting the Antipodes: Constructive and Nonstandard Views of the Continuum, pages 271-283.
Kluwer Academic Press, 2000.

[121] S. A. Terwijn and L. Torenvliet.
Arithmetical measure.
Mathematical Logic Quarterly, 44(4):277-286, 1998.
[ PostScript | PDF ]

[122] D. van Melkebeek.
Randomness and Completeness in Computational Complexity.
ACM Doctoral Dissertation Award Series. Springer-Verlag, 2000.
[ Abstract | PostScript ]

[123] D. van Melkebeek.
The zero-one law holds for BPP.
Theoretical Computer Science, 244(1-2):283-288, 2000.
[ Abstract | PostScript ]

[124] Y. Wang.
The law of the iterated logarithm for p-random sequences.
In Proceedings of the Eleventh Annual IEEE Conference on Computational Complexity, pages 180-189.
IEEE Computer Society, 1996.

[125] Y. Wang.
Randomness and Complexity.
PhD thesis, Department of Mathematics, University of Heidelberg, 1996.

[126] Y. Wang.
NP-hard sets are superterse unless NP is small.
Information Processing Letters, 61(1):1-6, 1997.

[127] Y. Wang.
Genericity, randomness, and polynomial-time approximations.
SIAM Journal on Computing, 28(2):394-408, 1999.

[128] Y. Wang.
Randomness, stochasticity, and approximations.
Theory of Computing Systems, 32:517-529, 1999.

[129] Y. Wang.
A separation of two randomness concepts.
Information Processing Letters, 69(3):115-118, 1999.

[130] Y. Wang.
Resource bounded randomness and computational complexity.
Theoretical Computer Science, 237(1-2):33-55, 2000.

[131] T. Yamakami.
Average Case Computational Complexity Theory.
PhD thesis, University of Toronto, 1997.
[ Abstract | PostScript (gzipped) ]

[132] M. Zimand.
Existential Theorems in Computational Complexity Theory: Size and Robustness.
PhD thesis, University of Rochester, 1996.
[ Abstract | PostScript ]

[133] M. Zimand.
How to privatize random bits.
Technical Report 616, Department of Computer Science, University of Rochester, April 1996.
[ PostScript ]

[134] M. Zimand.
On the size of classes with weak membership properties.
Theoretical Computer Science, 209(1-2):225-235, 1998.
[ PostScript ]

[135] M. Zimand.
Relative to a random oracle, P/Poly is not measurable in EXP.
Information Processing Letters, 69(2):83-86, 1999.
[ PostScript ]

[136] M. Zimand.
Computational Complexity: A Quantitative Perspective.
Elsevier, 2004.


This file has been generated by bibtex2html 1.76