skip to main content


Title: Equivalence relations and determinacy
We introduce the notion of [Formula: see text]-determinacy for [Formula: see text] a pointclass and [Formula: see text] an equivalence relation on a Polish space [Formula: see text]. A case of particular interest is the case when [Formula: see text] is the (left) shift-action of [Formula: see text] on [Formula: see text] where [Formula: see text] or [Formula: see text]. We show that for all shift actions by countable groups [Formula: see text], and any “reasonable” pointclass [Formula: see text], that [Formula: see text]-determinacy implies [Formula: see text]-determinacy. We also prove a corresponding result when [Formula: see text] is a subshift of finite type of the shift map on [Formula: see text].  more » « less
Award ID(s):
1800323
PAR ID:
10350249
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Journal of Mathematical Logic
Volume:
22
Issue:
01
ISSN:
0219-0613
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. null (Ed.)
    We consider criteria for the differentiability of functions with continuous Laplacian on the Sierpiński Gasket and its higher-dimensional variants [Formula: see text], [Formula: see text], proving results that generalize those of Teplyaev [Gradients on fractals, J. Funct. Anal. 174(1) (2000) 128–154]. When [Formula: see text] is equipped with the standard Dirichlet form and measure [Formula: see text] we show there is a full [Formula: see text]-measure set on which continuity of the Laplacian implies existence of the gradient [Formula: see text], and that this set is not all of [Formula: see text]. We also show there is a class of non-uniform measures on the usual Sierpiński Gasket with the property that continuity of the Laplacian implies the gradient exists and is continuous everywhere in sharp contrast to the case with the standard measure. 
    more » « less
  2. We investigate the problem of recovering jointly [Formula: see text]-rank and [Formula: see text]-bisparse matrices from as few linear measurements as possible, considering arbitrary measurements as well as rank-one measurements. In both cases, we show that [Formula: see text] measurements make the recovery possible in theory, meaning via a nonpractical algorithm. In case of arbitrary measurements, we investigate the possibility of achieving practical recovery via an iterative-hard-thresholding algorithm when [Formula: see text] for some exponent [Formula: see text]. We show that this is feasible for [Formula: see text], and that the proposed analysis cannot cover the case [Formula: see text]. The precise value of the optimal exponent [Formula: see text] is the object of a question, raised but unresolved in this paper, about head projections for the jointly low-rank and bisparse structure. Some related questions are partially answered in passing. For rank-one measurements, we suggest on arcane grounds an iterative-hard-thresholding algorithm modified to exploit the nonstandard restricted isometry property obeyed by this type of measurements. 
    more » « less
  3. Computing the Fréchet distance between two polygonal curves takes roughly quadratic time. In this paper, we show that for a special class of curves the Fréchet distance computations become easier. Let [Formula: see text] and [Formula: see text] be two polygonal curves in [Formula: see text] with [Formula: see text] and [Formula: see text] vertices, respectively. We prove four results for the case when all edges of both curves are long compared to the Fréchet distance between them: (1) a linear-time algorithm for deciding the Fréchet distance between two curves, (2) an algorithm that computes the Fréchet distance in [Formula: see text] time, (3) a linear-time [Formula: see text]-approximation algorithm, and (4) a data structure that supports [Formula: see text]-time decision queries, where [Formula: see text] is the number of vertices of the query curve and [Formula: see text] the number of vertices of the preprocessed curve. 
    more » « less
  4. We study the problem of covering barrier points by mobile sensors. Each sensor is represented by a point in the plane with the same covering range [Formula: see text] so that any point within distance [Formula: see text] from the sensor can be covered by the sensor. Given a set [Formula: see text] of [Formula: see text] points (called “barrier points”) and a set [Formula: see text] of [Formula: see text] points (representing the “sensors”) in the plane, the problem is to move the sensors so that each barrier point is covered by at least one sensor and the maximum movement of all sensors is minimized. The problem is NP-hard. In this paper, we consider two line-constrained variations of the problem and present efficient algorithms that improve the previous work. In the first problem, all sensors are given on a line [Formula: see text] and are required to move on [Formula: see text] only while the barrier points can be anywhere in the plane. We propose an [Formula: see text] time algorithm for the problem. We also consider the weighted case where each sensor has a weight; we give an [Formula: see text] time algorithm for this case. In the second problem, all barrier points are on [Formula: see text] while all sensors are in the plane but are required to move onto [Formula: see text] to cover all barrier points. We also solve the weighted case in [Formula: see text] time.

     
    more » « less
  5. Let [Formula: see text] be an integer and [Formula: see text] be a finite field with [Formula: see text] elements. We prove several results on the distribution in short intervals of polynomials in [Formula: see text] that are not divisible by the [Formula: see text]th power of any non-constant polynomial. Our main result generalizes a recent theorem by Carmon and Entin on the distribution of squarefree polynomials to all [Formula: see text]. We also develop polynomial versions of the classical techniques used to study gaps between [Formula: see text]-free integers in [Formula: see text]. We apply these techniques to obtain analogs in [Formula: see text] of some classical theorems on the distribution of [Formula: see text]-free integers. The latter results complement the main theorem in the case when the degrees of the polynomials are of moderate size.

     
    more » « less