Fast Computation in Algorithmic Self-Assembly

Identify a computational problem you wish to study in the context of tile self-assembly. Design an aTAM system that solves your problem (computes the corresponding function) according to the formulation provided in Fast Arithmetic in Algorithmic Self-Assembly. Analyze the worst case or average case run-time of your solution and compare to the best known run time within the standard model of computation.

To receive credit, your work must be new, i.e., no one has previously solved your problem in this model, or has not solved it as fast.

Turn in: Write your solution as a LaTex document with a theorem statement and proof.

Collaboration: You may work in groups of size up to 3 coauthors.

Evaluation: Your result will be evaluated on it’s depth, novelty, and the quality of the writup. Your goal should be to produce a surprising and novel result with a complete and correct proof.