Date: Thursday, March 31, 2011.
Place: Mengminwei building, room 109, Nanjing University (main campus)
11:00 am - 11:50 am
Speaker: Liang Yu (Nanjing Univ)
Title: Characterizing nonstandard randomness notions via Martin-Lof randomness
Abstract: We introduces two methods to characterize nonstandard
randomness notions via Martin-Lof randomness. By applying these
methods, we investigate 0'-Schnorr randomness.
Liang Yu is a professor at the Institute of Mathematical Science
of Nanjing University. His research interests include computability
theory, algorithmic randomness theory and set theory.
2:00 pm - 2:50 pm
Speaker: Ke Yi (HKUST)
Title: Tracking Distributed Data
Consider a model where k players each receive a sequence of elements
over time, and they communicate with the goal of tracking some
function of all the elements received so far continuously. This
distributed tracking model naturally generalize both the multi-party
communication model and the data stream model, and abstracts many
tracking problems in distributed systems. Though extensively studied
in the database and networking communities, this model has attracted
theoreticians only since recently. This talk will first present an
overview of results in this area, and then dive into a few selected
problems: tracking sum, frequent items, and random sampling.
Ke Yi received his B.E. from Tsinghua University and Ph.D. from Duke
University, in 2001 and 2006 respectively, both in computer science.
After spending one year at AT&T Labs as a researcher, he has been an
Assistant Professor in the Department of Computer Science and
Engineering at Hong Kong University of Science and Technology since
2007. His research interests include algorithms, data structures, and
3:00 pm - 4:00 pm
Speaker: Kord Eickmeyer (Humboldt University of Berlin)
Title: Randomisation and Derandomisation in Descriptive Complexity Theory
We study randomised complexity classes, in particular randomised AC^0
under various uniformity conditions, using tools from descriptive
complexity theory. To this end, we introduce randomised logics and study
their expressive power.
Using tools from finite model theory, we were able to show that
randomised first-order logic provably gains expressive power, even on
structures with an addition relation. In complexity theory terms, this
implies that under a certain strict uniformity condition, BPAC^0 cannot
Furthermore, we show that on certain restricted classes of structures,
randomised first-order logic can in fact be derandomised. The proof is
of interest as it deviates from the standard schema of constructing a
pseudorandom generator from hard functions.
Kord Eickmeyer studied mathematics and computer science in Luebeck,
Freiburg and Cambridge (UK). After completing his Diplom (M.Sc.-equiv)
in mathematics we went to Japan for eighteen months, nine of which he
spent as an intern in Hirokazu Anai's computer algebra group at Fujitsu
Research. Since 2007 he has been a PhD-student at Humboldt-University
Berlin, supervised by Martin Grohe.