{"id":53,"date":"2017-10-08T17:17:25","date_gmt":"2017-10-08T17:17:25","guid":{"rendered":"https:\/\/asarg.hackresearch.com\/main\/?page_id=53"},"modified":"2017-10-15T06:40:23","modified_gmt":"2017-10-15T06:40:23","slug":"publications","status":"publish","type":"page","link":"https:\/\/asarg.hackresearch.com\/main\/publications\/","title":{"rendered":"Publications"},"content":{"rendered":"

\n\n\t
\n\tnaturalcomputing<\/a>\nnc<\/a>\nconference<\/a>\nesa<\/a>\nicalp<\/a>\nalgorithmica<\/a>\ncccg<\/a>\n2021<\/a>\n2020<\/a>\n2018<\/a>\n2019<\/a>\narxiv<\/a>\nPublications<\/a>\ndna<\/a>\njournal<\/a>\njcdcggg<\/a>\nsoda<\/a>\n2015<\/a>\n2017<\/a>\n2016<\/a> <\/div>\n<\/div>\n<\/section>
\n
\r\n
\r\n \r\n\t\tOptimal Staged Self-Assembly of General Shapes\t<\/a>\r\n\t<\/div>\r\n
\r\n\t
\r\n\t\t

Title: Optimal Staged Self-Assembly of General Shapes
\nAuthors: Cameron Chalk, Eric Martinez, Robert Schweller, Luis Vega, Andrew Winslow, Tim Wylie
\nAbstract:
\nWe analyze the number of tile types t, bins b, and stages necessary to assemble \\(n \\times n\\) squares and scaled shapes in the staged tile assembly model. For \\(n \\times n\\) squares, we prove \\(\\mathcal {O}\\left( \\frac{\\log {n} – tb – t\\log t}{b^2} + \\frac{\\log \\log b}{\\log t}\\right) \\) stages suffice and \\(\\varOmega \\left( \\frac{\\log {n} – tb – t\\log t}{b^2}\\right) \\) are necessary for almost all n. For shapes S with Kolmogorov complexity K(S), we prove \\(\\mathcal {O}\\left( \\frac{K(S) – tb – t\\log t}{b^2} + \\frac{\\log \\log b}{\\log t}\\right) \\) stages suffice and \\(\\varOmega \\left( \\frac{K(S) – tb – t\\log t}{b^2}\\right) \\) are necessary to assemble a scaled version of S, for almost all S. We obtain similarly tight bounds when the more powerful flexible glues are permitted.
\nPublished: Arxiv, European Symposium on Algorithms (ESA’16), Algorithmica<\/p>\n

URL: https:\/\/link.springer.com\/article\/10.1007\/s00453-017-0318-0<\/p>\n

Journal Citation: Algorithmica, 80(4), 1383-1409, 2018. <\/p>\n

Bibtex:
\n@article{CMSVWW:2018:Algorithmica,
\n author=”Chalk, Cameron and Martinez, Eric and Schweller, Robert and Vega, Luis and Winslow, Andrew and Wylie, Tim”,
\n title=”Optimal Staged Self-Assembly of General Shapes”,
\n journal=”Algorithmica”,
\n year=”2018″,
\n month=”Apr”,
\n day=”01″,
\n volume=”80″,
\n number=”4″,
\n pages=”1383–1409″,
\n issn=”1432-0541″,
\n doi=”10.1007\/s00453-017-0318-0″,
\n url=”https:\/\/doi.org\/10.1007\/s00453-017-0318-0″
\n}<\/p>\n

Conference Citation: Proceedings of the 24th European Symposium of Algorithms (ESA’16), 57, 26:1–26:17, 2016. <\/p>\n<\/div>\n

2015<\/a>, 2016<\/a>, 2017<\/a>, 2018<\/a>, algorithmica<\/a>, arxiv<\/a>, conference<\/a>, esa<\/a>, journal<\/a>, publications<\/a><\/span><\/div>\t<\/div>\r\n<\/div><\/div>\n
\r\n
\r\n \r\n\t\tConcentration Independent Random Number Generation in Tile Self-Assembly\t<\/a>\r\n\t<\/div>\r\n
\r\n\t
\r\n\t\t

Title: Concentration Independent Random Number Generation in Tile Self-Assembly
\nAuthors:
\nIn this paper we introduce the robust random number generation problem where the goal is to design an abstract tile assembly system (aTAM system) whose terminal assemblies can be split into n partitions such that a resulting assembly of the system lies within each partition with probability 1\/n , regardless of the relative concentration assignment of the tile types in the system. First, we show this is possible for n=2n=2 (a robust fair coin flip ) within the aTAM, and that such systems guarantee a worst case O(1)O(1) space usage. We accompany our primary construction with variants that show trade-offs in space complexity, initial seed size, temperature, tile complexity, bias, and extensibility, and also prove some negative results. As an application, we combine our coin-flip system with a result of Chandran, Gopalkrishnan, and Reif to show that for any positive integer n , there exists a O(log\u2061n)O(log\u2061n) tile system that assembles a constant-width linear assembly of expected length n for any concentration assignment. We then extend our robust fair coin flip result to solve the problem of robust random number generation in the aTAM for all n. Two variants of robust random bit generation solutions are presented: an unbounded space solution and a bounded space solution which incurs a small bias. Further, we consider the harder scenario where tile concentrations change arbitrarily at each assembly step and show that while this is not possible in the aTAM, the problem can be solved by exotic tile assembly models from the literature.<\/p>\n

Bibtex:
\nPDF:
\nURL:<\/p>\n<\/div>\n

2015<\/a>, 2016<\/a>, 2017<\/a>, arxiv<\/a>, conference<\/a>, dna<\/a>, journal<\/a>, publications<\/a>, tcs<\/a><\/span><\/div>\t<\/div>\r\n<\/div><\/div>\n
\r\n
\r\n \r\n\t\tUniversal Shape Replicators via Self-Assembly with Attractive and Repulsive Forces\t<\/a>\r\n\t<\/div>\r\n
\r\n\t
\r\n\t\t

Title:
\nAuthors:Cameron Chalk, Erik D. Demaine, Martin L. Demaine, Eric Martinez, Robert Schweller, Luis Vega, and Tim Wylie.
\nAbstract:<\/p>\n

citation:
\nIn Proc. of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA’17), 2017. <\/p>\n<\/div>\n

2016<\/a>, 2017<\/a>, arxiv<\/a>, conference<\/a>, publications<\/a>, soda<\/a><\/span><\/div>\t<\/div>\r\n<\/div><\/div>\n
\r\n
\r\n \r\n\t\tComplexities for High-Temperature Two-Handed Tile Self-Assembly\t<\/a>\r\n\t<\/div>\r\n
\r\n\t
\r\n\t\t

Title: Complexities for High-Temperature Two-Handed Tile Self-Assembly.
\nAuthors: Robert Schweller, Andrew Winslow, and Tim Wylie.
\nAbstract: <\/p>\n

In Proc. of the 23rd Inter. Conf. on DNA Computing and Molecular Programming (DNA’17), 2017. <\/p>\n<\/div>\n

2017<\/a>, conference<\/a>, dna<\/a>, publications<\/a><\/span><\/div>\t<\/div>\r\n<\/div><\/div>\n
\r\n
\r\n \r\n\t\tVerification in Staged Tile Self-Assembly\t<\/a>\r\n\t<\/div>\r\n
\r\n\t
\r\n\t\t

Verification in Staged Tile Self-Assembly.
\nRobert Schweller, Andrew Winslow, and Tim Wylie.
\nIn Proc. of the 16th Inter. Conf. on Unconventional Computation and Natural Computation (UCNC’17), 2017. <\/p>\n<\/div>\n

2017<\/a>, arxiv<\/a>, conference<\/a>, publications<\/a>, ucnc<\/a><\/span><\/div>\t<\/div>\r\n<\/div><\/div>\n
\r\n
\r\n \r\n\t\tSelf-Assembly of Shapes at Constant Scale using Repulsive Forces\t<\/a>\r\n\t<\/div>\r\n
\r\n\t
\r\n\t\t

Self-Assembly of Shapes at Constant Scale using Repulsive Forces.
\nAustin Luchsinger, Robert Schweller, and Tim Wylie. In Natural Computing. 2018.<\/p>\n

Link: https:\/\/link.springer.com\/article\/10.1007\/s11047-018-9707-9<\/a><\/p>\n

<\/a><\/p>\n

Abstract:<\/p>\n

Bibtex:<\/p>\n

 <\/p>\n

Conference Version:<\/p>\n

Self-Assembly of Shapes at Constant Scale using Repulsive Forces.
\nAustin Luchsinger, Robert Schweller, and Tim Wylie.
\nIn Proc. of the 16th Inter. Conf. on Unconventional Computation and Natural Computation (UCNC’17), 2017.<\/p>\n

Abstract:<\/p>\n

Bibtex:<\/p>\n<\/div>\n

2017<\/a>, 2018<\/a>, conference<\/a>, journal<\/a>, naturalcomputing<\/a>, nc<\/a>, publications<\/a>, ucnc<\/a><\/span><\/div>\t<\/div>\r\n<\/div><\/div>\n
\r\n
\r\n \r\n\t\tOptimal Staged Self-Assembly of Linear Assemblies\t<\/a>\r\n\t<\/div>\r\n
\r\n\t
\r\n\t\t

Title: Optimal Staged Self-Assembly of Linear Assemblies
\nAuthors: Cameron Chalk, Eric Martinez, Robert Schweller, Luis Vega, Andrew Winslow, Tim Wylie
\nAbstract:
\nWe analyze the complexity of building linear assemblies, sets of linear assemblies, and $\\mathcal{O}(1)$-scale general shapes in the staged tile assembly model. For systems with at most $b$ bins and $t$ tile types, we prove that the minimum number of stages to uniquely assemble a $1 \\times n$ \\emph{line} is $\\Theta(\\log_t{n} + \\log_b{\\frac{n}{t}} + 1)$. Generalizing to $\\BO{1} \\times n$ lines, we prove the minimum number of stages is $\\BO{\\frac{\\log{n} – tb – t\\log t}{b^2} + \\frac{\\log \\log b}{\\log t}}$ and $\\Omega(\\frac{\\log{n} – tb – t\\log t}{b^2})$. We also obtain similar upper and lower bounds in a model permitting \\emph{flexible glues} using non-diagonal glue functions.<\/p>\n

Next, we consider assembling sets of lines and general shapes using $t = \\BO{1}$ tile types. We prove that the minimum number of stages needed to assemble a set of $k$ lines of size at most $\\BO{1} \\times n$ is $\\BO{\\frac{k\\log n}{b^2}+\\frac{k\\sqrt{\\log n}}{b}+\\log\\log n}$ and $\\Omega(\\frac{k\\log n}{b^2})$. In the case that $b = \\BO{\\sqrt{k}}$, the minimum number of stages is $\\Theta(\\log{n})$. The upper bound in this special case is then used to assemble “hefty” shapes of at least logarithmic edge-length-to-edge-count ratio at $\\BO{1}$-scale using $\\BO{\\sqrt{k}}$ bins and optimal $\\BO{\\log{n}}$ stages.<\/p>\n

Citation: Proc. of 17th Inter. Conf. on Unconventional Computation and Natural Computation (UCNC’18)
\nBibtex:<\/p>\n<\/div>\n

2018<\/a>, conference<\/a>, publications<\/a>, ucnc<\/a><\/span><\/div>\t<\/div>\r\n<\/div><\/div>\n
\r\n
\r\n \r\n\t\tFreezing Simulates Non-freezing Tile Automata\t<\/a>\r\n\t<\/div>\r\n
\r\n\t
\r\n\t\t

Title: Freezing Simulates Non-freezing Tile Automata<\/p>\n

Authors: Cameron Chalk, Austin Luchsinger, Eric Martinez, Robert Schweller, Andrew Winslow, and Tim Wylie
\nAbstract:<\/p>\n

Citation: Proc. of 24th Inter. Conf. on DNA Computing and Molecular Programming (DNA’18)
\nBibtex:
\nPDF:<\/p>\n<\/div>\n

2018<\/a>, conference<\/a>, dna<\/a>, publications<\/a><\/span><\/div>\t<\/div>\r\n<\/div><\/div>\n
\r\n
\r\n \r\n\t\tSelf-Assembly of Any Shape with Constant Tile Types using High Temperature\t<\/a>\r\n\t<\/div>\r\n
\r\n\t
\r\n\t\t

Title: Self-Assembly of Any Shape with Constant Tile Types using High Temperature<\/p>\n

Authors: Cameron Chalk, Austin Luchsinger, Robert Schweller, and Tim Wylie
\nAbstract:<\/p>\n

Citation: Proc. of 26th European Symposium of Algorithms (ESA’18)
\nBibtex:
\nPDF:<\/p>\n<\/div>\n

2018<\/a>, conference<\/a>, esa<\/a>, publications<\/a><\/span><\/div>\t<\/div>\r\n<\/div><\/div>\n
\r\n
\r\n \r\n\t\tTile Pattern-Building Games on a Grid are PSPACE-complete\t<\/a>\r\n\t<\/div>\r\n
\r\n\t
\r\n\t\t
Tile Pattern-Building Games on a Grid are PSPACE-complete (Short Abstract)<\/strong>.<\/div>\n

Angel A. Cantu, Arturo Gonzalez, Cesar Lozano, Austin Luchsinger, Eduardo Medina, Fernando Martinez, Arnoldo Ramirez, and Tim Wylie.
\nThe 21st Japan Conference on Discrete and Computational Geometry, Graphs, and Games<\/em> (JCDCG^3’18), 2018.<\/p>\n

Abstract: In this paper, we investigate a certain class of tile-based pattern games through a simplified version of a recent game titled Nonads. We prove that Nonads is PSPACE-complete with a reduction from bounded 2-player constraint logic (Bounded 2CL) even when both players share the same target and there is only one type of playable tile. This has application to any grid-based pattern building game.<\/p>\n

Bibtex:<\/p>\n<\/div>\n

2018<\/a>, conference<\/a>, jcdcggg<\/a>, publications<\/a><\/span><\/div>\t<\/div>\r\n<\/div><\/div><\/div><\/div><\/div>\n