Search Results

Documents authored by Chalk, Cameron

Document
DOI: 10.4230/LIPIcs.DNA.32.11
Universal Spatial Distribution Approximation in Equilibrium Lattice Models with Local Pairwise Interactions

Authors: Cameron Chalk and Erik Winfree

Published in: LIPIcs, Volume 387, 32nd International Conference on DNA Computing and Molecular Programming (DNA 32) (2026)

Abstract
Universality is one of the defining hallmarks of a useful neural network model: it means that the model is expressive enough, in principle, to learn arbitrary target behavior rather than being limited to a narrow class. Inspired by rigorous formal analogies between stochastic neural networks and lattice models in which molecules occupy discrete sites, contribute species-dependent interaction energies with neighbors, and rearrange according to the Boltzmann distribution, we ask whether interactions can be programmed to yield arbitrary spatial distributions. At the level of fine-grained spatial arrangements of species, universality fails: arbitrary spatial microstate distributions cannot be represented, as shown by a counting argument and explicit construction of unrepresentable distributions. Yet, for a natural observable - spatial patterns of molecular labels - universality can be achieved. We show that a grand-canonical lattice model of anisotropic molecules is universal for arbitrary label distributions, and a similar model with isotropic molecules is also universal given a simple symmetry-breaking boundary condition. Our results suggest that equilibrium systems of multivalent molecules undergoing stochastic rearrangement governed by local pairwise interactions can act similarly to probabilistic neural networks: with sufficient microstate detail in hidden dimensions, they can be universal in a meaningful macrostate observable.
Cite as

Cameron Chalk and Erik Winfree. Universal Spatial Distribution Approximation in Equilibrium Lattice Models with Local Pairwise Interactions. In 32nd International Conference on DNA Computing and Molecular Programming (DNA 32). Leibniz International Proceedings in Informatics (LIPIcs), Volume 387, pp. 11:1-11:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chalk_et_al:LIPIcs.DNA.32.11,
  author =	{Chalk, Cameron and Winfree, Erik},
  title =	{{Universal Spatial Distribution Approximation in Equilibrium Lattice Models with Local Pairwise Interactions}},
  booktitle =	{32nd International Conference on DNA Computing and Molecular Programming (DNA 32)},
  pages =	{11:1--11:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-444-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{387},
  editor =	{Scalise, Dominic and Schweller, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.32.11},
  URN =		{urn:nbn:de:0030-drops-267812},
  doi =		{10.4230/LIPIcs.DNA.32.11},
  annote =	{Keywords: universality, molecular programming, neural networks, self-assembly}
}
Document
DOI: 10.4230/LIPIcs.DNA.32.13
Contrastive Hebbian Learning for Multicomponent Liquids

Authors: Yancheng Du, Cameron Chalk, Salvador Buse, Lulu Qian, and Erik Winfree

Published in: LIPIcs, Volume 387, 32nd International Conference on DNA Computing and Molecular Programming (DNA 32) (2026)

Abstract
Molecules with designed interactions can serve as substrates for information processing; demonstrated examples include algorithmic self-assembly of DNA tiles and DNA strand displacement reactions. These two well-established paradigms correspond to solid-phase-like behavior, where spatially structured molecular assemblies grow by crystalline attachment, and gas-phase-like behavior, where a dilute mixture of freely diffusing molecules is governed by mass-action kinetics of reactions. A third paradigm, liquid-liquid phase separation, is a fundamental phenomenon in physical and biological systems, giving rise to membraneless compartments that facilitate complex information processing. Recent studies have shown that multicomponent liquid mixtures described by lattice models are analogous to Boltzmann machines and can implement neural computation. Mean-field models have also suggested a connection to Hopfield networks and illustrated complex decision-making during condensation from a reservoir. As an alternative to previous approaches to train liquid interaction energies using backpropagation through a loss function, here we derive "local" learning rules based on contrastive Hebbian learning that may be more biologically and physically plausible. The trained systems demonstrate a range of computational tasks, including associative recall, linear and nonlinear input-output relations, pattern classification, and spatial phase separation. Our work suggests that the computational potential of liquid-phase molecular systems could be unlocked in real physical systems with local learning rules.
Cite as

