Home Sitemap Contact 中文 CAS
  • HOME
  • About Us
  • Research
  • People
  • International Cooperation
  • News
  • Education & Training
  • Join Us
  • Publications
  • Papers
  • Resources
  • Life at ICT
  • Links
  • Location:Home>News>Upcoming Events
    Space-bounded Communication Complexity
    Update time: 2012-06-01
    Text Size: A A A
    Title: Space-bounded Communication Complexity
    Speaker: Periklis A. Papakonstantinou
    Inviter: Prof. Sun Xiaoming, Center for Advanced Computing Research, ICT
    Time: 14:00pm—15:00pm, June 5th, 2012 (Tuesday)
    Place: Room 1234, Institute of Computing Technology, Chinese Academy of Sciences
    We put forward a new program for developing tools towards understanding the limitations of space-bounded computation. This new, pure information-theoretic model restricts the classical 2-player communication complexity model by limiting (in some sense) the space each player can use to compress communication. We set the foundations of this model, and we develop two fundamentally new techniques (model-specific) for proving lower bounds. As a first step we aim to provide a concrete explanation on what's different in the use of space when computing each of the following three basic functions: EQUALITY, INNER-PRODUCT, and st-CONNECTIVITY.

    This is joint work in progress with Joshua Broody, Shiteng Chen, Hao Song, and Xiaoming Sun

    Address :No.6 Kexueyuan South Road Zhongguancun,Haidian District Beijing,China
    Postcode :100190 Tel : (8610)62601166 Email : office@ict.ac.cn