Hao Song
Institute for Interdisciplinary Information Sciences

Address: Room 4-609, FIT Building,Tsinghua University, Beijing, P. R. China
Tel: +86-10-62781693 Ext. 1643


Education Background:


 

I'm a doctoral candidate at the Institute for Theoretical Computer Science (ITCS) in IIIS of Tsinghua, under the supervision of Professor Periklis Papakonstantinou. 

I'm also a member of the Laboratory for the Study of Randomness in Computation and Cryptographic Complexity, please 
click here for more information about this lab.
 
I got my bachelor's degree in computer science from Tsinghua University in 2008, and joined the Institute for Theoretical Computer Science (ITCS) in IIIS of Tsinghua in the same year.


Research Interests:


 

I have a general research interest in computational complexity and algorithm design.

Currently, I'm focused on the study of space-bounded communication complexity. The study of communication complexity was first initiated by Professor Andrew Chi-Chih Yao in 1979. It has since found applications in diverse areas such as circuit complexity, VLSI design, streaming algorithms and property testing. But as a powerful tool for proving lower bounds in various areas, no super-linear lower bound can be achieved in the classical communication complexity model, since the players in the model are computationally unbounded.

Originally motivated by the goal to prove better lower bounds, particularly in the streaming computation setting, we introduced a new communication complexity model in which each player only has limited memory space to compress the communication history into. This leads to a reexamination of the role memory space plays in communication. We compare the relative power of the space-bounded communication model where different types of memory is involved e.g. write-once, oblivious, etc.


Publications:

 

Periklis A. Papakonstantinou, Dominik Scheder, Hao Song: Overlays and Limited Memory Communication Mode(l)s, IEEE Conference on Computational Complexity (CCC) 2014 (submitted) (click here for the ECCC version)


Joshua Brody, Shiteng Chen, Periklis A. Papakonstantinou, Hao Song, Xiaoming Sun: Space-Bounded Communication Complexity, Innovations in Theoretical Computer Science (ITCS) 2013 [pdf]


Talks:
 

Rectangle-Overlay and Limited-Memory Communication Models, at CTIC (Aarhus University, Denmark), CWI (Amsterdam, Netherlands) and LIAFA (Université Paris Diderot - Paris 7, France).

Space-Bounded Communication Complexity, at China Theory Week (CTW) 2012, Aarhus University, Denmark


Teaching Assistant:
 

2012 Fall - Representations, Algorithms, and Computation on Groups - Instructor: Periklis Papakonstantinou

2010 Fall - Operating System - Instructor: Yong-Guang Zhang

2010 Spring - Mathematics for Computer Science - Instructor: Andrew Chi-Chih Yao

2008 & 2009 Fall - Introduction to Computer Science, 2008 & 2009 Fall - Instructor: Frans Schalekamp, Anke van Zuylen