2026-07-23T08:35:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17948 2024-03-06T11:00:30Z ddc:004 open_access

Covert Computation in the Abstract Tile-Assembly Model Alaniz, Robert M. Caballero, David Gomez, Timothy Grizzell, Elise Rodriguez, Andrew Schweller, Robert Wylie, Tim self-assembly covert computation atam There have been many advances in molecular computation that offer benefits such as targeted drug delivery, nanoscale mapping, and improved classification of nanoscale organisms. This power led to recent work exploring privacy in the computation, specifically, covert computation in self-assembling circuits. Here, we prove several important results related to the concept of a hidden computation in the most well-known model of self-assembly, the Abstract Tile-Assembly Model (aTAM). We show that in 2D, surprisingly, the model is capable of covert computation, but only with an exponential-sized assembly. We also show that the model is capable of covert computation with polynomial-sized assemblies with only one step in the third dimension (just-barely 3D). Finally, we investigate types of functions that can be covertly computed as members of P/Poly. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Robert M. Alaniz and David Caballero and Timothy Gomez and Elise Grizzell and Andrew Rodriguez and Robert Schweller and Tim Wylie 2023 Is Part Of LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2023.12 urn:nbn:de:0030-drops-179482 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.12 eng https://creativecommons.org/licenses/by/4.0/legalcode