| Jan 28, 4 |
Marc Kaplan, Sophie Laplante.
"Kolmogorov complexity and combinatorial methods in communication complexity."
ECCC TR08-109. |
| Feb 11, 18 |
Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis.
"Exponential Separation of Quantum and Classical One-Way Communication
Complexity."
Siam Journal on Computing, 2008. |
| Feb 25 |
Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de
Wolf.
"Exponential separations for one-way quantum communication complexity, with
applications to cryptography."
Siam Journal on Computing, 2008. |
| Mar 4, 11 |
Matei David, Phuong Nguyen, Periklis Papakonstantinou.
"Hierarchies for (De)Randomization and Connections to Streaming."
Submitted, 2008. |
| Mar 25, Apr 8, 15, 22 |
Eyal Kushilevitz, Enav Weinreb.
"On the Complexity of Communication Complexity."
STOC 2009. |
| Apr 29, May 6 |
Joshua Brody, Amit Chakrabarti.
"A Multi-Round Communication Lower Bound for Gap Hamming and Some
Consequences."
ECCC TR09-015. |
| May 13, 20, 27, June 10 |
Boaz Barak, Mark Braverman, Xi Chen, Anup Rao.
"Direct sums in randomized communication complexity."
ECCC TR09-044. |
| June 17,24 |
Omer Barkol, Yuval Ishai, Enav Weinreb.
"Communication in the presence of replication."
STOC 2008. |
| July 1 |
Joshua Brody.
"The Maximum Communication Complexity of Multi-party Pointer Jumping."
CCC 2009. |
| July 8 |
Joshua Brody, Amit Chakrabarti.
"Sublinear Communication Protocols for Multi-Party Pointer Jumping and a
Related Lower Bound."
STACS 2008. |