Communication Complexity and Applications 2017 at the Banff International Research Station

The workshop was held at Banff International Research Station in Banff, Alberta, Canada, in March 2017. This list contains open problems suggested by participants during the open problems session. The list of open problems was scribed by Sagar Kale and authors of the problems. Further information can be found at the workshop webpage.

Links

• Workshop webpage

Open Problems

• Problem 75: Data Structure Lower Bound in the Cell Probe Model
• Problem 76: External Information and Amortized Expected Communication
• Problem 77: Frontiers in Structural Communication Complexity
• Problem 78: Linear Sketching Over $F_2$
• Problem 79: Cryptogenography
• Problem 80: Merlin–Arthur Communication Complexity of Connectivity