Yancheng Du, Cameron Chalk, Salvador Buse, Lulu Qian, and Erik Winfree. Contrastive Hebbian Learning for Multicomponent Liquids. In 32nd International Conference on DNA Computing and Molecular Programming (DNA 32). Leibniz International Proceedings in Informatics (LIPIcs), Volume 387, pp. 13:1-13:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{du_et_al:LIPIcs.DNA.32.13,
  author =	{Du, Yancheng and Chalk, Cameron and Buse, Salvador and Qian, Lulu and Winfree, Erik},
  title =	{{Contrastive Hebbian Learning for Multicomponent Liquids}},
  booktitle =	{32nd International Conference on DNA Computing and Molecular Programming (DNA 32)},
  pages =	{13:1--13:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-444-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{387},
  editor =	{Scalise, Dominic and Schweller, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.32.13},
  URN =		{urn:nbn:de:0030-drops-267838},
  doi =		{10.4230/LIPIcs.DNA.32.13},
  annote =	{Keywords: multicomponent liquid, liquid-liquid phase separation, continuous Hopfield network, contrastive Hebbian learning}
}
Document
DOI: 10.4230/LIPIcs.DNA.30.5
Learning and Inference in a Lattice Model of Multicomponent Condensates

Authors: Cameron Chalk, Salvador Buse, Krishna Shrinivas, Arvind Murugan, and Erik Winfree

Published in: LIPIcs, Volume 314, 30th International Conference on DNA Computing and Molecular Programming (DNA 30) (2024)

Abstract
Life is chemical intelligence. What is the source of intelligent behavior in molecular systems? Here we illustrate how, in contrast to the common belief that energy use in non-equilibrium reactions is essential, the detailed balance equilibrium properties of multicomponent liquid interactions are sufficient for sophisticated information processing. Our approach derives from the classical Boltzmann machine model for probabilistic neural networks, inheriting key principles such as representing probability distributions via quadratic energy functions, clamping input variables to infer conditional probability distributions, accommodating omnidirectional computation, and learning energy parameters via a wake phase / sleep phase algorithm that performs gradient descent on the relative entropy with respect to the target distribution. While the cubic lattice model of multicomponent liquids is standard, the behaviors exhibited by the trained molecules capture both previously-observed phenomena such as core-shell condensate architectures as well as novel phenomena such as an analog of Hopfield associative memories that perform recall by contact with a patterned surface. Our final example demonstrates equilibrium classification of MNIST digits. Experimental implementation using DNA nanostar liquids is conceptually straightforward.
Cite as

Cameron Chalk, Salvador Buse, Krishna Shrinivas, Arvind Murugan, and Erik Winfree. Learning and Inference in a Lattice Model of Multicomponent Condensates. In 30th International Conference on DNA Computing and Molecular Programming (DNA 30). Leibniz International Proceedings in Informatics (LIPIcs), Volume 314, pp. 5:1-5:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chalk_et_al:LIPIcs.DNA.30.5,
  author =	{Chalk, Cameron and Buse, Salvador and Shrinivas, Krishna and Murugan, Arvind and Winfree, Erik},
  title =	{{Learning and Inference in a Lattice Model of Multicomponent Condensates}},
  booktitle =	{30th International Conference on DNA Computing and Molecular Programming (DNA 30)},
  pages =	{5:1--5:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-344-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{314},
  editor =	{Seki, Shinnosuke and Stewart, Jaimie Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.30.5},
  URN =		{urn:nbn:de:0030-drops-209330},
  doi =		{10.4230/LIPIcs.DNA.30.5},
  annote =	{Keywords: multicomponent liquid, Boltzmann machine, phase separation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.14
Self-Assembly of Any Shape with Constant Tile Types using High Temperature

Authors: Cameron Chalk, Austin Luchsinger, Robert Schweller, and Tim Wylie

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
Inspired by nature and motivated by a lack of top-down tools for precise nanoscale manufacture, self-assembly is a bottom-up process where simple, unorganized components autonomously combine to form larger more complex structures. Such systems hide rich algorithmic properties - notably, Turing universality - and a self-assembly system can be seen as both the object to be manufactured as well as the machine controlling the manufacturing process. Thus, a benchmark problem in self-assembly is the unique assembly of shapes: to design a set of simple agents which, based on aggregation rules and random movement, self-assemble into a particular shape and nothing else. We use a popular model of self-assembly, the 2-handed or hierarchical tile assembly model, and allow the existence of repulsive forces, which is a well-studied variant. The technique utilizes a finely-tuned temperature (the minimum required affinity required for aggregation of separate complexes). We show that calibrating the temperature and the strength of the aggregation between the tiles, one can encode the shape to be assembled without increasing the number of distinct tile types. Precisely, we show one tile set for which the following holds: for any finite connected shape S, there exists a setting of binding strengths between tiles and a temperature under which the system uniquely assembles S at some scale factor. Our tile system only uses one repulsive glue type and the system is growth-only (it produces no unstable assemblies). The best previous unique shape assembly results in tile assembly models use O(K(S)/(log K(S))) distinct tile types, where K(S) is the Kolmogorov (descriptional) complexity of the shape S.
Cite as

Cameron Chalk, Austin Luchsinger, Robert Schweller, and Tim Wylie. Self-Assembly of Any Shape with Constant Tile Types using High Temperature. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chalk_et_al:LIPIcs.ESA.2018.14,
  author =	{Chalk, Cameron and Luchsinger, Austin and Schweller, Robert and Wylie, Tim},
  title =	{{Self-Assembly of Any Shape with Constant Tile Types using High Temperature}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.14},
  URN =		{urn:nbn:de:0030-drops-94773},
  doi =		{10.4230/LIPIcs.ESA.2018.14},
  annote =	{Keywords: self-assembly, molecular computing, tiling, tile, shapes}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.26
Optimal Staged Self-Assembly of General Shapes

Authors: Cameron Chalk, Eric Martinez, Robert Schweller, Luis Vega, Andrew Winslow, and Tim Wylie

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
We analyze the number of stages, tiles, and bins needed to construct n * n squares and scaled shapes in the staged tile assembly model. In particular, we prove that there exists a staged system with b bins and t tile types assembling an n * n square using O((log n - tb - t log t)/b^2 + log log b/log t) stages and Omega((log n - tb - t log t)/b^2) are necessary for almost all n. For a shape S, we prove O((K(S) - tb - t log t)/b^2 + (log log b)/log t) stages suffice and Omega((K(S) - tb - t log t)/b^2) are necessary for the assembly of a scaled version of S, where K(S) denotes the Kolmogorov complexity of S. Similarly tight bounds are also obtained when more powerful flexible glue functions are permitted. These are the first staged results that hold for all choices of b and t and generalize prior results. The upper bound constructions use a new technique for efficiently converting each both sources of system complexity, namely the tile types and mixing graph, into a "bit string" assembly.
Cite as

Cameron Chalk, Eric Martinez, Robert Schweller, Luis Vega, Andrew Winslow, and Tim Wylie. Optimal Staged Self-Assembly of General Shapes. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chalk_et_al:LIPIcs.ESA.2016.26,
  author =	{Chalk, Cameron and Martinez, Eric and Schweller, Robert and Vega, Luis and Winslow, Andrew and Wylie, Tim},
  title =	{{Optimal Staged Self-Assembly of General Shapes}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{26:1--26:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.26},
  URN =		{urn:nbn:de:0030-drops-63776},
  doi =		{10.4230/LIPIcs.ESA.2016.26},
  annote =	{Keywords: Tile self-assembly, 2HAM, aTAM, DNA computing, biocomputing}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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