More Like this

1. THE TREE PIGEONHOLE PRINCIPLE IN THE WEIHRAUCH DEGREES

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

   DZHAFAROV, DAMIR D; SOLOMON, REED; VALENTI, MANLIO (February 2025, The Journal of Symbolic Logic)

   Abstract We study versions of the tree pigeonhole principle,$$\mathsf {TT}^1$$, in the context of Weihrauch-style computable analysis. The principle has previously been the subject of extensive research in reverse mathematics, an outstanding question of which investigation is whether$$\mathsf {TT}^1$$is$$\Pi ^1_1$$-conservative over the ordinary pigeonhole principle,$$\mathsf {RT}^1$$. Using the recently introduced notion of the first-order part of an instance-solution problem, we formulate the analog of this question for Weihrauch reducibility, and give an affirmative answer. In combination with other results, we use this to show that unlike$$\mathsf {RT}^1$$, the problem$$\mathsf {TT}^1$$is not Weihrauch requivalent to any first-order problem. Our proofs develop new combinatorial machinery for constructing and understanding solutions to instances of$$\mathsf {TT}^1$$. 

   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. A note on the diamond operator

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

   Westrick, Linda (January 2020, Computability)

   We show that if F has a computable instance and the compositional product of F with itself is Weihrauch reducible to F, then F-diamond is Weihrauch reducible to F. The compositional product allows the use of two principles in sequence, while the diamond operator allows an arbitrary but finite number of uses of the given principle in sequence. This answers a question of Pauly. 

   more » « less
4. On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem

   Göös, Mika; Kamath, Pritish; Sotiraki, Katerina; Zampetakis, Manolis (January 2020, Computational Complexity Conference 2020)

   null (Ed.)

   We study the search problem class PPA_q defined as a modulo-q analog of the well-known polynomial parity argument class PPA introduced by Papadimitriou (JCSS 1994). Our first result shows that this class can be characterized in terms of PPA_p for prime p. Our main result is to establish that an explicit version of a search problem associated to the Chevalley - Warning theorem is complete for PPA_p for prime p. This problem is natural in that it does not explicitly involve circuits as part of the input. It is the first such complete problem for PPA_p when p ≥ 3. Finally we discuss connections between Chevalley-Warning theorem and the well-studied short integer solution problem and survey the structural properties of PPA_q. 

   more » « less
5. Systemic Robustness: A Mean‐Field Particle System Approach

   https://doi.org/10.1111/mafi.12459  

   Bayraktar, Erhan; Guo, Gaoyue; Tang, Wenpin; Zhang, Yuming Paul (February 2025, Mathematical Finance)

   ABSTRACT This paper is concerned with the problem of capital provision in a large particle system modeled by stochastic differential equations involving hitting times, which arises from considerations of systemic risk in a financial network. Motivated by Tang and Tsai, we focus on the number or proportion of surviving entities that never default to measure the systemic robustness. First we show that the mean‐field particle system and its limit McKean–Vlasov equation are both well‐posed by virtue of the notion of minimal solutions. We then establish a connection between the proportion of surviving entities in the large particle system and the probability of default in the McKean–Vlasov equation as the size of the interacting particle system tends to infinity. Finally, we study the asymptotic efficiency of capital provision for different drift , which is linked to the economy regime: The expected number of surviving entities has a uniform upper bound if ; it is of order if ; and it is of order if , where the effect of capital provision is negligible. 

   more » « less