Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Bruno Durand:

TR08-030 | 16th November 2007
Bruno Durand, Alexander Shen, Andrei Romashchenko

Fixed Point and Aperiodic Tilings

An aperiodic tile set was first constructed by R.Berger while
proving the undecidability of the domino problem. It turned out
that aperiodic tile sets appear in many topics ranging from
logic (the Entscheidungsproblem) to physics (quasicrystals)

We present a new construction of an aperiodic tile set. The
flexibility of this ... more >>>

TR01-087 | 29th October 2001
Bruno Durand, Alexander Shen, Nikolay Vereshchagin

Descriptive complexity of computable sequences

We study different notions of descriptive complexity of
computable sequences. Our main result states that if for almost all
n the Kolmogorov complexity of the n-prefix of an infinite
binary sequence x conditional to n
is less than m then there is a program of length
m^2+O(1) that for ... more >>>

ISSN 1433-8092 | Imprint