In this Dagstuhl Seminar, we will address several of the arising questions in the context of circuit and formula sizes, meta-complexity, proof complexity, fine-grained complexity, communication complexity, and classical computational complexity. In each area, powerful tools for proving lower and upper bounds are known, but particularly interesting and powerful results often arise from establishing connections between the fields. By bringing together a diverse group of leading experts and promising young researchers in these areas, the seminar will be an ideal place to discover new, further connections.