View source for Speed of Assembly in the 2HAM

Since the 2HAM allows for assemblies to begin forming in parallel and then to combine in pairs, it would seem that perhaps this would allow for sublinear assembly times.  However, Chen and Doty <ref name=CheDot12 /> developed a physically inspired timing model for the 2HAM (referred to there as the ''Hierarchical aTAM'') and showed that it is impossible to build shapes of diameter $n$ in time less than $\Omega(n)$ in deterministic systems under that timing model.  Nonetheless, they then exhibited a nondeterministic system which can assemble an ''n × n' '' rectangle (where ''n > n' '') in time $O(n^{4/5}\log n)$, breaking the linear-time lower bound (which applies not only to deterministic 2HAM systems, but also to seeded aTAM systems as mentioned in [[Speed of assembly]]).
==References==
<references>

<ref name =CheDot12><bibtex>
@inproceedings{CheDot12,
  author = {Ho-Lin Chen and David Doty},
  title = {Parallelism and Time in Hierarchical Self-Assembly},
  booktitle =  {SODA 2012: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms},
  publisher =  {SIAM},
  year =    {2012},
  pages = {1163--1182},
}
</bibtex></ref>

</references>

[[Category: 2HAM Results]]