Seminar on March 31, 2011.

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

be derandomised.

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.