Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userIntrinsic universality and the computational power of self-assembly
107
0
0.0
(
0
)
Added by
EPTCS
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Authors
Damien Woods
Ask ChatGPT about the research
No Arabic abstract
This short survey of recent work in tile self-assembly discusses the use of simulation to classify and separate the computational and expressive power of self-assembly models. The journey begins with the result that there is a single universal tile set that, with proper initialization and scaling, simulates any tile assembly system. This universal tile set exhibits something stronger than Turing universality: it captures the geometry and dynamics of any simulated system. From there we find that there is no such tile set in the noncooperative, or temperature 1, model, proving it weaker than the full tile assembly model. In the two-handed or hierarchal model, where large assemblies can bind together on one step, we encounter an infinite set, of infinite hierarchies, each with strictly increasing simulation power. Towards the end of our trip, we find one tile to rule them all: a single rotatable flipable polygonal tile that can simulate any tile assembly system. It seems this could be the beginning of a much longer journey, so directions for future work are suggested.
rate research
Read More
The classic Ham-Sandwich theorem states that for any $d$ measurable sets in $mathbb{R}^d$, there is a hyperplane that bisects them simultaneously. An extension by Barany, Hubard, and Jeronimo [DCG 2008] states that if the sets are convex and emph{well-separated}, then for any given $alpha_1, dots, alpha_d in [0, 1]$, there is a unique oriented hyperplane that cuts off a respective fraction $alpha_1, dots, alpha_d$ from each set. Steiger and Zhao [DCG 2010] proved a discrete analogue of this theorem, which we call the emph{$alpha$-Ham-Sandwich theorem}. They gave an algorithm to find the hyperplane in time $O(n (log n)^{d-3})$, where $n$ is the total number of input points. The computational complexity of this search problem in high dimensions is open, quite unlike the complexity of the Ham-Sandwich problem, which is now known to be PPA-complete (Filos-Ratsikas and Goldberg [STOC 2019]). Recently, Fearley, Gordon, Mehta, and Savani [ICALP 2019] introduced a new sub-class of CLS (Continuous Local Search) called emph{Unique End-of-Potential Line} (UEOPL). This class captures problems in CLS that have unique solutions. We show that for the $alpha$-Ham-Sandwich theorem, the search problem of finding the dividing hyperplane lies in UEOPL. This gives the first non-trivial containment of the problem in a complexity class and places it in the company of classic search problems such as finding the fixed point of a contraction map, the unique sink orientation problem and the $P$-matrix linear complementarity problem.
In a nutshell, we show that polynomials and nested polytopes are topological, algebraic and algorithmically equivalent. Given two polytops $Asubseteq B$ and a number $k$, the Nested Polytope Problem (NPP) asks, if there exists a polytope $X$ on $k$ vertices such that $Asubseteq X subseteq B$. The polytope $A$ is given by a set of vertices and the polytope $B$ is given by the defining hyperplanes. We show a universality theorem for NPP. Given an instance $I$ of the NPP, we define the solutions set of $I$ as $$ V(I) = {(x_1,ldots,x_k)in mathbb{R}^{kcdot n} : Asubseteq text{conv}(x_1,ldots,x_k) subseteq B}.$$ As there are many symmetries, induced by permutations of the vertices, we will consider the emph{normalized} solution space $V(I)$. Let $F$ be a finite set of polynomials, with bounded solution space. Then there is an instance $I$ of the NPP, which has a rationally-equivalent normalized solution space $V(I)$. Two sets $V$ and $W$ are rationally equivalent if there exists a homeomorphism $f : V rightarrow W$ such that both $f$ and $f^{-1}$ are given by rational functions. A function $f:Vrightarrow W$ is a homeomorphism, if it is continuous, invertible and its inverse is continuous as well. As a corollary, we show that NPP is $exists mathbb{R}$-complete. This implies that unless $exists mathbb{R} =$ NP, the NPP is not contained in the complexity class NP. Note that those results already follow from a recent paper by Shitov. Our proof is geometric and arguably easier.
Ailon et al. [SICOMP11] proposed self-improving algorithms for sorting and Delaunay triangulation (DT) when the input instances $x_1,cdots,x_n$ follow some unknown emph{product distribution}. That is, $x_i$ comes from a fixed unknown distribution $mathsf{D}_i$, and the $x_i$s are drawn independently. After spending $O(n^{1+varepsilon})$ time in a learning phase, the subsequent expected running time is $O((n+ H)/varepsilon)$, where $H in {H_mathrm{S},H_mathrm{DT}}$, and $H_mathrm{S}$ and $H_mathrm{DT}$ are the entropies of the distributions of the sorting and DT output, respectively. In this paper, we allow dependence among the $x_i$s under the emph{group product distribution}. There is a hidden partition of $[1,n]$ into groups; the $x_i$s in the $k$-th group are fixed unknown functions of the same hidden variable $u_k$; and the $u_k$s are drawn from an unknown product distribution. We describe self-improving algorithms for sorting and DT under this model when the functions that map $u_k$ to $x_i$s are well-behaved. After an $O(mathrm{poly}(n))$-time training phase, we achieve $O(n + H_mathrm{S})$ and $O(nalpha(n) + H_mathrm{DT})$ expected running times for sorting and DT, respectively, where $alpha(cdot)$ is the inverse Ackermann function.
We prove that by successively combining subassemblies, we can achieve sublinear construction times for staged assembly of micro-scale objects from a large number of tiny particles, for vast classes of shapes; this is a significant advance in the context of programmable matter and self-assembly for building high-yield micro-factories.The underlying model has particles moving under the influence of uniform external forces until they hit an obstacle; particles bond when forced together with a compatible particle. Previous work considered sequential composition of objects, resulting in construction time that is linear in the number N of particles, which is inefficient for large N. Our progress implies critical speedup for constructible shapes; for convex polyominoes, even a constant construction time is possible. We also show that our construction process can be used for pipelining, resulting in an amortized constant production time.
In this paper, we study the quantity of computational resources (state machine states and/or probabilistic transition precision) needed to solve specific problems in a single hop network where nodes communicate using only beeps. We begin by focusing on randomized leader election. We prove a lower bound on the states required to solve this problem with a given error bound, probability precision, and (when relevant) network size lower bound. We then show the bound tight with a matching upper bound. Noting that our optimal upper bound is slow, we describe two faster algorithms that trade some state optimality to gain efficiency. We then turn our attention to more general classes of problems by proving that once you have enough states to solve leader election with a given error bound, you have (within constant factors) enough states to simulate correctly, with this same error bound, a logspace TM with a constant number of unary input tapes: allowing you to solve a large and expressive set of problems. These results identify a key simplicity threshold beyond which useful distributed computation is possible in the beeping model.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
