Home Sitemap Contact 中文 CAS
 
Navigation
  • HOME
  • About Us
  • Research
  • People
  • International Cooperation
  • News
  • Education & Training
  • Join Us
  • Publications
  • Papers
  • Resources
  • Links
  • Location:Home>News>Upcoming Events
    Space-bounded Communication Complexity
    Author:
    ArticleSource:
    Update time: 2012-06-01
    Close
    Text Size: A A A
    Print
    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
    Abstract:
    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