讲课题目：通信复杂度及其在流计算中的应用 
讲座时间：2012-12-08 10:00:00 
  
讲座地点：软件园校区办公楼二楼学术报告厅

讲座（一）
讲座题目：通信复杂度及其在流计算中的应用
讲座人：中科院计算所孙晓明研究员
讲座时间：2012年12月8日 10:00
讲座地点：软件园校区高性能中心第一学术报告厅
讲座内容简介：
In this talk I will give a short survey on the basic concepts and results in communication complexity. I will also discuss its applications in the streaming computation. Some graph and linear algebra problems include: approximate the clique number, decide the bipartiteness of a graph, and compute the rank/det of a matrix etc. will be considered. I will present some new randomized /quantum lower bound for these problems.
讲座人简介：
孙晓明，中国科学院计算技术研究所研究员。2005年毕业于清华大学计算机系，获博士学位。曾任清华大学高等研究院助理研究员、副研究员。主要研究方向为算法与计算复杂性。已发表论文30余篇，包括FOCS, SODA, CRYPTO, ICALP, Recomb等会议和SIAM J. Computing, IEEE Tran. Information Theory, J. Cryptology, Algorithmica, JCSS等期刊。2010年至今担任JCST领域编委，多次担任ISAAC、TAMC、COCOON等会议PC。

讲座（二）
讲座题目：When Selfish Agents Meet Distributed System: distributed consensus resilient to strategic manipulations
讲座人：中科院计算所张家琳副研究员
讲座时间：2012年12月8日 11:00
讲座地点：软件园校区高性能中心第一学术报告厅
讲座内容简介：
In traditional research of distributed problems, two types of failures are commonly considered: crash failure (agent stops executing the protocol) and malicious Byzantine failure (agent may do anything). Few works study the selfish agents in the system. This issue is more evident in systems spanning multiple administrative domains, such as peer-to-peer systems, mobile computing systems, and federated cloud computing systems, where each computing entity has selfish incentives. In this talk, we study distributed consensus problem in synchronous systems subject to both crash failures and strategic manipulations by rational agents in the system. We use ex-post Nash equilibrium to model protocols that are resilient to both crash failures and strategic manipulations of rational agents, and we consider collusions among rational agents. For a system with n distributed agents, we design a deterministic protocol that tolerates 2 colluding agents and a randomized protocol that tolerates n-1 colluding agents, and both tolerate any number of crash failures. We also show that if colluders have private channels of communication, there is no protocol that can tolerate even 2 colluding agents and 1 crash failure. These results are the first step of our effort to study richer and more real models in the distributed system.
讲座人简介：
张家琳，中国科学院计算技术研究所副研究员。2010年在清华大学获应用数学博士学位。研究兴趣包括分布式计算的容错研究，社会网络和信息网络，算法博弈论，算法的平滑分析，组合优化。