skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


This content will become publicly available on May 7, 2026

Title: Algorithmically Optimal Outer Measures
We investigate the relationship between algorithmic fractal dimensions and the classical local fractal dimensions of outer measures in Euclidean spaces. We introduce global and local optimality conditions for lower semicomputable outer measures. We prove that globally optimal outer measures exist. Our main theorem states that the classical local fractal dimensions of any locally optimal outer measure coincide exactly with the algorithmic fractal dimensions. Our proof uses an especially convenient locally optimal outer measureκdefined in terms of Kolmogorov complexity. We discuss implications for point-to-set principles.  more » « less
Award ID(s):
1900716
PAR ID:
10642281
Author(s) / Creator(s):
 ;  
Publisher / Repository:
Association for Computing Machinery
Date Published:
Journal Name:
ACM Transactions on Computation Theory
ISSN:
1942-3454
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, The Journal of Geometric Analysis)
    null (Ed.)
    Abstract The uniformization and hyperbolization transformations formulated by Bonk et al. in “Uniformizing Gromov Hyperbolic Spaces” , Astérisque, vol 270 (2001), dealt with geometric properties of metric spaces. In this paper we consider metric measure spaces and construct a parallel transformation of measures under the uniformization and hyperbolization procedures. We show that if a locally compact roughly starlike Gromov hyperbolic space is equipped with a measure that is uniformly locally doubling and supports a uniformly local p -Poincaré inequality, then the transformed measure is globally doubling and supports a global p -Poincaré inequality on the corresponding uniformized space. In the opposite direction, we show that such global properties on bounded locally compact uniform spaces yield similar uniformly local properties for the transformed measures on the corresponding hyperbolized spaces. We use the above results on uniformization of measures to characterize when a Gromov hyperbolic space, equipped with a uniformly locally doubling measure supporting a uniformly local p -Poincaré inequality, carries nonconstant globally defined p -harmonic functions with finite p -energy. We also study some geometric properties of Gromov hyperbolic and uniform spaces. While the Cartesian product of two Gromov hyperbolic spaces need not be Gromov hyperbolic, we construct an indirect product of such spaces that does result in a Gromov hyperbolic space. This is done by first showing that the Cartesian product of two bounded uniform domains is a uniform domain. 
    more » « less
  2. ; (, Transactions of the American Mathematical Society)
    In this paper we construct short time classical solutions to a class of master equations in the presence of non-degenerate individual noise arising in the theory of mean field games. The considered Hamiltonians are non-separable andlocalfunctions of the measure variable, therefore the equation is restricted to absolutely continuous measures whose densities lie in suitable Sobolev spaces. Our results hold for smooth enough Hamiltonians, without any additional structural conditions as convexity or monotonicity. 
    more » « less
  3. ; (, Pure and Applied Analysis)
    We study all the ways that a given convex body in d dimensions can break into countably many pieces that move away from each other rigidly at constant velocity, with no rotation or shearing. The initial velocity field is locally constant a.e., but may be continuous and/or fail to be integrable. For any choice of mass-velocity pairs for the pieces, such a motion can be generated by the gradient of a convex potential that is affine on each piece. We classify such potentials in terms of a countable version of a theorem of Alexandrov for convex polytopes, and prove a stability theorem. For bounded velocities, there is a bijection between the mass-velocity data and optimal transport flows (Wasserstein geodesics) that are locally incompressible. Given any rigidly breaking velocity field that is the gradient of a continuous potential, the convexity of the potential is established under any of several conditions, such as the velocity field being continuous, the potential being semiconvex, the mass measure generated by a convexified transport potential being absolutely continuous, or there being a finite number of pieces. Also we describe a number of curious and paradoxical examples having fractal structure. 
    more » « less
  4. ; ; (, Quantum)
    A powerful operational paradigm for distributed quantum information processing involves manipulating pre-shared entanglement by local operations and classical communication (LOCC). The LOCC round complexity of a given task describes how many rounds of classical communication are needed to complete the task. Despite some results separating one-round versus two-round protocols, very little is known about higher round complexities. In this paper, we revisit the task of one-shot random-party entanglement distillation as a way to highlight some interesting features of LOCC round complexity. We first show that for random-party distillation in three qubits, the number of communication rounds needed in an optimal protocol depends on the entanglement measure used; for the same fixed state some entanglement measures need only two rounds to maximize whereas others need an unbounded number of rounds. In doing so, we construct a family of LOCC instruments that require an unbounded number of rounds to implement. We then prove explicit tight lower bounds on the LOCC round number as a function of distillation success probability. Our calculations show that the original W-state random distillation protocol by Fortescue and Lo is essentially optimal in terms of round complexity. 
    more » « less
  5. ; ; (, Computability)
    We prove that, for every 0 ⩽ s ⩽ 1, there is a Hamel basis of the vector space of reals over the field of rationals that has Hausdorff dimension s. The logic of our proof is of particular interest. The statement of our theorem is classical; it does not involve the theory of computing. However, our proof makes essential use of algorithmic fractal dimension–a computability-theoretic construct–and the point-to-set principle of J. Lutz and N. Lutz (2018). 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email