RSReed Solomon

Reed Solomon

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Reed Solomon has a total of 46 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    THE TREE PIGEONHOLE PRINCIPLE IN THE WEIHRAUCH DEGREES

    by Damir D. Dzhafarov, Reed Solomon, Manlio Valenti

    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$ .


  • Open Access

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

    by Damir D. Dzhafarov, Reed Solomon, Keita Yokoyama

    We introduce the notion of the \emph{first-order part} of a problem in the Weihrauch degrees. Informally, the first-order part of a problem $\mathsf{P}$ is the strongest problem with codomaixn $ω$ that is Weihrauch reducible to $\mathsf{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.


  • On the isomorphism problem for some classes of computable algebraic structures

    by Valentina S. Harizanov, Steffen Lempp, Charles F. D. McCoy, Andrei S. Morozov, Reed Solomon


  • Model completeness and relative decidability

    by Jennifer Chubb, Russell Miller, Reed Solomon


  • Open Access

    The determined property of Baire in reverse math

    by Eric P. Astor, Damir Dzhafarov, Antonio Montalbán, Reed Solomon, Linda Brown Westrick

    We define the notion of a determined Borel code in reverse math, and consider the principle $DPB$, which states that every determined Borel set has the property of Baire. We show that this principle is strictly weaker than $ATR$. Any $\omega$-model of $DPB$ must be closed under hyperarithmetic reduction, but $DPB$ is not a theory of hyperarithmetic analysis. We show that whenever $M\subseteq 2^\omega$ is the second-order part of an $\omega$-model of $DPB$, then for every $Z \in M$, there is a $G \in M$ such that $G$ is $\Delta^1_1$-generic relative to $Z$.

  • The reverse mathematics of Hindman’s Theorem for sums of exactly two elements

    by Barbara F. Csima, Damir D. Dzhafarov, Denis R. Hirschfeldt, Jr. Carl G. Jockusch, Reed Solomon, Linda Brown Westrick

    Hindman’s Theorem (HT) states that for every coloring of N with finitely many colors, there is an infinite set H ⊆ N such that all nonempty sums of distinct elements of H have the same color. The investigation of restricted versions of HT from the co


  • THE DETERMINED PROPERTY OF BAIRE IN REVERSE MATH

    by Eric P. Astor, Damir Dzhafarov, Antonio Montalbán, Reed Solomon, Linda Brown Westrick

    We define the notion of a completely determined Borel code in reverse mathematics, and consider the principle $CD - PB$ , which states that every completely determined Borel set has the property of Baire. We show that this principle is strictly weaker than $AT{R_0}$ . Any ω-model of $CD - PB$ must be closed under hyperarithmetic reduction, but $CD - PB$ is not a theory of hyperarithmetic analysis. We show that whenever $M \subseteq {2^\omega }$ is the second-order part of an ω-model of $CD - PB$ , then for every $Z \in M$ , there is a $G \in M$ such that G is ${\rm{\Delta }}_1^1$ -generic relative to Z.


  • Open Access

    Model completeness and relative decidability

    by Jennifer Chubb, Russell Miller, Reed Solomon

    We study the implications of model completeness of a theory for the effectiveness of presentations of models of that theory. It is immediate that for a computable model $\mathcal A$ of a computably enumerable, model complete theory, the entire elementary diagram $E(\mathcal A)$ must be decidable. We prove that indeed a c.e. theory $T$ is model complete if and only if there is a uniform procedure that succeeds in deciding $E(\mathcal A)$ from the atomic diagram $\Delta(\mathcal A)$ for all countable models $\mathcal A$ of $T$. Moreover, if every presentation of a single isomorphism type $\mathcal A$ has this property of relative decidability, then there must be a procedure with succeeds uniformly for all presentations of an expansion $(\mathcal A,\vec{a})$ by finitely many new constants. We end with a conjecture about the situation when all models of a theory are relatively decidable.

  • Open Access

    The reverse mathematics of Hindman's theorem for sums of exactly two elements

    by Barbara F. Csima, Damir D. Dzhafarov, Denis R. Hirschfeldt, Jr. Carl G. Jockusch, Reed Solomon, Linda Brown Westrick

    Hindman's Theorem (HT) states that for every coloring of $\mathbb N$ with finitely many colors, there is an infinite set $H \subseteq \mathbb N$ such that all nonempty sums of distinct elements of $H$ have the same color. The investigation of restricted versions of HT from the computability-theoretic and reverse-mathematical perspectives has been a productive line of research recently. In particular, HT$^{\leqslant n}_k$ is the restriction of HT to sums of at most $n$ many elements, with at most $k$ colors allowed, and HT$^{=n}_k$ is the restriction of HT to sums of \emph{exactly} $n$ many elements and $k$ colors. Even HT$^{\leqslant 2}_2$ appears to be a strong principle, and may even imply HT itself over RCA$_0$. In contrast, HT$^{=2}_2$ is known to be strictly weaker than HT over RCA$_0$, since HT$^{=2}_2$ follows immediately from Ramsey's Theorem for $2$-colorings of pairs. In fact, it was open for several years whether HT$^{=2}_2$ is computably true. We show that HT$^{=2}_2$ and similar results with addition replaced by subtraction and other operations are not provable in RCA$_0$, or even WKL$_0$. In fact, we show that there is a computable instance of HT$^{=2}_2$ such that all solutions can compute a function that is diagonally noncomputable relative to $\emptyset'$. It follows that there is a computable instance of HT$^{=2}_2$ with no $\Sigma^0_2$ solution, which is the best possible result with respect to the arithmetical hierarchy. Furthermore, a careful analysis of the proof of the result above about solutions DNC relative to $\emptyset'$ shows that HT$^{=2}_2$ implies RRT$^{=2}_2$, the Rainbow Ramsey Theorem for $2$-colorings of pairs, over RCA$_0$. The most interesting aspect of our construction of computable colorings as above is the use of an effective version of the Lov\'asz Local Lemma due to Rumyantsev and Shen.