Computational Aspects (May 30 - June 3)

Schedule

Afternoons are devoted to talks and free discussions.You can already propose a talk by email.

Lectures

Igor Pak: Complexity of finite tilings

Can you tile a given finite region in the plane with tiles from a given finite set? If yes, how many such tilings are there? These questions depend heavily on the set of tiles and sometimes reflect the most difficult problems in complexity theory. There is a very thin line between tiling problems which have polynomial time algorithms and those which are universally hard. We discuss where this line lies, present both positive and negative results and state some open problems.

Andreï Romashchenko: Embedding computations in tilings Slides0 Slides1 Sldes2 Slides3

In this course we will discuss several computational ideas that are used in constructions of tilings (subshifts of finite type). Surprisingly, these inherently algorithmic techniques help to solve several problems that look purely combinatorial, without any computational flavor. We shall in particular explain the method of fixed-point tilings (based on self-referential programs) and the technique of embedding arithmetic of real numbers (represented by their Beatty sequences).

Damien Woods: Theory and practice of algorithmic self-assembly

The field of algorithmic self-assembly is concerned with the theory and practice of having molecules grow complicated structures in an autonomous bottom-up fashion. Theoretical work is concerned with characterising the computational expressivity of self-assembly models. Practice is concerned with using molecules, such as DNA, to implement algorithmic self-assembly programs in the wet-lab. In between these two extremes we have a computer-assisted compilation process to go from abstract tile-based programs, through to DNA sequence design, all the way down to mixing hundreds of interacting molecules with some water in a test tube and imaging them to see the result.

The presentation will cover all of these topics. First, there will be an introduction to self-assembly models and some basic computational results. Attendees will then be given a brief sense of how one goes about designing and implementing self-assembling DNA tiles in the wet lab, and will see some of the latest results on that topic. Finally, we will look more deeply into the theory of algorithmic self-assembly in order to understand what are the capabilities and limitations of these models. We will define a notion of simulation between tile assembly models which will be used to contrast these models and to establish the existence of so-called intrinsically universal sets of molecules that can, in an accurate sense, act like any instance of a model. A really fun part of this will be exploring proof techniques that can be used to show when one model is of equivalent power, or strictly more powerful, than another.

Afternoon talks

May 31
T.  Monteil The asymptotic genus of a tile set  Slides
L. Liao Fuglede’s conjecture on Q_p Slides
J.  Cassaigne  Even and odd shift


June 1
M. Rao Aperiodic tile set with 11 tiles Slides
C. Goodman-Strauss 50.625  new simple aperiodic sets of tiles Slides
S. Barbieri SFT on groups

Open problems
N. Macé Introduction to electron dynamics and tilings with local rules with arrows that form irrotational fields
D. Woods D. Regnault Self-avoiding paths in Z^2
O. Parshina Tilings of finite abelian groups and complete rank  characteristic vectors

June 2
M. Schraudner Complexity and effectiveness
A. Schen Fixed-point and subaction Slides
N. Chandgotia Mixing  properties of Hom-shifts Notes

Open problems
T. Fernique Self-similarity  and local rules
C. Goodman-Strauss Self-assembly
P. Guillon Determinism and expansiveness Slides

June 3
I. Ivanov-Belov Burnside’s groups and tilings Slides