| [1] |
M. Agrawal, D. Chakraborty, D. Das, and S. Nandakumar. Dimension, pseudorandomness and extraction of pseudorandomness. Computability, 6(3):277--305, 2017. [ DOI ] |
| [2] |
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 ] |
| [3] |
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 ] |
| [4] |
E. Allender and M. Strauss. Measure on small complexity classes with applications for BPP. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pages 807--818. IEEE Computer Society, 1994. [ DOI ] |
| [5] |
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 ] |
| [6] |
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 ] |
| [7] |
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 ] |
| [8] |
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 ] |
| [9] |
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 ] |
| [10] |
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 ] |
| [11] |
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. [ DOI ] |
| [12] |
K. Ambos-Spies, W. Merkle, J. Reimann, and F. Stephan. Hausdorff dimension in exponential time. In Proceedings of the 16th IEEE Conference on Computational Complexity, pages 210--217. IEEE Computer Society, 2001. [ DOI ] |
| [13] |
K. Ambos-Spies, W. Merkle, J. Reimann, and S. A. Terwijn. Almost complete sets. Theoretical Computer Science, 306(1--3):177--194, 2003. [ DOI ] |
| [14] |
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 ] |
| [15] |
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 ] |
| [16] |
L. Antunes, A. Matos, A. Souto, and P. Vitányi. Depth as randomness deficiency. Theory of Computing Systems, 45(4):724--739, 2009. [ DOI | arXiv ] |
| [17] |
V. Arvind and J. Köbler. On pseudorandomness and resource-bounded measure. Theoretical Computer Science, 255(1--2):205--221, 2001. [ DOI ] |
| [18] |
K. B. Athreya, J. M. Hitchcock, J. H. Lutz, and E. Mayordomo. Effective strong dimension in algorithmic information and computational complexity. SIAM Journal on Computing, 37(3):671--705, 2007. [ DOI | arXiv | Abstract | PDF ] |
| [19] |
R. Beigel, L. Fortnow, and F. Stephan. Infinitely-often autoreducible sets. SIAM Journal on Computing, 36(3):595--608, 2006. [ DOI ] |
| [20] |
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 ] |
| [21] |
R. V. Book and E. Mayordomo. On the robustness of ALMOST-R. Rairo Informatique Théorique et Applications, 30(2):123--133, 1996. [ Abstract ] |
| [22] |
J. M. Breutzmann and J. H. Lutz. Equivalence of measures of complexity classes. SIAM Journal on Computing, 29(1):302--326, 2000. [ DOI | PDF ] |
| [23] |
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 ] |
| [24] |
H. Buhrman and L. Fortnow. Two queries. Journal of Computer and System Sciences, 59(2):182--194, 1999. [ DOI ] |
| [25] |
H. Buhrman, B. Hescott, S. Homer, and L. Torenvliet. Non-uniform reductions. Theory of Computing Systems, 47(2):317--341, 2010. [ DOI ] |
| [26] |
H. Buhrman and L. Longpré. Compressibility and resource bounded measure. SIAM Journal on Computing, 31(3):876--886, 2002. [ DOI ] |
| [27] |
H. Buhrman and E. Mayordomo. An excursion to the Kolmogorov random strings. Journal of Computer and System Sciences, 54(3):393--399, 1997. [ DOI ] |
| [28] |
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. [ DOI ] |
| [29] |
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 ] |
| [30] |
H. Buhrman and D. van Melkebeek. Hard sets are hard to find. Journal of Computer and System Sciences, 59(2):327--345, 1999. [ DOI ] |
| [31] |
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 ] |
| [32] |
J. Cai and A. L. Selman. Fine separation of average time complexity classes. SIAM Journal on Computing, 28(4):1310--1325, 1999. [ DOI ] |
| [33] |
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. [ DOI ] |
| [34] |
C. Calude and M. Zimand. Effective category and measure in abstract complexity theory. Theoretical Computer Science, 154(2):307--327, 1996. [ DOI ] |
| [35] |
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 | arXiv ] |
| [36] |
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 ] |
| [37] |
Y. Chen and J. Flum. On optimal inverters. Bulletin of Symbolic Logic, 20(1):1--23, 2014. [ DOI ] |
| [38] |
Y. Chen, J. Flum, and M. Müller. Hard instances of algorithms and proof systems. ACM Trans. Comput. Theory, 6(2):7:1--7:25, 2014. [ DOI ] |
| [39] |
J. J. Dai. Some results in probability and theoretical computer science. PhD thesis, Iowa State University, 2001. [ Abstract ] |
| [40] |
J. J. Dai. A stronger Kolmogorov zero-one law for resource-bounded measure. Theoretical Computer Science, 292(3):723--732, 2003. [ DOI ] |
| [41] |
J. J. Dai. An outer-measure approach for resource-bounded measure. Theory of Computing Systems, 45(1):64--73, 2009. [ DOI ] |
| [42] |
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. [ DOI | PDF ] |
| [43] |
D. Doty and P. Moser. Finite-state dimension and lossy decompressors. Technical Report arXiv:cs/0609096 [cs.CC], Computing Research Repository, 2006. [ arXiv ] |
| [44] |
D. Doty and P. Moser. Feasible depth. In Proceedings of the 3rd Conference on Computability in Europe, pages 228--237. Springer-Verlag, 2007. [ DOI | arXiv ] |
| [45] |
T. Ebert, W. Merkle, and H. Vollmer. On the autoreducibility of random sequences. SIAM Journal on Computing, 32(6):1542--1569, 2003. [ DOI | PDF ] |
| [46] |
F. Egidy and C. Glaßer. Optimal proof systems for complex sets are hard to find. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025. To appear. [ arXiv ] |
| [47] |
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 ] |
| [48] |
S. Figueira and A. Nies. Feasible analysis, randomness, and base invariance. Theory of Computing Systems, 56(3):439--464, 2015. [ DOI ] |
| [49] |
L. Fortnow. Relativized worlds with an infinite hierarchy. Information Processing Letters, 69(6):309--313, 1999. [ DOI ] |
| [50] |
L. Fortnow, J. M. Hitchcock, A. Pavan, N. V. Vinodchandran, and F. Wang. Extracting Kolmogorov complexity with applications to dimension zero-one laws. Information and Computation, 209(4):627--636, 2011. [ DOI | Abstract | PDF ] |
| [51] |
L. Fortnow and M. Kummer. On resource-bounded instance complexity. Theoretical Computer Science, 161(1-2):123--140, 1996. [ DOI ] |
| [52] |
L. Fortnow and J. H. Lutz. Prediction and dimension. Journal of Computer and System Sciences, 70(4):570--589, 2005. [ DOI | PDF ] |
| [53] |
L. Fortnow, J. H. Lutz, and E. Mayordomo. Inseparability and strong hypotheses for disjoint np pairs. Theory Comput. Syst., 51:229--247, 2012. [ DOI | PDF ] |
| [54] |
L. Fortnow, A. Pavan, and A. L. Selman. Distributionally hard languages. Theory of Computing Systems, 34(3):245--261, 2001. [ DOI ] |
| [55] |
R. Gavaldà, M. López-Valdés, E. Mayordomo, and N. V. Vinodchandran. Resource-bounded dimension in computational learning theory. Technical report, arXiv, 2010. [ arXiv ] |
| [56] |
C. Glaßer, M. Ogihara, A. Pavan, A. L. Selman, and L. Zhang. Autoreducibility, mitoticity, and immunity. Journal of Computer and System Sciences, 73(5):735--754, 2007. [ DOI ] |
| [57] |
E. Grädel and A. Malmström. 0-1 laws for recursive structures. Archive for Mathematical Logic, 38(4):205--215, 1999. [ DOI ] |
| [58] |
J. A. Grochow. Polynomial-time axioms of choice and polynomial-time cardinality. Theory of Computing Systems, 67(4):627--669, 2023. [ DOI ] |
| [59] |
X. Gu. A note on dimensions of polynomial size circuits. Theoretical Computer Science, 359(1--3):176--187, 2006. [ DOI ] |
| [60] |
X. Gu. Fractals in complexity and geometry. PhD thesis, Iowa State University, 2009. [ Abstract ] |
| [61] |
X. Gu and J. H. Lutz. Dimension characterizations of complexity classes. Computational Complexity, 17:459--474, 2008. [ DOI | PDF ] |
| [62] |
X. Gu, J. H. Lutz, S. Nandakumar, and J. S. Royer. Axiomatizing resource bounds for measure. In B. Löwe, D. Normann, I. Soskov, and A. Soskova, editors, Models of Computation in Context, pages 102--111. Springer, 2011. [ DOI | arXiv | PDF ] |
| [63] |
R. C. Harkins. Applications of resource-bounded measure in double-exponential time. Master's thesis, University of Wyoming, 2006. [ Abstract ] |
| [64] |
R. C. Harkins. Randomness, learnability, and betting games. PhD thesis, University of Wyoming, 2012. [ Abstract ] |
| [65] |
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 ] |
| [66] |
R. C. Harkins and J. M. Hitchcock. Dimension, halfspaces, and the density of hard sets. Theory of Computing Systems, 49(3):601--614, 2011. [ DOI | Abstract | PDF ] |
| [67] |
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 ] |
| [68] |
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 ] |
| [69] |
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 ] |
| [70] |
M. Hauptmann. Scaled dimension and the Berman-Hartmanis conjecture. Technical Report 85300-CS, University of Bonn, 2008. [ Abstract | PDF ] |
| [71] |
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. [ DOI ] |
| [72] |
J. M. Hitchcock. Resource-bounded dimension, nonuniform complexity, and approximation of MAX3SAT. Master's thesis, Iowa State University, Ames, IA, USA, 2001. [ DOI | Abstract ] |
| [73] |
J. M. Hitchcock. MAX3SAT is exponentially hard to approximate if NP has positive dimension. Theoretical Computer Science, 289(1):861--869, 2002. [ DOI | Abstract | PDF ] |
| [74] |
J. M. Hitchcock. Effective Fractal Dimension: Foundations and Applications. PhD thesis, Iowa State University, 2003. [ Abstract | PostScript | PDF ] |
| [75] |
J. M. Hitchcock. Fractal dimension and logarithmic loss unpredictability. Theoretical Computer Science, 304(1--3):431--441, 2003. [ DOI | Abstract | PDF ] |
| [76] |
J. M. Hitchcock. The size of SPP. Theoretical Computer Science, 320(2--3):495--503, 2004. [ DOI | Abstract | PDF ] |
| [77] |
J. M. Hitchcock. Small spans in scaled dimension. SIAM Journal on Computing, 34(1):170--194, 2004. [ DOI | arXiv | Abstract | PDF ] |
| [78] |
J. M. Hitchcock. Hausdorff dimension and oracle constructions. Theoretical Computer Science, 355(3):382--388, 2006. [ DOI | Abstract | PDF ] |
| [79] |
J. M. Hitchcock. Online learning and resource-bounded dimension: Winnow yields new lower bounds for hard sets. SIAM Journal on Computing, 36(6):1696--1708, 2007. [ DOI | arXiv | Abstract | PDF ] |
| [80] |
J. M. Hitchcock. Limitations of efficient reducibility to the Kolmogorov random strings. Computability, 1(1):39--43, 2012. [ DOI | Abstract | PDF ] |
| [81] |
J. M. Hitchcock, M. López-Valdés, and E. Mayordomo. Scaled dimension and the Kolmogorov complexity of Turing-hard sets. Theory of Computing Systems, 43(3-4):471--497, 2008. [ DOI | Abstract | PDF ] |
| [82] |
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 ] |
| [83] |
J. M. Hitchcock, J. H. Lutz, and E. Mayordomo. Scaled dimension and nonuniform complexity. Journal of Computer and System Sciences, 69(2):97--122, 2004. [ DOI | Abstract | PDF ] |
| [84] |
J. M. Hitchcock, J. H. Lutz, and E. Mayordomo. The fractal geometry of complexity classes. SIGACT News, 36(3):24--38, September 2005. [ DOI | Abstract | PDF ] |
| [85] |
J. M. Hitchcock and E. Mayordomo. Base invariance of feasible dimension. Information Processing Letters, 113(14-16):546--551, 2013. [ DOI | Abstract | PDF ] |
| [86] |
J. M. Hitchcock and A. Pavan. Resource-bounded strong dimension versus resource-bounded category. Information Processing Letters, 95(3):377--381, 2005. [ DOI | Abstract | PDF ] |
| [87] |
J. M. Hitchcock and A. Pavan. Comparing reductions to NP-complete sets. Information and Computation, 205(5):694--706, 2007. [ DOI | Abstract | PDF ] |
| [88] |
J. M. Hitchcock and A. Pavan. Hardness hypotheses, derandomization, and circuit complexity. Computational Complexity, 17(1):119--146, 2008. [ DOI | Abstract | PDF ] |
| [89] |
J. M. Hitchcock, A. Pavan, and N. V. Vinodchandran. Partial bi-immunity, scaled dimension, and NP-completeness. Theory of Computing Systems, 42(2):131--142, 2008. [ DOI | Abstract | PDF ] |
| [90] |
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 ] |
| [91] |
J. M. Hitchcock, A. Sekoni, and H. Shafei. Polynomial-time random oracles and separating complexity classes. ACM Transactions on Computation Theory, 13(1), 1 2021. [ DOI | Abstract | PDF ] |
| [92] |
J. M. Hitchcock and H. Shafei. Autoreducibility of NP-complete sets under strong hypotheses. Computational Complexity, 27:63--97, 2018. [ DOI | Abstract | PDF ] |
| [93] |
J. M. Hitchcock and H. Shafei. Nonuniform reductions and NP-completeness. Theory of Computing Systems, 66(4):743--757, 2022. [ DOI | Abstract | PDF ] |
| [94] |
J. M. Hitchcock and N. V. Vinodchandran. Dimension, entropy rates, and compression. Journal of Computer and System Sciences, 72(4):760--782, 2006. [ DOI | Abstract | PDF ] |
| [95] |
X. Huang and D. M. Stull. Polynomial Space Randomness in Analysis. In P. Faliszewski, A. Muscholl, and R. Niedermeier, editors, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), volume 58 of Leibniz International Proceedings in Informatics (LIPIcs), pages 86:1--86:13, Dagstuhl, Germany, 2016. Schloss Dagstuhl -- Leibniz-Zentrum für Informatik. [ DOI | arXiv ] |
| [96] |
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 ] |
| [97] |
G. Istrate. Resource-bounded measure and autoreducibility. Technical Report 644, Department of Computer Science, University of Rochester, December 1996. |
| [98] |
D. W. Juedes. The Complexity and Distribution of Computationally Useful Problems. PhD thesis, Iowa State University, 1994. [ Abstract ] |
| [99] |
D. W. Juedes. Weakly complete problems are not rare. Computational Complexity, 5(3/4):267--283, 1995. [ DOI ] |
| [100] |
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 ] |
| [101] |
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 ] |
| [102] |
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 ] |
| [103] |
D. W. Juedes and J. H. Lutz. Weak completeness in E and E2. Theoretical Computer Science, 143(1):149--158, 1995. [ DOI | PDF ] |
| [104] |
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 ] |
| [105] |
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 ] |
| [106] |
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 ] |
| [107] |
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 ] |
| [108] |
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 ] |
| [109] |
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 ] |
| [110] |
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 ] |
| [111] |
J. I. Lathrop and J. H. Lutz. Recursive computational depth. Information and Computation, 153(2):139--172, 1999. [ DOI | PDF ] |
| [112] |
W. Lindner. On the polynomial time bounded measure of one-truth-table degrees and p-selectivity. PhD thesis, Technische Universität Berlin, 1993. |
| [113] |
W. Lindner and R. Schuler. A small span theorem within P. Technical Report UIB-1997-02, Universität Ulm, 1997. [ PDF ] |
| [114] |
W. Lindner, R. Schuler, and O. Watanabe. Resource-bounded measure and learnability. Theory of Computing Systems, 33(2):151--170, 2000. [ DOI ] |
| [115] |
M. López-Valdés and E. Mayordomo. Dimension is compression. Theory of Computing Systems, 52(1):95--112, 2013. [ DOI ] |
| [116] |
A. K. Lorentz and J. H. Lutz. Genericity and randomness over feasible probability measures. Theoretical Computer Science, 207(1):245--259, 1998. [ DOI | PDF ] |
| [117] |
J. H. Lutz. One-way functions and balanced NP. Manuscript. [ PDF ] |
| [118] |
J. H. Lutz. Resource-Bounded Category and Measure in Exponential Complexity Classes. PhD thesis, California Institute of Technology, 1987. [ DOI | PDF ] |
| [119] |
J. H. Lutz. Category and measure in complexity classes. SIAM Journal on Computing, 19(6):1100--1131, 1990. [ DOI ] |
| [120] |
J. H. Lutz. Pseudorandom sources for BPP. Journal of Computer and System Sciences, 41(3):307--320, 1990. [ DOI ] |
| [121] |
J. H. Lutz. An upward measure separation theorem. Theoretical Computer Science, 81(1):127--135, 1991. [ DOI | PDF ] |
| [122] |
J. H. Lutz. Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences, 44(2):220--258, 1992. [ DOI | PDF ] |
| [123] |
J. H. Lutz. On independent random oracles. Theoretical Computer Science, 92:301--307, 1992. [ DOI | PDF ] |
| [124] |
J. H. Lutz. A pseudorandom oracle characterization of BPP. SIAM Journal on Computing, 22(5):1075--1086, 1993. [ DOI ] |
| [125] |
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. [ DOI | PDF ] |
| [126] |
J. H. Lutz. Weakly hard problems. SIAM Journal on Computing, 24(6):1170--1189, 1995. [ DOI | PDF ] |
| [127] |
J. H. Lutz. Observations on measure and lowness for ΔP2. Theory of Computing Systems, 30(4):429--442, 1997. [ DOI | PDF ] |
| [128] |
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 ] |
| [129] |
J. H. Lutz. Resource-bounded measure. In Proceedings of the 13th IEEE Conference on Computational Complexity, pages 236--248. IEEE Computer Society, 1998. [ DOI ] |
| [130] |
J. H. Lutz. Dimension in complexity classes. SIAM Journal on Computing, 32(5):1236--1259, 2003. [ DOI | arXiv | PDF ] |
| [131] |
J. H. Lutz. Computability versus exact computability of martingales. Information Processing Letters, 92(5):235--237, 2004. [ DOI | PDF ] |
| [132] |
J. H. Lutz. Effective fractal dimensions. Mathematical Logic Quarterly, 51(1):62--72, 2005. [ DOI | PDF ] |
| [133] |
J. H. Lutz and N. Lutz. Lines missing every random point. Computability, 4(2):85--102, 2015. [ DOI | arXiv ] |
| [134] |
J. H. Lutz, N. Lutz, and E. Mayordomo. Dimension and the structure of complexity classes. Theory of Computing Systems, 67:473--490, 2023. [ DOI | arXiv ] |
| [135] |
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 ] |
| [136] |
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 ] |
| [137] |
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 appears [138]. [ PDF ] |
| [138] |
J. H. Lutz and E. Mayordomo. Twelve problems in resource-bounded measure. In G. Păun, G. Rozenberg, and A. Salomaa, editors, Current Trends in Theoretical Computer Science: Entering the 21st Century, pages 83--101. World Scientific Publishing, 2001. [ DOI ] |
| [139] |
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 ] |
| [140] |
J. H. Lutz and W. J. Schmidt. Circuit size relative to pseudorandom oracles. Theoretical Computer Science, 107(1):95--120, 3 1993. [ DOI | PDF ] |
| [141] |
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 ] |
| [142] |
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 ] |
| [143] |
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 ] |
| [144] |
N. Lutz. Some open problems in algorithmic fractal geometry. ACM SIGACT News, 48(4):35--41, 2017. [ DOI ] |
| [145] |
M. López-Valdés. Aplicaciones de la dimensión efectiva a la complejidad computacional y a los algoritmos de comprensión de datos. PhD thesis, Universidad de Zaragoza, 2011. [ Abstract ] |
| [146] |
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 ] |
| [147] |
E. Mayordomo. Almost every set in exponential time is P-bi-immune. Theoretical Computer Science, 136(2):487--506, 1994. [ DOI | DOI ] |
| [148] |
E. Mayordomo. Contributions to the study of resource-bounded measure. PhD thesis, Universitat Politècnica de Catalunya, 1994. [ Abstract | PDF ] |
| [149] |
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. |
| [150] |
E. Mayordomo. Effective Hausdorff dimension. In B. Löwe, B. Piwinger, and T. Räsch, editors, Classical and New Paradigms of Computation and their Complexity Hierarchies, volume 23 of Trends in Logic, pages 171--186. Kluwer Academic Press, 2004. [ DOI | PostScript (gzipped) ] |
| [151] |
E. Mayordomo. Two open problems on effective dimension. In Proceedings of Second Conference on Computability in Europe, pages 353--359. Springer-Verlag, 2006. [ DOI | PDF ] |
| [152] |
W. Merkle. The global power of additional queries to p-random oracles. SIAM Journal on Computing, 31(2):483--495, 2001. [ DOI ] |
| [153] |
W. Merkle and N. Mihailovíc. On the construction of effective random sets. Journal of Symbolic Logic, 69(3):862--878, 2004. [ DOI ] |
| [154] |
W. Merkle, N. Mihailovíc, and T. A. Slaman. Some results on effective randomness. Theory of Computing Systems, 39(5):707--721, 2006. [ DOI ] |
| [155] |
V. S. Mhetre. Instance complexities of hard and weakly hard problems. Master's thesis, Iowa State University, Ames, IA, USA, 1999. [ Abstract ] |
| [156] |
P. Moser. A generalization of Lutz's measure to probabilistic classes. Technical Report TR02-058, Electronic Colloquium on Computational Complexity, 2002. [ Abstract ] |
| [157] |
P. Moser. ZPP is hard unless RP is small. Technical Report TR02-015, Electronic Colloquium on Computational Complexity, 2002. [ Abstract ] |
| [158] |
P. Moser. BPP has effective dimension at most 1/2 unless BPP = EXP. Technical Report TR03-029, Electronic Colloquium on Computational Complexity, 2003. [ Abstract | PDF ] |
| [159] |
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. [ Abstract ] |
| [160] |
P. Moser. Derandomization and Quantitative Complexity. PhD thesis, Université de Genève, 2004. |
| [161] |
P. Moser. Baire categories on small complexity classes and meager-comeager laws. Information and Computation, 206(1):15--33, 2008. [ DOI ] |
| [162] |
P. Moser. Generic density and small span theorem. Information and Computation, 206(1):1--14, 2008. [ DOI ] |
| [163] |
P. Moser. Martingale families and dimension in P. Theoretical Computer Science, 400(1--3):46--61, 2008. [ DOI ] |
| [164] |
P. Moser. Resource-bounded measure on probabilistic classes. Information Processing Letters, 106(6):241--245, 2008. [ DOI ] |
| [165] |
P. Moser. A zero-one SUBEXP-dimension law for BPP. Information Processing Letters, 111(9):429--432, 2011. [ DOI ] |
| [166] |
P. Moser. On the polynomial depth of various sets of random strings. Theoretical Computer Science, 477:96--108, 2013. [ DOI | arXiv ] |
| [167] |
P. Moser. Polylog depth, highness and lowness for E. Information and Computation, 271:104483, 2020. [ DOI | arXiv ] |
| [168] |
C. Mukhopadhyay. Resource bounded measure and P versus NP problem-a critical study. Master's thesis, Indian Statistical Institute, 2000. [ Abstract ] |
| [169] |
A. V. Naik, K. W. Regan, and D. Sivakumar. On quasilinear-time complexity theory. Theoretical Computer Science, 148(2):325--349, 1995. [ DOI ] |
| [170] |
S. Nandakumar and S. Pulari. Ergodic theorems and converses for PSPACE functions. Theory of Computing Systems, 67(3):491--520, 2023. [ DOI | arXiv ] |
| [171] |
S. Nandakumar, S. Pulari, A. S, and S. Sarma. One-way functions and polynomial time dimension. Technical report, arXiv, 2025. [ DOI | arXiv ] |
| [172] |
A. Nies. Differentiability of polynomial time computable functions. In E. W. Mayr and N. Portier, editors, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), volume 25 of Leibniz International Proceedings in Informatics (LIPIcs), pages 602--613, Dagstuhl, Germany, 2014. Schloss Dagstuhl -- Leibniz-Zentrum für Informatik. [ DOI ] |
| [173] |
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 ] |
| [174] |
A. Pavan. Average-case complexity theory and polynomial-time reductions. PhD thesis, State University of New York at Buffalo, 2001. [ Abstract ] |
| [175] |
A. Pavan. Comparison of reductions and completeness notions. SIGACT News, 34(2):27--41, June 2003. [ DOI ] |
| [176] |
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 ] |
| [177] |
O. Powell. Measure on P revisited. Technical Report TR02-065, Electronic Colloquium on Computational Complexity, 2002. [ Abstract ] |
| [178] |
O. Powell. PSPACE contains almost complete problems. Technical Report TR03-028, Electronic Colloquium on Computational Complexity, 2003. [ Abstract ] |
| [179] |
O. Powell. A note on measuring in P. Theoretical Computer Science, 320(2--3):229--246, 2004. [ DOI ] |
| [180] |
O. Powell. Almost completeness in small complexity classes. Technical Report TR05-010, Electronic Colloquium on Computational Complexity, 2005. [ Abstract ] |
| [181] |
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. |
| [182] |
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. [ DOI ] |
| [183] |
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. [ DOI ] |
| [184] |
J. Reimann. Computability and fractal dimension. PhD thesis, Ruprecht-Karls Universität Heidelberg, 2004. [ DOI ] |
| [185] |
D. Ronneberger. Kolmogorov Complexity and Derandomization. PhD thesis, Rutgers University, 2004. |
| [186] |
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 ] |
| [187] |
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. [ DOI ] |
| [188] |
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 ] |
| [189] |
A. Sekoni. Polynomial-space randomness and DNF complexity. Master's thesis, University of Wyoming, 2014. [ Abstract ] |
| [190] |
A. Sekoni. Polynomial-time Random Oracles, Nondeterministic Sublinear Time, and Boolean Function Complexity. PhD thesis, University of Wyoming, 2018. [ Abstract ] |
| [191] |
H. Shafei. Autoreducibility, Nonuniform Completeness, and Random Oracles. PhD thesis, University of Wyoming, 2017. [ Abstract ] |
| [192] |
D. Sivakumar. Probabilistic Techniques in Structural Complexity Theory. PhD thesis, SUNY at Buffalo, 1996. [ Abstract ] |
| [193] |
S. Srinivasan. Average-case complexity and instance complexity. Master's thesis, Iowa State University, Ames, IA, USA, 2000. [ Abstract ] |
| [194] |
M. Strauss. Measure on P: Strength of the notion. Information and Computation, 136(1):1--23, 1997. [ DOI ] |
| [195] |
M. Strauss. Normal numbers and sources for BPP. Theoretical Computer Science, 178(1--2):155--169, 1997. [ DOI ] |
| [196] |
M. J. Strauss. Measure in feasible complexity classes. PhD thesis, Rutgers, The State University of New Jersey, 1995. [ Abstract ] |
| [197] |
D. M. Stull. Algorithmic Randomness and Analysis. PhD thesis, Iowa State University, 2017. [ Abstract ] |
| [198] |
D. M. Stull. Resource bounded randomness and its applications. In J. N. Y. Franklin and C. P. Porter, editors, Algorithmic Randomness: Progress and Prospects, volume 50 of Lecture Notes in Logic, page 301–348. Cambridge University Press, Cambridge, 2020. [ DOI ] |
| [199] |
C. Sureson. Subcomputable Hausdorff function dimension. Theor. Comput. Sci., 891:59--83, 2021. [ DOI ] |
| [200] |
S. A. Terwijn. Computability and Measure. PhD thesis, University of Amsterdam, 1998. [ Abstract ] |
| [201] |
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 ] |
| [202] |
S. A. Terwijn and L. Torenvliet. Arithmetical measure. Mathematical Logic Quarterly, 44(4):277--286, 1998. [ DOI ] |
| [203] |
D. van Melkebeek. Randomness and Completeness in Computational Complexity, volume 1950 of Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, 2000. [ DOI | Abstract ] |
| [204] |
D. van Melkebeek. The zero-one law holds for BPP. Theoretical Computer Science, 244(1--2):283--288, 2000. [ DOI ] |
| [205] |
F. Wang. Kolmogorov extraction and resource-bounded zero-one laws. Master's thesis, Iowa State University, 2006. [ Abstract ] |
| [206] |
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. [ DOI ] |
| [207] |
Y. Wang. Randomness and Complexity. PhD thesis, Department of Mathematics, University of Heidelberg, 1996. [ Abstract | PDF ] |
| [208] |
Y. Wang. NP-hard sets are superterse unless NP is small. Information Processing Letters, 61(1):1--6, 1997. [ DOI ] |
| [209] |
Y. Wang. Genericity, randomness, and polynomial-time approximations. SIAM Journal on Computing, 28(2):394--408, 1999. [ DOI ] |
| [210] |
Y. Wang. Randomness, stochasticity, and approximations. Theory of Computing Systems, 32:517--529, 1999. [ DOI ] |
| [211] |
Y. Wang. A separation of two randomness concepts. Information Processing Letters, 69(3):115--118, 1999. [ DOI ] |
| [212] |
Y. Wang. Resource bounded randomness and computational complexity. Theoretical Computer Science, 237(1--2):33--55, 2000. [ DOI ] |
| [213] |
T. Yamakami. Average Case Computational Complexity Theory. PhD thesis, University of Toronto, 1997. [ Abstract | PDF ] |
| [214] |
M. Zimand. Existential Theorems in Computational Complexity Theory: Size and Robustness. PhD thesis, University of Rochester, 1996. [ Abstract ] |
| [215] |
M. Zimand. How to privatize random bits. Technical Report 616, Department of Computer Science, University of Rochester, April 1996. |
| [216] |
M. Zimand. On the size of classes with weak membership properties. Theoretical Computer Science, 209(1--2):225--235, 1998. [ DOI ] |
| [217] |
M. Zimand. Relative to a random oracle, P/Poly is not measurable in EXP. Information Processing Letters, 69(2):83--86, 1999. [ DOI ] |
| [218] |
M. Zimand. Computational Complexity: A Quantitative Perspective. Elsevier, 2004. [ Abstract ] |
This file was generated by bibtex2html 1.99.
UWYO Essay service topgradeessay.com