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.


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. 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. 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. 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
  4. 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
  5. Abstract Bacterial cells at fluid interfaces can self-assemble into collective communities with stunning macroscopic morphologies. Within these soft, living materials, called pellicles, constituent cells gain group-level survival advantages including increased antibiotic resistance. However, the regulatory and structural components that drive pellicle self-patterning are not well defined. Here, usingVibrio choleraeas our model system, we report that two sets of matrix proteins and a key quorum-sensing regulator jointly orchestrate the sequential mechanical instabilities underlying pellicle morphogenesis, culminating in fractal patterning. A pair of matrix proteins, RbmC and Bap1, maintain pellicle localization at the interface and prevent self-peeling. A single matrix protein, RbmA, drives a morphogenesis program marked by a cascade of ever finer wrinkles with fractal scaling in wavelength. Artificial expression ofrbmArestores fractal wrinkling to a ΔrbmAmutant and enables precise tuning of fractal dimensions. The quorum-sensing regulatory small RNAs Qrr1-4 first activate matrix synthesis to launch pellicle primary wrinkling and ridge instabilities. Subsequently, via a distinct mechanism, Qrr1-4 suppress fractal wrinkling to promote fine modulation of pellicle morphology. Our results connect cell-cell signaling and architectural components to morphogenic patterning and suggest that manipulation of quorum-sensing regulators or synthetic control ofrbmAexpression could underpin strategies to engineer soft biomaterial morphologies on demand. 
    more » « less