***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Xiaoyu He (Princeton)

Thursday September 16th, 3:00 in Fine Hall 224.

Title: Long common subsequences between bitstrings

Abstract: A binary code of positive rate is a subset of {0,1}^n with size
exponentially large in n. In any binary code of positive rate, one can find two
codewords sharing the same majority bit and thus a common subsequence of length
at least n/2. Surprisingly, whether this trivial constant 1/2 could be improved
was a longstanding open problem in coding theory, and we solve it in a
strengthened form. That is, we show that there exist A, c > 0 such that among
any 2^{(log n)^A} bitstrings of length n, some two have a common subsequence of
length at least (1/2 + c)n. In the language of coding theory, this means that
the zero-rate threshold for coding against adversarial bit-deletion is strictly
less than 1/2.

The main idea of the proof is to develop a classification system for bitstrings
according to their "oscillation patterns," very roughly analogous to Fourier
phases; one key ingredient of this classification is a new entropy-increment
variant of the string regularity lemma of Axenovitch, Person, and Puzynina.

Joint work with Venkatesan Guruswami and Ray Li. 

		----------------------------------

Next week: Swee Hong Chan

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)