More Like this

1. On the first-order parts of problems in the Weihrauch degrees

   https://doi.org/10.3233/COM-230446  

   Dzhafarov, Damir D; Solomon, Reed; Yokoyama, Keita (January 2024, Computability)

   We introduce the notion of the first-order part of a problem in the Weihrauch degrees. Informally, the first-order part of a problem P is the strongest problem with codomaixn ω that is Weihrauch reducible to P. We show that the first-order part is always well-defined, examine some of the basic properties of this notion, and characterize the first-order parts of several well-known problems from the literature. 

   more » « less
2. Minimal covers in the Weihrauch degrees

   https://doi.org/10.1090/proc/16952  

   Lempp, Steffen; Miller, Joseph; Pauly, Arno; Soskova, Mariya; Valenti, Manlio (November 2024, Proceedings of the American Mathematical Society)

   In this paper, we study the existence of minimal covers and strong minimal covers in the Weihrauch degrees. We characterize when a problem  $f$is a minimal cover or strong minimal cover of a problem  $h$. We show that strong minimal covers only exist in the cone below  $id$and that the Weihrauch lattice above  $id$is dense. From this, we conclude that the degree of $id$is first-order definable in the Weihrauch degrees and that the first-order theory of the Weihrauch degrees is computably isomorphic to third-order arithmetic. 

   more » « less
3. Multiplicative series, modular forms, and Mandelbrot polynomials

   https://doi.org/10.1090/mcom/3564  

   Larsen, Michael (January 2021, Mathematics of Computation)

   null (Ed.)

   We say a power series ∑ n = 0 ∞ a n q n \sum _{n=0}^\infty a_n q^n is multiplicative if the sequence 1 , a 2 / a 1 , … , a n / a 1 , … 1,a_2/a_1,\ldots ,a_n/a_1,\ldots is so. In this paper, we consider multiplicative power series f f such that f 2 f^2 is also multiplicative. We find a number of examples for which f f is a rational function or a theta series and prove that the complete set of solutions is the locus of a (probably reducible) affine variety over C \mathbb {C} . The precise determination of this variety turns out to be a finite computational problem, but it seems to be beyond the reach of current computer algebra systems. The proof of the theorem depends on a bound on the logarithmic capacity of the Mandelbrot set. 

   more » « less
4. On finite energy monopoles on $$C x \Sigma$$.

   Wang, Donghao (July 2019, ArXiv.org)

   Let $$X=\mathbb{C}\times\Sigma$$ be the product of the complex plane and a compact Riemann surface. We establish a classification theorem of solutions to the Seiberg-Witten equation on $$X$$ with finite analytic energy. The spin bundle $$S^+\to X$$ splits as $$L^+\oplus L^-$$. When $$2-2g\leq c_1(S^+)[\Sigma]<0$$, the moduli space is in bijection with the moduli space of pairs $$((L^+,\bar{\partial}), f)$$ where $$(L^+,\bar{\partial})$$ is a holomorphic structure on $L^+$ and $$f: \mathbb{C}\to H^0(\Sigma, L^+,\bar{\partial})$$ is a polynomial map. Moreover, the solution has analytic energy $$-4\pi^2d\cdot c_1(S^+)[\Sigma]$$ if $$f$$ has degree $$d$$. When $$c_1(S^+)=0$$, all solutions are reducible and the moduli space is the space of flat connections on $$\bigwedge^2 S^+$$. We also estimate the decay rate at infinity for these solutions. 

   more » « less
5. The Complexity of Iterated Reversible Computation

   https://doi.org/10.46298/theoretics.23.10  

   Eppstein, David (December 2023, TheoretiCS)

   We study a class of functional problems reducible to computing $$f^{(n)}(x)$$for inputs $$n$$ and $$x$$, where $$f$$ is a polynomial-time bijection. As we prove,the definition is robust against variations in the type of reduction used inits definition, and in whether we require $$f$$ to have a polynomial-time inverseor to be computible by a reversible logic circuit. These problems arecharacterized by the complexity class $$\mathsf{FP}^{\mathsf{PSPACE}}$$, andinclude natural $$\mathsf{FP}^{\mathsf{PSPACE}}$$-complete problems in circuitcomplexity, cellular automata, graph algorithms, and the dynamical systemsdescribed by piecewise-linear transformations. 

   more » « less