More Like this

1. COUNTABLE LENGTH EVERYWHERE CLUB UNIFORMIZATION

   https://doi.org/10.1017/jsl.2022.78  

   CHAN, WILLIAM; JACKSON, STEPHEN; TRANG, NAM (November 2022, The Journal of Symbolic Logic)

   Abstract Assume $$\mathsf {ZF} + \mathsf {AD}$$ and all sets of reals are Suslin. Let $$\Gamma $$ be a pointclass closed under $$\wedge $$ , $$\vee $$ , $$\forall ^{\mathbb {R}}$$ , continuous substitution, and has the scale property. Let $$\kappa = \delta (\Gamma )$$ be the supremum of the length of prewellorderings on $$\mathbb {R}$$ which belong to $$\Delta = \Gamma \cap \check \Gamma $$ . Let $$\mathsf {club}$$ denote the collection of club subsets of $$\kappa $$ . Then the countable length everywhere club uniformization holds for $$\kappa $$ : For every relation $$R \subseteq {}^{<{\omega _1}}\kappa \times \mathsf {club}$$ with the property that for all $$\ell \in {}^{<{\omega _1}}\kappa $$ and clubs $$C \subseteq D \subseteq \kappa $$ , $$R(\ell ,D)$$ implies $$R(\ell ,C)$$ , there is a uniformization function $$\Lambda : \mathrm {dom}(R) \rightarrow \mathsf {club}$$ with the property that for all $$\ell \in \mathrm {dom}(R)$$ , $$R(\ell ,\Lambda (\ell ))$$ . In particular, under these assumptions, for all $$n \in \omega $$ , $$\boldsymbol {\delta }^1_{2n + 1}$$ satisfies the countable length everywhere club uniformization. 

   more » « less
