Seminar: Clairvoyant Embedding in One Dimensions

Dr. Peter Gacs (Boston University)

Wednesday, March 12, 2014, 10:30AM-12:00PM, EV 3.309

Abstract

Let v, w be infinite 0-1 sequences, and m a positive integer. We say that w is m-embeddable in v, if there exists an increasing sequence n_{i} of integers with n_{0}=0, such that 0< n_{i} - n_{i-1} < m, w(i) = v(n_i) for all i > 0. Let X and Y be independent coin-tossing sequences. We will show that there is an m with the property that Y is m-embeddable into X with positive probability. This answers a question that was open for a while. The proof generalizes somewhat the multi-scale method of an earlier paper of the author on dependent percolation.

Bio

Before coming to Boston University, Dr. Peter Gacs studied in Budapest, worked at the Hungarian Academy of Science with trips to Moscow, obtained PhD in Frankfurt, did postdoc work at Stanford, and taught in Rochester. Professor Gacs has worked on problems derived from information theory (classical, and algorithmic) and reliable computation. With Ahlswede and Körner, he wrote some of the earliest papers of multi-user information theory. In algorithmic information theory (Kolmogorov complexity), Gacs also had some part in developing the fundamental results (earlier with Levin, later with Vitányi and others). In reliable computation, his main contributions are to the probabilistic cellular automaton model: in some sense the most natural one, but mathematically difficult. He has been the principal investigator of several NSF grants, and is an external member of the Hungarian Academy of Sciences.