Search Results

Documents authored by Huang, Xiang

Document
DOI: 10.4230/LIPIcs.DNA.28.7
Computing Real Numbers with Large-Population Protocols Having a Continuum of Equilibria

Authors: Xiang Huang and Rachel N. Huls

Published in: LIPIcs, Volume 238, 28th International Conference on DNA Computing and Molecular Programming (DNA 28) (2022)

Abstract
Bournez, Fraigniaud, and Koegler [Bournez et al., 2012] defined a number in [0,1] as computable by their Large-Population Protocol (LPP) model, if the proportion of agents in a set of marked states converges to said number over time as the population grows to infinity. The notion, however, restricts the ordinary differential equations (ODEs) associated with an LPP to have only finitely many equilibria. This restriction places an intrinsic limitation on the model. As a result, a number is computable by an LPP if and only if it is algebraic, namely, not a single transcendental number can be computed under this notion. In this paper, we lift the finitary requirement on equilibria. That is, we consider systems with a continuum of equilibria. We show that essentially all numbers in [0,1] that are computable by bounded general-purpose analog computers (GPACs) or chemical reaction networks (CRNs) can also be computed by LPPs under this new definition. This implies a rich series of numbers (e.g., the reciprocal of Euler’s constant, π/4, Euler’s γ, Catalan’s constant, and Dottie number) are all computable by LPPs. Our proof is constructive: We develop an algorithm that transfers bounded GPACs/CRNs into LPPs. Our algorithm also fixes a gap in Bournez et al.’s construction of LPPs designed to compute any arbitrary algebraic number in [0,1].
Cite as

Xiang Huang and Rachel N. Huls. Computing Real Numbers with Large-Population Protocols Having a Continuum of Equilibria. In 28th International Conference on DNA Computing and Molecular Programming (DNA 28). Leibniz International Proceedings in Informatics (LIPIcs), Volume 238, pp. 7:1-7:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.DNA.28.7,
  author =	{Huang, Xiang and Huls, Rachel N.},
  title =	{{Computing Real Numbers with Large-Population Protocols Having a Continuum of Equilibria}},
  booktitle =	{28th International Conference on DNA Computing and Molecular Programming (DNA 28)},
  pages =	{7:1--7:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-253-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{238},
  editor =	{Ouldridge, Thomas E. and Wickham, Shelley F. J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.28.7},
  URN =		{urn:nbn:de:0030-drops-167922},
  doi =		{10.4230/LIPIcs.DNA.28.7},
  annote =	{Keywords: Population protocols, Chemical reaction networks, Analog computation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.51
Asymptotic Divergences and Strong Dichotomy

Authors: Xiang Huang, Jack H. Lutz, Elvira Mayordomo, and Donald M. Stull

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
The Schnorr-Stimm dichotomy theorem [Schnorr and Stimm, 1972] concerns finite-state gamblers that bet on infinite sequences of symbols taken from a finite alphabet Σ. The theorem asserts that, for any such sequence S, the following two things are true. (1) If S is not normal in the sense of Borel (meaning that every two strings of equal length appear with equal asymptotic frequency in S), then there is a finite-state gambler that wins money at an infinitely-often exponential rate betting on S. (2) If S is normal, then any finite-state gambler betting on S loses money at an exponential rate betting on S. In this paper we use the Kullback-Leibler divergence to formulate the lower asymptotic divergence div(S||α) of a probability measure α on Σ from a sequence S over Σ and the upper asymptotic divergence Div(S||α) of α from S in such a way that a sequence S is α-normal (meaning that every string w has asymptotic frequency α(w) in S) if and only if Div(S||α)=0. We also use the Kullback-Leibler divergence to quantify the total risk Risk_G(w) that a finite-state gambler G takes when betting along a prefix w of S. Our main theorem is a strong dichotomy theorem that uses the above notions to quantify the exponential rates of winning and losing on the two sides of the Schnorr-Stimm dichotomy theorem (with the latter routinely extended from normality to α-normality). Modulo asymptotic caveats in the paper, our strong dichotomy theorem says that the following two things hold for prefixes w of S. (1') The infinitely-often exponential rate of winning in 1 is 2^{Div(S||α)|w|}. (2') The exponential rate of loss in 2 is 2^{-Risk_G(w)}. We also use (1') to show that 1-Div(S||α)/c, where c= log(1/ min_{a∈Σ} α(a)), is an upper bound on the finite-state α-dimension of S and prove the dual fact that 1-div(S||α)/c is an upper bound on the finite-state strong α-dimension of S.
Cite as

Xiang Huang, Jack H. Lutz, Elvira Mayordomo, and Donald M. Stull. Asymptotic Divergences and Strong Dichotomy. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 51:1-51:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.STACS.2020.51,
  author =	{Huang, Xiang and Lutz, Jack H. and Mayordomo, Elvira and Stull, Donald M.},
  title =	{{Asymptotic Divergences and Strong Dichotomy}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{51:1--51:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.51},
  URN =		{urn:nbn:de:0030-drops-119125},
  doi =		{10.4230/LIPIcs.STACS.2020.51},
  annote =	{Keywords: finite-state dimension, finite-state gambler, Kullback-Leibler divergence, normal sequences}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.86
Polynomial Space Randomness in Analysis

Authors: Xiang Huang and Donald M. Stull

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
We study the interaction between polynomial space randomness and a fundamental result of analysis, the Lebesgue differentiation theorem. We generalize Ko's framework for polynomial space computability in R^n to define weakly pspace-random points, a new variant of polynomial space randomness. We show that the Lebesgue differentiation theorem characterizes weakly pspace random points. That is, a point x is weakly pspace random if and only if the Lebesgue differentiation theorem holds for a point x for every pspace L_1-computable function.
Cite as

Xiang Huang and Donald M. Stull. Polynomial Space Randomness in Analysis. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 86:1-86:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.MFCS.2016.86,
  author =	{Huang, Xiang and Stull, Donald M.},
  title =	{{Polynomial Space Randomness in Analysis}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{86:1--86:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.86},
  URN =		{urn:nbn:de:0030-drops-64943},
  doi =		{10.4230/LIPIcs.MFCS.2016.86},
  annote =	{Keywords: algorithmic randomness, computable analysis, resource-bounded randomness, complexity theory}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact