3 Search Results for "Huang, Thomas"

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-dev.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.2011.249
The Complexity of Weighted Boolean #CSP Modulo k

Authors: Heng Guo, Sangxia Huang, Pinyan Lu, and Mingji Xia

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
We prove a complexity dichotomy theorem for counting weighted Boolean CSP modulo k for any positive integer $k>1$. This generalizes a theorem by Faben for the unweighted setting. In the weighted setting, there are new interesting tractable problems. We first prove a dichotomy theorem for the finite field case where k is a prime. It turns out that the dichotomy theorem for the finite field is very similar to the one for the complex weighted Boolean #CSP, found by [Cai, Lu and Xia, STOC 2009]. Then we further extend the result to an arbitrary integer k.
Cite as

Heng Guo, Sangxia Huang, Pinyan Lu, and Mingji Xia. The Complexity of Weighted Boolean #CSP Modulo k. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 249-260, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{guo_et_al:LIPIcs.STACS.2011.249,
  author =	{Guo, Heng and Huang, Sangxia and Lu, Pinyan and Xia, Mingji},
  title =	{{The Complexity of Weighted Boolean #CSP Modulo k}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{249--260},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.249},
  URN =		{urn:nbn:de:0030-drops-30158},
  doi =		{10.4230/LIPIcs.STACS.2011.249},
  annote =	{Keywords: #CSP, dichotomy theorem, counting problems, computational complexity}
}
Document
DOI: 10.4230/DagSemRep.268
Multi-Image Search, Filtering, Reasoning and Visualisation (Dagstuhl Seminar 00111)

Authors: Alfred Bruckstein, Thomas Huang, Reinhard Klette, and SongDe Ma

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Alfred Bruckstein, Thomas Huang, Reinhard Klette, and SongDe Ma. Multi-Image Search, Filtering, Reasoning and Visualisation (Dagstuhl Seminar 00111). Dagstuhl Seminar Report 268, pp. 1-35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{bruckstein_et_al:DagSemRep.268,
  author =	{Bruckstein, Alfred and Huang, Thomas and Klette, Reinhard and Ma, SongDe},
  title =	{{Multi-Image Search, Filtering, Reasoning and Visualisation (Dagstuhl Seminar 00111)}},
  pages =	{1--35},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{268},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.268},
  URN =		{urn:nbn:de:0030-drops-151530},
  doi =		{10.4230/DagSemRep.268},
}
  • Refine by Author
  • 1 Bruckstein, Alfred
  • 1 Guo, Heng
  • 1 Huang, Sangxia
  • 1 Huang, Thomas
  • 1 Huang, Xiang
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Abstract machines
  • 1 Theory of computation → Interactive computation
  • 1 Theory of computation → Probabilistic computation

  • Refine by Keyword
  • 1 #CSP
  • 1 Analog computation
  • 1 Chemical reaction networks
  • 1 Population protocols
  • 1 computational complexity
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2000
  • 1 2011
  • 1 2022

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 Imprint Privacy Contact