10 citations · 11 across the 7 of their papers we have counts for
8 papers · 1 filter
Axiomatizing Resource Bounds for Measure
Xiaoyang Gu, Jack H. Lutz, Satyadev Nandakumar +1
Resource-bounded measure is a generalization of classical Lebesgue measure that is useful in computational complexity. The central parameter of resource-bounded measure is the {\it…
Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses
Xiaoyang Gu, John M. Hitchcock, A. Pavan
This paper presents the following results on sets that are complete for NP. 1. If there is a problem in NP that requires exponential time at almost all lengths, then every many-one…
Curves That Must Be Retraced
Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo
We exhibit a polynomial time computable plane curve GAMMA that has finite length, does not intersect itself, and is smooth except at one endpoint, but has the following property. F…
Dimension and Relative Frequencies
Xiaoyang Gu, Jack H. Lutz
We show how to calculate the finite-state dimension (equivalently, the finite-state compressibility) of a saturated sets consisting of {\em all} infinite sequences over a f…
Points on Computable Curves
Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo
The ``analyst's traveling salesman theorem'' of geometric measure theory characterizes those subsets of Euclidean space that are contained in curves of finite length. This result,…
Dimensions of Copeland-Erdos Sequences
Xiaoyang Gu, Jack H. Lutz, Philippe Moser
The base- {\em Copeland-Erdös sequence} given by an infinite set of positive integers is the infinite sequence $\CE_k(A)$ formed by concatenating the base- representation…