Author: asargadmin

Posted on

Discrete Planar Map Matching

Title: Discrete Planar Map Matching

Authors: Bin Fu, Robert Schweller, Tim Wylie

Conference: The 31st Canadian Conference on Computational Geometry (CCCG’19)

Abstract:

Route reconstruction is an important application for Geographic Information Systems (GIS) that rely heavily upon GPS data and other location data from IoT devices. Many of these techniques rely on geometric methods involving the Frechet distance to compare curve similarity. The goal of reconstruction, or map matching, is to find the most similar path within a given graph to a given input curve, which is often only approximate location data. This process can be approximated by sampling the curves and using the discrete Frechet distance. Due to power and coverage constraints, the GPS data itself may be sparse causing improper constraints along the edges during the reconstruction if only the continuous Frechet distance is used. Here, we look at two variations of discrete map matching: one constraining the walk length and the other limiting the number of vertices visited in the graph. We give an efficient algorithm to solve one and prove the other is NP-complete and the minimization version is APX-hard while also giving a parameterized algorithm to solve the problem.

Posted on

Paper accepted at CCCG 2019

We have just had a paper accepted to the 31st Canadian Conference on Computational Geometry. The paper is titled “Discrete Planar Map Matching” authored by Bin Fu, Robert Schweller, and Tim Wylie. For more information visit the publication page.

Posted on

Summer REU Students

This summer the NSF has granted us funding for two REU (Research Experience for Undergraduates) students. David Caballero and Tim Gomez will be granted these REU stipends as they continue their great work over the summer months.

Posted on

Paper accepted to ICALP

Our paper “Covert Computation in Self-Assembled Circuits” was accepted to the 46th International Colloquium on Automata, Languages, and Programming (ICALP ’19), which is a top tier conference. The authors on the paper are Angel Cantu, Austin Luchsinger, Robert Schweller, and Tim Wylie. For more information about the paper, visit the post.

Posted on

Covert Computation in Self-Assembled Circuits

Title: Covert Computation in Self-Assembled Circuits

Authors: Angel Cantu, Austin Luchsinger, Robert Schweller, and Tim Wylie

Conference: The 46th International Colloquium on Automata, Languages, and Programming (ICALP ’19)

Abstract:

Traditionally, computation within self-assembly models is hard to conceal because the self-assembly process generates a crystalline assembly whose computational history is inherently part of the structure itself. With no way to remove information from the computation, this computational model offers a unique problem: how can computational input and computation be hidden while still computing and reporting the final output? Designing such systems is inherently motivated by privacy concerns in biomedical computing and applications in cryptography.

In this paper we propose the problem of performing “covert computation” within tile self-assembly that seeks to design self-assembly systems that “conceal” both the input and computational history of performed computations. We achieve these results within the growth-only restricted abstract tile assembly model (aTAM) with positive and negative interactions. We show that general-case covert computation is possible by implementing a set of basic covert logic gates capable of simulating any circuit (functionally complete). To further motivate the study of covert computation, we apply our new framework to resolve an outstanding complexity question; we use our covert circuitry to show that the unique assembly verification problem within the growth-only aTAM with negative interactions is coNP-complete.

Posted on

Nearly Constant Tile Complexity for any Shape in Two-Handed Tile Assembly

Title: Nearly Constant Tile Complexity for any Shape in Two-Handed Tile Assembly

Authors: Robert Schweller, Andrew Winslow, and Tim Wylie

Journal: Algorithmica, 2019

Abstract:

Tile self-assembly is a well-studied theoretical model of geometric computation based on nanoscale DNA-based molecular systems. Here, we study the two-handed tile self-assembly model or 2HAM at general temperatures, in contrast with prior study limited to small constant temperatures, leading to surprising results. We obtain constructions at larger (i.e., hotter) temperatures that disprove prior conjectures and break well-known bounds for low-temperature systems via new methods of temperature-encoded information.

In particular, for all $n \in \mathbb{N}$, we assemble $n \times n$ squares using $O(2^{\log^*{n}})$ tile types, thus breaking the well-known information theoretic lower bound of Rothemund and Winfree. Using this construction, we then show how to use the temperature to encode general shapes and construct them at scale with $O(2^{\log^*{K}})$ tiles, where $K$ denotes the Kolmogorov complexity of the target shape. Following, we refute a long-held conjecture by showing how to use temperature to construct $n \times O(1)$ rectangles using only $O(\log{n}/\log\log{n})$ tile types. We also give two small systems to generate nanorulers of varying length based solely on varying the system temperature.

These results constitute the first real demonstration of the power of high temperature systems for tile assembly in the 2HAM. This leads to several directions for future explorations which we discuss in the conclusion.

Posted on

Single-Step Shape Constructors

Here are some videos from our latest single-step work!

3X3 K-Colored Shape

3X3 K-Colored Pattern

4X4 K-Colored Pattern

4X4 K-Colored Shape