More Like this

1. CHARACTERIZING THE CONTINUOUS DEGREES

   Andrews, Uri; Igusa, Gregory; Miller, Joseph S.; Soskova, Mariya I. (January 2019, Israel journal of mathematics)

   The continuous degrees measure the computability-theoretic content of elements of computable metric spaces. They properly extend the Turing degrees and naturally embed into the enumeration degrees. Although nontotal (i.e., non-Turing) continuous degrees exist, they are all very close to total: joining a continuous degree with a total degree that is not below it always results in a total degree. We call this property almost totality. We prove that the almost total degrees coincide with the continuous degrees. Since the total degrees are definable in the partial order of enumeration degrees, we see that the continuous degrees are also definable. Applying earlier work on the continuous degrees, this shows that the relation “PA above” on the total degrees is definable in the enumeration degrees. In order to prove that every almost total degree is continuous, we pass through another characterization of the continuous degrees that slightly simplifies one of Kihara and Pauly. We prove that the enumeration degree of A is continuous if and only if A is codable, meaning that A is enumeration above the complement of an infinite tree, every path of which enumerates A. 

   more » « less
2. The set of bounded continuous nowhere locally uniformly continuous functions is not Borel

   Alexander J. Izzo (January 2022, Houston journal of mathematics)

   It is known that for $$X$$ a nowhere locally compact metric space, the set of bounded continuous, nowhere locally uniformly continuous real-valued functions on $$X$$ contains a dense $$G_\delta$$ set in the space $$C_b(X)$$ of all bounded continuous real-valued functions on $$X$$ in the supremum norm. Furthermore, when $$X$$ is separable, the set of bounded continuous, nowhere locally uniformly continuous real-valued functions on $$X$$ is itself a $$G_\delta$$ set. We show that in contrast, when $$X$$ is nonseparable, this set of functions is not even a Borel set. 

   more » « less
3. The Replenishment Schedule to Minimize Peak Storage Problem: The Gap Between the Continuous and Discrete Versions of the Problem

   https://doi.org/10.1287/opre.2018.1839  

   Hochbaum, Dorit S.; Rao, Xu (September 2019, Operations Research)

   The replenishment storage problem (RSP) is to minimize the storage capacity requirement for a deterministic demand, multi-item inventory system, where each item has a given reorder size and cycle length. We consider the discrete RSP, where reorders can only take place at an integer time unit within the cycle. Discrete RSP was shown to be NP-hard for constant joint cycle length (the least common multiple of the length of all individual cycles). We show here that discrete RSP is weakly NP-hard for constant joint cycle length and prove that it is strongly NP-hard for nonconstant joint cycle length. For constant joint cycle-length discrete RSP, we further present a pseudopolynomial time algorithm that solves the problem optimally and the first known fully polynomial time approximation scheme (FPTAS) for the single-cycle RSP. The scheme is utilizing a new integer programming formulation of the problem that is introduced here. For the strongly NP-hard RSP with nonconstant joint cycle length, we provide a polynomial time approximation scheme (PTAS), which for any fixed [Formula: see text], provides a linear time [Formula: see text] approximate solution. The continuous RSP, where reorders can take place at any time within a cycle, seems (with our results) to be easier than the respective discrete problem. We narrow the previously known complexity gap between the continuous and discrete versions of RSP for the multi-cycle RSP (with either constant or nonconstant cycle length) and the single-cycle RSP with constant cycle length and widen the gap for single-cycle RSP with nonconstant cycle length. For the multi-cycle case and constant joint cycle length, the complexity status of continuous RSP is open, whereas it is proved here that the discrete RSP is weakly NP-hard. Under our conjecture that the continuous RSP is easier than the discrete one, this implies that continuous RSP on multi-cycle and constant joint cycle length (currently of unknown complexity status) is at most weakly NP-hard. 

   more » « less
4. From Targets to Rewards: Continuous Target Sets in the Algorithmic Search Framework

   https://doi.org/10.5220/0012370600003636  

   Knell, Milo; Rane, Sahil; Bicker, Forrest; Che, Tiger; Wu, Alan; Montañez, George (February 2024, Proceedings of the 16th International Conference on Agents and Artificial Intelligence - Volume 3: ICAART)

   Ana Paula Rocha, Luc Steels (Ed.)

   Many machine learning tasks have a measure of success that is naturally continuous, such as error under a loss function. We generalize the Algorithmic Search Framework (ASF), used for modeling machine learning domains as discrete search problems, to the continuous space. Moving from discrete target sets to a continuous measure of success extends the applicability of the ASF by allowing us to model fundamentally continuous notions like fuzzy membership. We generalize many results from the discrete ASF to the continuous space and prove novel results for a continuous measure of success. Additionally, we derive an upper bound for the expected performance of a search algorithm under arbitrary levels of quantization in the success measure, demonstrating a negative relationship between quantization and the performance upper bound. These results improve the fidelity of the ASF as a framework for modeling a range of machine learning and artificial intelligence tasks. 

   more » « less
5. Differentiability of Effective Fronts in the Continuous Setting in Two Dimensions

   https://doi.org/10.1093/imrn/rnad212  

   Tran, Hung V; Yu, Yifeng (September 2023, International Mathematics Research Notices)

   Abstract We study the effective front associated with first-order front propagations in two dimensions ($n=2$) in the periodic setting with continuous coefficients. Our main result says that that the boundary of the effective front is differentiable at every irrational point. Equivalently, the stable norm associated with a continuous $${\mathbb{Z}}^{2}$$-periodic Riemannian metric is differentiable at irrational points. This conclusion was obtained decades ago for smooth metrics [ 4, 6]. To the best of our knowledge, our result provides the first nontrivial property of the effective fronts in the continuous setting, which is the standard assumption in the literature of partial differential equations (PDE). Combining with the sufficiency result in [ 15], our result leads to a realization type conclusion: for continuous coefficients, a polygon could be an effective front if and only if it is centrally symmetric with rational vertices and nonempty interior. 

   more » « less