Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-041 | 31st March 2014 18:02

Recent advances on the log-rank conjecture in communication complexity

RSS-Feed




TR14-041
Authors: Shachar Lovett
Publication: 31st March 2014 20:34
Downloads: 2996
Keywords: 


Abstract:

The log-rank conjecture is one of the fundamental open problems in communication complexity. It speculates that the deterministic communication complexity of any two-party function is equal to the log of the rank of its associated matrix, up to polynomial factors. Despite much research, we still know very little about this conjecture. Recently, there has been renewed interest in this conjecture and its relations to other fundamental problems in complexity theory. This survey describes some of the recent progress, and hints at potential directions for future research.



ISSN 1433-8092 | Imprint