Synergies in Lower Bounds will bring together researchers from various areas of theoretical computer science (complexity, cryptography, algorithms) whose specialty is proving impossibility results: rigorously proving that certain tasks cannot be done efficiently, a.k.a. "lower bounds". There is much in common between impossibility results in algorithms, complexity, and cryptography, and the goal of the workshop is to expose these connections, transfer lower-bound techniques between areas, and explore the boundaries of proving impossibility: What can be proved impossible? What seems too difficult to prove right now? Which directions spell new progress? Which areas or problems have not yet received enough attention by lower bounds experts?

The focus will be on unconditional or "information-theoretic" lower bounds. Workshop topics will include: Communication complexity, circuit complexity, data structures, streaming algorithms, property testing, cryptography, information theory, extractors and pseudo randomness, and learning theory.

The workshop is arranged by the Center for the Theory of Interactive Computation. Speakers in the workshop will include researchers from the Danish and the Chinese sides of the collaboration, as well as a number of invited speakers from other countries. The lectures will include introductory tutorial-style lectures, as well as shorter research contributions, and ample time for discussion.