Showing 2025Show all
2 papers · 1 filter
cs.CC2025
Random Permutations in Computational Complexity
John M. Hitchcock, Adewale Sekoni, Hadi Shafei
Classical results of Bennett and Gill (1981) show that with probability 1, relative to a random oracle , and with probability 1, relati…
cs.CC2025
Counting Martingales for Measure and Dimension in Complexity Classes
John M. Hitchcock, Adewale Sekoni, Hadi Shafei
This paper makes two primary contributions. First, we introduce the concept of counting martingales and use it to define counting measures, counting dimensions, and counting strong…