Individual Communication Complexity: Extended Abstract.
作者： Paul M. B. Vitányi , Nikolai K. Vereshchagin , Harry Buhrman , Hartmut Klauck
DOI:
关键词: Computer science 、 Communication complexity 、 Worst-case complexity 、 Theoretical computer science
摘要:
参考文章(7)
Harry Buhrman, Tao Jiang, Ming Li, Paul Vitányi, New applications of the incompressibility method: part II Theoretical Computer Science. ,vol. 235, pp. 59- 70 ,(2000) , 10.1016/S0304-3975(99)00184-X
Andrej A. Muchnik, Conditional complexity and codes Theoretical Computer Science. ,vol. 271, pp. 97- 109 ,(2002) , 10.1016/S0304-3975(01)00033-0
Leonid A. Levin, Average case complete problems SIAM Journal on Computing. ,vol. 15, pp. 285- 286 ,(1986) , 10.1137/0215020
N. Vereshchagin, P. Vitanyi, Kolmogorov's structure functions with an application to the foundations of model selection foundations of computer science. pp. 751- 760 ,(2002) , 10.1109/SFCS.2002.1182000
C.H. Bennett, P. Gacs, Ming Li, P.M.B. Vitanyi, W.H. Zurek, Information distance IEEE Transactions on Information Theory. ,vol. 44, pp. 1407- 1423 ,(1998) , 10.1109/18.681318
Noam Nisan, Eyal Kushilevitz, Communication Complexity ,(1996)
Paul Vitányi, Ming Li, An introduction to Kolmogorov complexity and its applications Graduate texts in computer science. pp. 1- 637 ,(1997)