本周四3月31日将举办一场理论计算机科学的workshop。有三个学术报告，报告人：南京大
学数学系喻良，香港科技大学易珂，德国Humboldt-University at Berlin的Kord
Eickmeyer。 此次workshop将有上海交大、复旦、浙大、MSRA等多个单位的理论研究组参加。欢迎各位
同学和老师们来听报告和交流。
时间：3月31日，星期四
地点：蒙民伟109
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. Bio: 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. http://math.nju.edu.cn/~yuliang/
2:00 pm - 2:50 pm
Speaker: Ke Yi (HKUST) Title: Tracking Distributed Data Abstract:
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. Bio:
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
databases. http://www.cs.ust.hk/~yike/ 3:00 pm - 4:00 pm Speaker: Kord Eickmeyer (Humboldt University of Berlin) Title: Randomisation and Derandomisation in Descriptive Complexity Theory Abstract:
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. Bio:
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. http://www2.informatik.hu-berlin.de/~eickmeye/
|
