Mathematical Sciences Seminar - k-Radius Sequences
When:
—
Venue:
Birkbeck Main Building, Malet Street
No booking required
(Joint work with James McKee.)
A k-radius sequence is a finite sequence over an alphabet of size n, with the property that every two alphabet symbols occur within a distance of k of each other somewhere in the sequence. We write fk(n) for the shortest n-ary k-radius sequence. Jaromczyk and Lonc introduced this concept in 2004: they were interested in designing a (first-in first-out) caching strategy for computations involving pairs of large data objects such as medical images.
In this talk, I will start by talking a little about the caching application. I'll then show how to prove that fk(n) grows like (1/k)(n(n-1)/2) when k is fixed and n goes to infinity.
This talk is based on the following papers:
S.R. Blackburn, 'The existence of k-radius sequences'. See http://arxiv.org/abs/1101.1172
S.R. Blackburn and J.F. McKee, 'Constructing k-radius sequences', Mathematics of Computation, to appear. See http://arxiv.org/abs/1006.5812
Contact name:
Department of Economics, Mathematics and Statistics