2. Outlier robust multivariate polynomial regression

   Arora, Vipul; Bhattacharyya, Arnab; Boban, Mathews; Guruswami, Venkatesan; Kelman, Esty (September 0024, Proceedings of the European Symposium on Algorithms (ESA),)

   We study the problem of robust multivariate polynomial regression: let p\colon\mathbb{R}^n\to\mathbb{R} be an unknown n-variate polynomial of degree at most d in each variable. We are given as input a set of random samples (\mathbf{x}_i,y_i) \in [-1,1]^n \times \mathbb{R} that are noisy versions of (\mathbf{x}_i,p(\mathbf{x}_i)). More precisely, each \mathbf{x}_i is sampled independently from some distribution \chi on [-1,1]^n, and for each i independently, y_i is arbitrary (i.e., an outlier) with probability at most \rho < 1/2, and otherwise satisfies |y_i-p(\mathbf{x}_i)|\leq\sigma. The goal is to output a polynomial \hat{p}, of degree at most d in each variable, within an \ell_\infty-distance of at most O(\sigma) from p. Kane, Karmalkar, and Price [FOCS'17] solved this problem for n=1. We generalize their results to the n-variate setting, showing an algorithm that achieves a sample complexity of O_n(d^n\log d), where the hidden constant depends on n, if \chi is the n-dimensional Chebyshev distribution. The sample complexity is O_n(d^{2n}\log d), if the samples are drawn from the uniform distribution instead. The approximation error is guaranteed to be at most O(\sigma), and the run-time depends on \log(1/\sigma). In the setting where each \mathbf{x}_i and y_i are known up to N bits of precision, the run-time's dependence on N is linear. We also show that our sample complexities are optimal in terms of d^n. Furthermore, we show that it is possible to have the run-time be independent of 1/\sigma, at the cost of a higher sample complexity. 

   more » « less
3. MAXIMAL TOWERS AND ULTRAFILTER BASES IN COMPUTABILITY THEORY

   https://doi.org/10.1017/jsl.2022.60  

   LEMPP, STEFFEN; MILLER, JOSEPH S.; NIES, ANDRÉ; SOSKOVA, MARIYA I. (August 2022, The Journal of Symbolic Logic)

   Abstract The tower number $${\mathfrak t}$$ and the ultrafilter number $$\mathfrak {u}$$ are cardinal characteristics from set theory. They are based on combinatorial properties of classes of subsets of $$\omega $$ and the almost inclusion relation $$\subseteq ^*$$ between such subsets. We consider analogs of these cardinal characteristics in computability theory. We say that a sequence $$(G_n)_{n \in {\mathbb N}}$$ of computable sets is a tower if $$G_0 = {\mathbb N}$$ , $$G_{n+1} \subseteq ^* G_n$$ , and $$G_n\smallsetminus G_{n+1}$$ is infinite for each n . A tower is maximal if there is no infinite computable set contained in all $$G_n$$ . A tower $${\left \langle {G_n}\right \rangle }_{n\in \omega }$$ is an ultrafilter base if for each computable R , there is n such that $$G_n \subseteq ^* R$$ or $$G_n \subseteq ^* \overline R$$ ; this property implies maximality of the tower. A sequence $$(G_n)_{n \in {\mathbb N}}$$ of sets can be encoded as the “columns” of a set $$G\subseteq \mathbb N$$ . Our analogs of $${\mathfrak t}$$ and $${\mathfrak u}$$ are the mass problems of sets encoding maximal towers, and of sets encoding towers that are ultrafilter bases, respectively. The relative position of a cardinal characteristic broadly corresponds to the relative computational complexity of the mass problem. We use Medvedev reducibility to formalize relative computational complexity, and thus to compare such mass problems to known ones. We show that the mass problem of ultrafilter bases is equivalent to the mass problem of computing a function that dominates all computable functions, and hence, by Martin’s characterization, it captures highness. On the other hand, the mass problem for maximal towers is below the mass problem of computing a non-low set. We also show that some, but not all, noncomputable low sets compute maximal towers: Every noncomputable (low) c.e. set computes a maximal tower but no 1-generic $$\Delta ^0_2$$ -set does so. We finally consider the mass problems of maximal almost disjoint, and of maximal independent families. We show that they are Medvedev equivalent to maximal towers, and to ultrafilter bases, respectively. 

   more » « less
4. The Borel complexity of the space of left‐orderings, low‐dimensional topology, and dynamics

   https://doi.org/10.1112/jlms.70024  

   Calderoni, Filippo; Clay, Adam (November 2024, Journal of the London Mathematical Society)

   Abstract We develop new tools to analyze the complexity of the conjugacy equivalence relation , whenever is a left‐orderable group. Our methods are used to demonstrate nonsmoothness of for certain groups of dynamical origin, such as certain amalgams constructed from Thompson's group . We also initiate a systematic analysis of , where is a 3‐manifold. We prove that if is not prime, then is a universal countable Borel equivalence relation, and show that in certain cases the complexity of is bounded below by the complexity of the conjugacy equivalence relation arising from the fundamental group of each of the JSJ pieces of . We also prove that if is the complement of a nontrivial knot in then is not smooth, and show how determining smoothness of for all knot manifolds is related to the L‐space conjecture. 

   more » « less
5. On the three ball theorem for solutions of the Helmholtz equation

   https://doi.org/10.1007/s40627-021-00070-3  

   Berge, Stine Marie; Malinnikova, Eugenia (June 2021, Complex Analysis and its Synergies)

   null (Ed.)

   Abstract Let $$u_{k}$$ u k be a solution of the Helmholtz equation with the wave number k , $$\varDelta u_{k}+k^{2} u_{k}=0$$ Δ u k + k 2 u k = 0 , on (a small ball in) either $${\mathbb {R}}^{n}$$ R n , $${\mathbb {S}}^{n}$$ S n , or $${\mathbb {H}}^{n}$$ H n . For a fixed point p , we define $$M_{u_{k}}(r)=\max _{d(x,p)\le r}|u_{k}(x)|.$$ M u k ( r ) = max d ( x , p ) ≤ r | u k ( x ) | . The following three ball inequality $$M_{u_{k}}(2r)\le C(k,r,\alpha )M_{u_{k}}(r)^{\alpha }M_{u_{k}}(4r)^{1-\alpha }$$ M u k ( 2 r ) ≤ C ( k , r , α ) M u k ( r ) α M u k ( 4 r ) 1 - α is well known, it holds for some $$\alpha \in (0,1)$$ α ∈ ( 0 , 1 ) and $$C(k,r,\alpha )>0$$ C ( k , r , α ) > 0 independent of $$u_{k}$$ u k . We show that the constant $$C(k,r,\alpha )$$ C ( k , r , α ) grows exponentially in k (when r is fixed and small). We also compare our result with the increased stability for solutions of the Cauchy problem for the Helmholtz equation on Riemannian manifolds. 

   more » « less