Selected Recent Research Contributions

  • (with Elvira Mayordomo) The first algorithm to compute absolutely normal numbers in nearly linear time. arxiv

  • (with Neil Lutz) Development of conditional algorithmic fractal dimensions. STACS 2017. arxiv

  • (with Neil Lutz) Use of the point-to-set principle to give a new, information-theoretic proof that every plane Kakeya set (set containing a unit segment in every direction) has Hausdorff dimension 2, a theorem first proved by Davies in 1971. STACS 2017. arxiv

  • (with Neil Lutz) A point-to-set principle that enables one to use the (relativized algorithmic) dimension of a single point in an arbitrary set E in Euclidean space to establish a lower bound on the (classical) Hausdorff dimension of E. STACS 2017. arxiv

  • (with Adam Case and Don Stull) Proof that reachability in the rate-independent continuous chemical reaction network model of Chen, Doty, and Soloveichik (2014) is computable in polynomial time. UCNC 2016. arxiv

  • (with Adam Case) Quantitative analysis of the mutual algorithmic dimensions between correlated random sequences. MFCS 2015. arxiv

  • (with Neil Lutz) Proof that, in every direction in Euclidean space, there is a line missing every random point. Computability, 2015. arxiv

  • (with Adam Case) Proof of the data processing inequalities, which state that applying a computable Lipschitz function to a point x in a Euclidean space cannot increase its mutual dimension with a point y in a Euclidean space. ACM Transactions on Computation Theory, 2015. arxiv

  • (with Adam Case) Development of the lower and upper mutual (algorithmic) dimensions between points in Euclidean spaces. ACM Transactions on Computation Theory, 2015. arxiv

  • (with Randy Dougherty, Dan Mauldin, and Jason Teutsch) Determination of the dimension spectra of translations of the Cantor middle thirds set by reals that are algorithmically random. Transactions of the American Mathematical Society, 2014. arxiv

  • (with Xiaoyang Gu, Elvira Mayordomo, and Philippe Moser) Determination of the dimension spectra of algorithmically random subfractals of self-similar fractals. Annals of Pure and Applied Logic, 2014. pdf

  • Use of the probabilistic method to give a very easy proof of a previously difficult theorem of Meyer (1969) and Chaitin (1976) on the paucity of strings with very low Kolmogorov complexity. Information Processing Letters, 2014. arxiv

  • (with Dave Doty, Matt Patitz, Robbie Schweller, Scott Summers, and Damien Woods) Proof that Winfree’s abstract Tile Assembly Model of nanoscale self-assembly is intrinsically universal, meaning that there is a single tile assembly system U that can be initialized to carry out the self-assembly process of any tile assembly system T. FOCS 2012. arxiv

  • (with Brad Shutters) Tight bounds on the approximate self-assembly of discrete Sierpinski triangles. Theory of Computing Systems, 2012. arxiv

  • (with Lance Fortnow and Elvira Mayordomo) Proof that, if NP does not have measure zero in EXP, then there exist disjoint pairs of NP languages that cannot be separated in subexponential time. Theory of Computing Systems, 2012. arxiv