| [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. [ DOI ] |
| [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. [ DOI ] |
| [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. |
| [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. [ DOI ] |
| [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. [ DOI ] |
| [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. [ DOI ] |
| [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. [ DOI ] |
| [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. [ DOI ] |
| [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. [ DOI ] |
| [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. |
| [11] |
K. Ambos-Spies, W. Merkle, J. Reimann, and S. A. Terwijn. Almost complete sets. Theoretical Computer Science, 306(1--3):177--194, 2003. [ DOI ] |
| [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. [ DOI ] |
| [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. [ DOI ] |
| [14] |
V. Arvind and J. Köbler. On pseudorandomness and resource-bounded measure. Theoretical Computer Science, 255(1--2):205--221, 2001. [ DOI ] |
| [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. [ DOI ] |
| [16] |
R. V. Book and E. Mayordomo. On the robustness of ALMOST-R. Rairo Informatique Théorique et Applications, 30(2):123--133, 1996. |
| [17] |
J. M. Breutzmann and J. H. Lutz. Equivalence of measures of complexity classes. SIAM Journal on Computing, 29(1):302--326, 2000. [ DOI | PDF ] |
| [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 ] |
| [19] |
H. Buhrman and L. Fortnow. Two queries. Journal of Computer and System Sciences, 59(2):182--194, 1999. [ DOI ] |
| [20] |
H. Buhrman, B. Hescott, S. Homer, and L. Torenvliet. Non-uniform reductions. Theory of Computing Systems, 47(2):317--341, 2010. [ DOI ] |
| [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. [ DOI ] |
| [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. [ DOI ] |
| [25] |
H. Buhrman and D. van Melkebeek. Hard sets are hard to find. Journal of Computer and System Sciences, 59(2):327--345, 1999. [ DOI ] |
| [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. [ DOI ] |
| [27] |
J. Cai and A. L. Selman. Fine separation of average time complexity classes. SIAM Journal on Computing, 28(4):1310--1325, 1999. [ DOI ] |
| [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. [ DOI ] |
| [30] |
D. Chakraborty, S. Nandakumar, and H. Shukla. On resource-bounded versions of the van lambalgen theorem. In International Conference on Theory and Applications of Models of Computation, pages 129--143. Springer, 2017. [ DOI ] |
| [31] |
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. [ DOI ] |
| [32] |
J. J. Dai. A stronger Kolmogorov zero-one law for resource-bounded measure. Theoretical Computer Science, 292(3):723--732, 2003. [ DOI ] |
| [33] |
J. J. Dai. An outer-measure approach for resource-bounded measure. Theory of Computing Systems, 45(1):64--73, 2009. [ DOI ] |
| [34] |
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. [ PDF ] |
| [35] |
D. Doty and P. Moser. Feasible depth. In Proceedings of the 3rd Conference on Computability in Europe. Springer-Verlag, 2007. To appear. [ DOI | DOI | Abstract | PostScript | PDF ] |
| [36] |
T. Ebert, W. Merkle, and H. Vollmer. On the autoreducibility of random sequences. SIAM Journal on Computing, 32(6):1542--1569, 2003. [ DOI | PostScript | PDF ] |
| [37] |
S. A. Fenner, J. H. Lutz, E. Mayordomo, and P. Reardon. Weakly useful sequences. Information and Computation, 197(1--2):41--54, 2005. [ DOI | PDF ] |
| [38] |
L. Fortnow. Relativized worlds with an infinite hierarchy. Information Processing Letters, 69(6):309--313, 1999. [ DOI ] |
| [39] |
L. Fortnow and M. Kummer. On resource-bounded instance complexity. Theoretical Computer Science, 161(1-2):123--140, 1996. [ DOI ] |
| [40] |
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. [ DOI | Abstract ] |
| [41] |
L. Fortnow, A. Pavan, and A. L. Selman. Distributionally hard languages. Theory of Computing Systems, 34(3):245--261, 2001. [ DOI ] |
| [42] |
E. Grädel and A. Malmström. 0-1 laws for recursive structures. Archive for Mathematical Logic, 38(4):205--215, 1999. [ DOI ] |
| [43] |
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 | PDF ] |
| [44] |
R. C. Harkins and J. M. Hitchcock. Exact learning algorithms, betting games, and circuit lower bounds. ACM Transactions on Computation Theory, 5(4):article 18, 2013. [ DOI | Abstract | PDF ] |
| [45] |
R. C. Harkins, J. M. Hitchcock, and A. Pavan. Stronger reductions and isomorphism of complete sets. Computability, 3(2):91--104, 2014. [ DOI | Abstract | PDF ] |
| [46] |
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. [ DOI ] |
| [47] |
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. |
| [48] |
J. M. Hitchcock. The size of SPP. Theoretical Computer Science, 320(2--3):495--503, 2004. [ DOI | Abstract | PDF ] |
| [49] |
J. M. Hitchcock and J. H. Lutz. Why computational complexity requires stricter martingales. Theory of Computing Systems, 39(2):277--296, 2006. [ DOI | Abstract | PDF ] |
| [50] |
J. M. Hitchcock and A. Pavan. Comparing reductions to NP-complete sets. Information and Computation, 205(5):694--706, 2007. [ DOI | Abstract | PDF ] |
| [51] |
J. M. Hitchcock and A. Sekoni. Nondeterministic sublinear time has measure 0 in P. Theory of Computing Systems, 63(3):386--393, 2019. [ DOI | Abstract | PDF ] |
| [52] |
J. M. Hitchcock, A. Sekoni, and H. Shafei. Polynomial-time random oracles and separating complexity classes. ACM Trans. Comput. Theory, 13(1), 1 2021. [ DOI | Abstract | PDF ] |
| [53] |
J. M. Hitchcock and H. Shafei. Autoreducibility of NP-complete sets under strong hypotheses. computational complexity, 27:63--97, 2018. [ DOI | Abstract | PDF ] |
| [54] |
J. M. Hitchcock and H. Shafei. Nonuniform reductions and NP-completeness. Theory of Computing Systems, 66(4):743--757, 2022. [ DOI | Abstract | PDF ] |
| [55] |
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 ] |
| [56] |
G. Istrate. Resource-bounded measure and autoreducibility. Technical Report 644, Department of Computer Science, University of Rochester, December 1996. |
| [57] |
D. W. Juedes. The Complexity and Distribution of Computationally Useful Problems. PhD thesis, Iowa State University, 1994. |
| [58] |
D. W. Juedes. Weakly complete problems are not rare. Computational Complexity, 5(3/4):267--283, 1995. [ DOI ] |
| [59] |
D. W. Juedes, J. I. Lathrop, and J. H. Lutz. Computational depth and reducibility. Theoretical Computer Science, 132(1--2):37--70, 1994. [ DOI | PDF ] |
| [60] |
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. [ DOI | PDF ] |
| [61] |
D. W. Juedes and J. H. Lutz. The complexity and distribution of hard problems. SIAM Journal on Computing, 24(2):279--295, 1995. [ DOI | PDF ] |
| [62] |
D. W. Juedes and J. H. Lutz. Weak completeness in E and E2. Theoretical Computer Science, 143(1):149--158, 1995. [ PDF ] |
| [63] |
D. W. Juedes and J. H. Lutz. Completeness and weak completeness under polynomial-size circuits. Information and Computation, 125(1):13--31, 1996. [ DOI | PDF ] |
| [64] |
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. [ DOI ] |
| [65] |
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. [ DOI ] |
| [66] |
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. [ DOI ] |
| [67] |
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. [ DOI ] |
| [68] |
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. [ PDF ] |
| [69] |
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. [ DOI ] |
| [70] |
J. I. Lathrop and J. H. Lutz. Recursive computational depth. Information and Computation, 153(2):139--172, 1999. [ DOI | PDF ] |
| [71] |
W. Lindner. On the polynomial time bounded measure of one-truth-table degrees and p-selectivity. Diplomarbeit, Technische Universität Berlin, 1993. |
| [72] |
W. Lindner and R. Schuler. A small span theorem within P. Technical Report UIB-1997-02, Universität Ulm, 1997. [ PDF ] |
| [73] |
W. Lindner, R. Schuler, and O. Watanabe. Resource-bounded measure and learnability. Theory of Computing Systems, 33(2):151--170, 2000. [ DOI ] |
| [74] |
A. K. Lorentz and J. H. Lutz. Genericity and randomness over feasible probability measures. Theoretical Computer Science, 207(1):245--259, 1998. [ DOI | PDF ] |
| [75] |
J. H. Lutz. One-way functions and balanced NP. Theoretical Computer Science. To appear. [ PDF ] |
| [76] |
J. H. Lutz. Resource-Bounded Category and Measure in Exponential Complexity Classes. PhD thesis, California Institute of Technology, 1987. [ Abstract ] |
| [77] |
J. H. Lutz. Category and measure in complexity classes. SIAM Journal on Computing, 19(6):1100--1131, 1990. [ DOI ] |
| [78] |
J. H. Lutz. Pseudorandom sources for BPP. Journal of Computer and System Sciences, 41(3):307--320, 1990. [ DOI ] |
| [79] |
J. H. Lutz. An upward measure separation theorem. Theoretical Computer Science, 81(1):127--135, 1991. [ DOI | PDF ] |
| [80] |
J. H. Lutz. Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences, 44(2):220--258, 1992. [ DOI | PDF ] |
| [81] |
J. H. Lutz. On independent random oracles. Theoretical Computer Science, 92:301--307, 1992. [ DOI | PDF ] |
| [82] |
J. H. Lutz. A pseudorandom oracle characterization of BPP. SIAM Journal on Computing, 22(5):1075--1086, 1993. [ DOI ] |
| [83] |
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. [ PDF ] |
| [84] |
J. H. Lutz. Weakly hard problems. SIAM Journal on Computing, 24(6):1170--1189, 1995. [ DOI | PDF ] |
| [85] |
J. H. Lutz. Observations on measure and lowness for ΔP2. Theory of Computing Systems, 30(4):429--442, 1997. [ DOI | PDF ] |
| [86] |
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. [ DOI | PDF ] |
| [87] |
J. H. Lutz. Resource-bounded measure. In Proceedings of the 13th IEEE Conference on Computational Complexity, pages 236--248. IEEE Computer Society, 1998. |
| [88] |
J. H. Lutz. Computability versus exact computability of martingales. Information Processing Letters, 92(5):235--237, 2004. [ DOI | PDF ] |
| [89] |
J. H. Lutz and E. Mayordomo. Measure, stochasticity, and the density of hard languages. SIAM Journal on Computing, 23(4):762--779, 1994. [ DOI | PDF ] |
| [90] |
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. [ DOI | PDF ] |
| [91] |
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. [ PDF ] |
| [92] |
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. [ DOI | PDF ] |
| [93] |
J. H. Lutz and W. J. Schmidt. Circuit size relative to pseudorandom oracles. Theoretical Computer Science, 107(1):95--120, 3 1993. [ DOI | PDF ] |
| [94] |
J. H. Lutz and D. L. Schweizer. Feasible reductions to kolmogorov-loveland stochastic sequences. Theoretical Computer Science, 225(1--2):185--194, 1999. [ DOI | PDF ] |
| [95] |
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. [ DOI | PDF ] |
| [96] |
J. H. Lutz and Y. Zhao. The density of weakly complete problems under adaptive reductions. SIAM Journal on Computing, 30(4):1197--1210, 2000. [ DOI | PDF ] |
| [97] |
D. Mandal, A. Pavan, and R. Venugopalan. Separating Cook Completeness from Karp-Levin Completeness Under a Worst-Case Hardness Hypothesis. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014), volume 29 of Leibniz International Proceedings in Informatics (LIPIcs), pages 445--456, 2014. [ DOI | Abstract ] |
| [98] |
E. Mayordomo. Almost every set in exponential time is P-bi-immune. Theoretical Computer Science, 136(2):487--506, 1994. [ DOI | DOI ] |
| [99] |
E. Mayordomo. Contributions to the study of resource-bounded measure. PhD thesis, Universitat Politècnica de Catalunya, 1994. |
| [100] |
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. |
| [101] |
W. Merkle. The global power of additional queries to p-random oracles. SIAM Journal on Computing, 31(2):483--495, 2001. |
| [102] |
W. Merkle and N. Mihailovíc. On the construction of effective random sets. Journal of Symbolic Logic, 69(3):862--878, 2004. [ DOI ] |
| [103] |
W. Merkle, N. Mihailovíc, and T. A. Slaman. Some results on effective randomness. Theory of Computing Systems, 39(5):707--721, 2006. |
| [104] |
P. Moser. A generalization of Lutz's measure to probabilistic classes. Technical Report TR02-058, Electronic Colloquium on Computational Complexity, 2002. |
| [105] |
P. Moser. ZPP is hard unless RP is small. Technical Report TR02-015, Electronic Colloquium on Computational Complexity, 2002. |
| [106] |
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. |
| [107] |
P. Moser. Baire categories on small complexity classes and meager-comeager laws. Information and Computation, 206(1):15--33, 2008. [ DOI | DOI ] |
| [108] |
P. Moser. Resource-bounded measure on probabilistic classes. Information Processing Letters, 106(6):241--245, 2008. [ DOI ] |
| [109] |
A. V. Naik, K. W. Regan, and D. Sivakumar. On quasilinear-time complexity theory. Theoretical Computer Science, 148(2):325--349, 1995. [ DOI ] |
| [110] |
S. Nandakumar and S. Pulari. Ergodic theorems and converses for PSPACE functions. Theory of Computing Systems, 67(3):491--520, 2023. [ DOI ] |
| [111] |
A. Nies and F. Stephan. Closure of Resource-Bounded Randomness Notions Under Polynomial-Time Permutations. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), volume 96 of Leibniz International Proceedings in Informatics (LIPIcs), pages 51:1--51:10, 2018. [ DOI ] |
| [112] |
A. Pavan. Comparison of reductions and completeness notions. SIGACT News, 34(2):27--41, June 2003. |
| [113] |
A. Pavan and A. L. Selman. Complete distributional problems, hard languages, and resource-bounded measure. Theoretical Computer Science, 234(1--2):273--286, 2000. [ DOI ] |
| [114] |
O. Powell. Measure on P revisited. Technical Report TR02-065, Electronic Colloquium on Computational Complexity, 2002. |
| [115] |
O. Powell. PSPACE contains almost complete problems. Technical Report TR03-028, Electronic Colloquium on Computational Complexity, 2003. |
| [116] |
O. Powell. A note on measuring in P. Theoretical Computer Science, 320(2--3):229--246, 2004. [ DOI ] |
| [117] |
O. Powell. Almost completeness in small complexity classes. Technical Report TR05-010, Electronic Colloquium on Computational Complexity, 2005. |
| [118] |
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. |
| [119] |
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. |
| [120] |
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. |
| [121] |
D. Ronneberger. Kolmogorov Complexity and Derandomization. PhD thesis, Rutgers University, 2004. |
| [122] |
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. [ DOI ] |
| [123] |
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. |
| [124] |
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. [ DOI ] |
| [125] |
D. Sivakumar. Probabilistic Techniques in Structural Complexity Theory. PhD thesis, SUNY at Buffalo, 1996. |
| [126] |
M. Strauss. Measure on P: Strength of the notion. Information and Computation, 136(1):1--23, 1997. [ DOI ] |
| [127] |
M. Strauss. Normal numbers and sources for BPP. Theoretical Computer Science, 178(1--2):155--169, 1997. [ DOI ] |
| [128] |
D. M. Stull. Resource bounded randomness and its applications. In Algorithmic Randomness: Progress and Prospects, volume 50 of Lecture Notes in Logic, pages 301--. Cambridge University Press, 2020. [ DOI ] |
| [129] |
S. A. Terwijn. Computability and Measure. PhD thesis, University of Amsterdam, 1998. |
| [130] |
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. [ DOI ] |
| [131] |
S. A. Terwijn and L. Torenvliet. Arithmetical measure. Mathematical Logic Quarterly, 44(4):277--286, 1998. [ DOI ] |
| [132] |
D. van Melkebeek. Randomness and Completeness in Computational Complexity. ACM Doctoral Dissertation Award Series. Springer-Verlag, 2000. [ DOI ] |
| [133] |
D. van Melkebeek. The zero-one law holds for BPP. Theoretical Computer Science, 244(1--2):283--288, 2000. [ DOI ] |
| [134] |
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. |
| [135] |
Y. Wang. Randomness and Complexity. PhD thesis, Department of Mathematics, University of Heidelberg, 1996. |
| [136] |
Y. Wang. NP-hard sets are superterse unless NP is small. Information Processing Letters, 61(1):1--6, 1997. [ DOI ] |
| [137] |
Y. Wang. Genericity, randomness, and polynomial-time approximations. SIAM Journal on Computing, 28(2):394--408, 1999. |
| [138] |
Y. Wang. Randomness, stochasticity, and approximations. Theory of Computing Systems, 32:517--529, 1999. [ DOI ] |
| [139] |
Y. Wang. A separation of two randomness concepts. Information Processing Letters, 69(3):115--118, 1999. [ DOI ] |
| [140] |
Y. Wang. Resource bounded randomness and computational complexity. Theoretical Computer Science, 237(1--2):33--55, 2000. [ DOI ] |
| [141] |
T. Yamakami. Average Case Computational Complexity Theory. PhD thesis, University of Toronto, 1997. [ Abstract | PDF ] |
| [142] |
M. Zimand. Existential Theorems in Computational Complexity Theory: Size and Robustness. PhD thesis, University of Rochester, 1996. [ Abstract ] |
| [143] |
M. Zimand. How to privatize random bits. Technical Report 616, Department of Computer Science, University of Rochester, April 1996. |
| [144] |
M. Zimand. On the size of classes with weak membership properties. Theoretical Computer Science, 209(1--2):225--235, 1998. [ DOI ] |
| [145] |
M. Zimand. Relative to a random oracle, P/Poly is not measurable in EXP. Information Processing Letters, 69(2):83--86, 1999. [ DOI ] |
| [146] |
M. Zimand. Computational Complexity: A Quantitative Perspective. Elsevier, 2004. |
This file was generated by bibtex2html 1.99.
UWYO Essay service topgradeessay.com